0votos

Laberinto numérico en Haskell

por josejuan hace 2 años

Se puede aproximar con coste logarítmico si reducimos de N a 1 y de 1 a M. La solución suele estar entorno al 123% de la mejor solución pero permite obtener rutas entre números absurdamente grandes.

Búsqueda de la longitud del camino más corto en un laberinto numérico.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
-- De N a 1 y de 1 a M, luego reducimos 
deNaM :: ℤ → ℤ → [ℤ] 
deNaM n m = comprimir (deNa1 n ⧺ de1aN m) 
 
-- Obtiene una ruta desde N hasta 1 
deNa1 :: ℤ → [ℤ] 
deNa1 1 = [1] 
deNa1 n = let (d, r) = n `divMod` 2 
          in  if r ≡ 0 
                 then n: deNa1 d 
                 else n: (2 × n): (2 × n + 2): deNa1 ((2 × n + 2) ÷ 2) 
 
-- Obtiene una ruta desde 1 hasta N, consiste en asumir que es par y añadir 
-- bits por la derecha. El caso impar es convertirlo en par y dividir 
de1aNe :: ℤ → [ℤ] 
de1aNe = g 2 ∘ tail ∘ bits 
  where g k (𝐹:[]) = [k] 
        g k (𝑇:xs) = k: (2 × k): g (2 × k + 2) xs 
        g k (𝐹:xs) = k:          g (2 × k    ) xs 
 
de1aN :: ℤ → [ℤ] 
de1aN n | even n = de1aNe n 
        | odd  n = de1aNe (2 × n) ⧺ [n] 
 
-- Elimina los tramos que van de un nº al mismo nº (ej. en 
-- 10,5,10,12,6,3,6,8,4,2,1 se puede reducir 6,3,6 a 6) 
comprimir :: [ℤ] → [ℤ] 
comprimir [] = [] 
comprimir (x:xs) | x ∈ xs    = comprimir $ dropWhile (x ≢) xs 
                 | otherwise = x: comprimir xs 
 
-- Bits del n0 
bits :: ℤ → [𝔹] 
bits = reverse ∘ map ((0<).snd) ∘ tail ∘ takeWhile (λ(a, b) →  a + b > 0) ∘ iterate ((`divMod` 2) ∘ fst) ∘ (,0) 
 
{- 
 
> length $ deNaM 9234562340234201928371719128475610912928374823491238 897623465123016314078162349851514981263501625016234981253412875342323 
597 
(0.05 secs, 6,536,704 bytes) 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.