-
Notifications
You must be signed in to change notification settings - Fork 1
/
Caminos_en_una_matriz.hs
127 lines (112 loc) · 3.71 KB
/
Caminos_en_una_matriz.hs
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
-- Caminos_en_una_matriz.hs
-- Caminos en una matriz (con programación dinámica)
-- José A. Alonso Jiménez <https://jaalonso.github.io>
-- Sevilla, 14-octubre-2023
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Los caminos desde el extremo superior izquierdo (posición (1,1))
-- hasta el extremo inferior derecho (posición (3,4)) en la matriz
-- ( 1 6 11 2 )
-- ( 7 12 3 8 )
-- ( 3 8 4 9 )
-- moviéndose en cada paso una casilla hacia la derecha o abajo, son los
-- siguientes:
-- [1,6,11,2,8,9]
-- [1,6,11,3,8,9]
-- [1,6,12,3,8,9]
-- [1,7,12,3,8,9]
-- [1,6,11,3,4,9]
-- [1,6,12,3,4,9]
-- [1,7,12,3,4,9]
-- [1,6,12,8,4,9]
-- [1,7,12,8,4,9]
-- [1,7, 3,8,4,9]
--
-- Definir la función
-- caminos :: Matrix Int -> [[Int]]
-- tal que (caminos m) es la lista de los caminos en la matriz m desde
-- el extremo superior izquierdo hasta el extremo inferior derecho,
-- moviéndose en cada paso una casilla hacia abajo o hacia la
-- derecha. Por ejemplo,
-- λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
-- [[1,6,11,2,8,9],
-- [1,6,11,3,8,9],
-- [1,6,12,3,8,9],
-- [1,7,12,3,8,9],
-- [1,6,11,3,4,9],
-- [1,6,12,3,4,9],
-- [1,7,12,3,4,9],
-- [1,6,12,8,4,9],
-- [1,7,12,8,4,9],
-- [1,7, 3,8,4,9]]
-- λ> length (caminos (fromList 12 12 [1..]))
-- 705432
-- ---------------------------------------------------------------------
module Caminos_en_una_matriz where
import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)
-- 1ª definición (por recursión)
-- =============================
caminos1 :: Matrix Int -> [[Int]]
caminos1 m =
reverse (map reverse (caminos1Aux m (nf,nc)))
where nf = nrows m
nc = ncols m
-- (caminos1Aux m p) es la lista de los caminos invertidos en la matriz m
-- desde la posición (1,1) hasta la posición p. Por ejemplo,
caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]]
caminos1Aux m (1,1) = [[m!(1,1)]]
caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]]
caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]]
caminos1Aux m (i,j) = [m!(i,j) : xs
| xs <- caminos1Aux m (i,j-1) ++
caminos1Aux m (i-1,j)]
-- 2ª solución (mediante programación dinámica)
-- ============================================
caminos2 :: Matrix Int -> [[Int]]
caminos2 m =
map reverse (matrizCaminos m ! (nrows m, ncols m))
matrizCaminos :: Matrix Int -> Matrix [[Int]]
matrizCaminos m = q
where
q = matrix (nrows m) (ncols m) f
f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]]
f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]]
f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> length (caminos1 (fromList 11 11 [1..]))
-- 184756
-- (3.64 secs, 667,727,568 bytes)
-- λ> length (caminos2 (fromList 11 11 [1..]))
-- 184756
-- (0.82 secs, 129,181,072 bytes)
-- Verificación
-- ============
verifica :: IO ()
verifica = hspec spec
spec :: Spec
spec = do
it "e1" $
caminos1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r
it "e2" $
caminos2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` r
where r = [[1,6,11,2,8,9],
[1,6,11,3,8,9],
[1,6,12,3,8,9],
[1,7,12,3,8,9],
[1,6,11,3,4,9],
[1,6,12,3,4,9],
[1,7,12,3,4,9],
[1,6,12,8,4,9],
[1,7,12,8,4,9],
[1,7, 3,8,4,9]]
-- La verificación es
-- λ> verifica
--
-- e1
-- e2
--
-- Finished in 0.0010 seconds
-- 2 examples, 0 failures