0votos

Número de caminos en una cuadrícula en Haskell

por josejuan hace 6 años

Lo divertido de este problema (para mí), es que no tiene solución eficiente y es divertido ver de que formas podemos arañar algo de eficiencia. La mejor forma (que conozca) es usando árboles de decisión ZDD (en el enunciado se referencia). Pero lo suyo es hacerlo "al vuelo". Las tres estrategias que yo he usado aquí es la que ya ha usado durbon, empezar con un avance (y multiplicar el nº por dos) y paralelizar.

Dada una cuadrícula de NxN nodos, ¿cuantos caminos diferentes hay (sin pasar dos veces por el mismo nodos) al ir de una esquina a su opuesta diagonal?

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
{-- 
 * cada función está expandida (se podría hacer una sola) por eficiencia. 
 
 * como tiempo de referencia la última solución de "durbon" me da para n=6 un tiempo de: 
 
$ time -f "time: %E, memory: %M Kb" python2 paths.py   
17.5 
time: 0:17.60, memory: 5940 Kb 
 
* esta versión en Haskell (1paths.5.x), da estos tiempos (6 cpu AMD Phenom(tm) II 2.7GHz)  
 
$ for i in 4 5 6 7; do echo "1paths.5.x $i:"; time -f "\ttiempo: %E" ./1paths.5.x $i +RTS -N6; done 
1paths.5.x 4: 
184 
        tiempo: 0:00.00 
1paths.5.x 5: 
8512 
        tiempo: 0:00.01 
1paths.5.x 6: 
1262816 
        tiempo: 0:00.43 
1paths.5.x 7: 
575780564 
        tiempo: 3:37.69 
 
 
--} 
import Data.Array 
import System.Environment(getArgs) 
import Control.Parallel 
import Control.Parallel.Strategies 
 
countingD n g p@(x, y) = 
  if g!p then 0 else if x == n then if y == n then 1 else l + d else if x == 1 then r + d else if y == 1 then r + d else if y == n then r else l `par` r `par` d `pseq` (l + r + d) 
  where g' = g//[((x, y), True)] 
        r = countingR n g' $! (x + 1, y) 
        d = countingD n g' $! (x, y + 1) 
        l = countingL n g' $! (x - 1, y) 
 
countingU n g p@(x, y) = 
  if g!p then 0 else if x == n then if y == n then 1 else l else if x == 1 then r else if y == 1 then r else if y == n then r + u else l `par` r `par` u `pseq` (l + r + u) 
  where g' = g//[((x, y), True)] 
        r = countingR n g' $! (x + 1, y) 
        l = countingL n g' $! (x - 1, y) 
        u = countingU n g' $! (x, y - 1) 
 
countingR n g p@(x, y) = 
  if g!p then 0 else if x == n then if y == n then 1 else d else if x == 1 then r + d else if y == 1 then r + d else if y == n then r + u else r `par` u `par` d `pseq` (r + u + d) 
  where g' = g//[((x, y), True)] 
        r = countingR n g' $! (x + 1, y) 
        d = countingD n g' $! (x, y + 1) 
        u = countingU n g' $! (x, y - 1) 
 
countingL n g p@(x, y) = 
  if g!p then 0 else if x == n then if y == n then 1 else l + d else if x == 1 then d else if y == 1 then d else if y == n then u else l `par` u `par` d `pseq` (l + u + d) 
  where g' = g//[((x, y), True)] 
        d = countingD n g' $! (x, y + 1) 
        l = countingL n g' $! (x - 1, y) 
        u = countingU n g' $! (x, y - 1) 
 
count1Paths :: Int -> Int 
count1Paths n = 
  let n1 = n + 1 
      f x y = or [x == 0, y == 0, x == n1, y == n1, x == 1 && y == 1] 
      g = array ((0, 0), (n1, n1)) [((x, y), if f x y then True else False) | x <- [0..n1], y <- [0..n1]] 
       
  -- podimos dividir el esfuerzo por dos eliminando la simetría de la diagonal 
  in  2 * countingD n g (1, 2) 
       
main = do 
  (n':_) <- getArgs 
  print $ count1Paths $ read n' 
1 comentario
0votos

Escrito por josejuan hace 6 años

como tiempo de referencia la última solución de "durbon"

¡Perdón! es "drabor"!

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.