Caminos en una matriz (con programación dinámica)
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 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 2 3 4 5 6 7 8 9 10 |
[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
|
1 |
caminos :: Matrix Int -> [[Int]] |
tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 |
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 |
|
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 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def caminos1(m: list[list[int]]) -> list[list[int]]: nf = len(m) nc = len(m[0]) return list(reversed([list(reversed(xs)) for xs in caminos1Aux(m, (nf,nc))])) # 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, def caminos1Aux(m: list[list[int]], p: tuple[int, int]) -> list[list[int]]: (i, j) = p if p == (1,1): return [[m[0][0]]] if i == 1: return [[m[0][k-1] for k in range(j, 0, -1)]] if j == 1: return [[m[k-1][0] for k in range(i, 0, -1)]] return [[m[i-1][j-1]] + xs for xs in caminos1Aux(m, (i,j-1)) + caminos1Aux(m, (i-1,j))] # 2ª solución (mediante programación dinámica) # ============================================ def caminos2(p: list[list[int]]) -> list[list[int]]: m = len(p) n = len(p[0]) return [list(reversed(xs)) for xs in diccionarioCaminos(p)[(m, n)]] # diccionarioCaminos(p) es el diccionario cuyas claves son los # puntos de la matriz p y sus valores son los caminos a dichos # puntos. Por ejemplo, # >>> diccionarioCaminos([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) # defaultdict(<class 'list'>, # {(1, 1): [[1]], # (1, 2): [[6, 1]], # (1, 3): [[11, 6, 1]], # (1, 4): [[2, 11, 6, 1]], # (2, 1): [[7, 1]], # (2, 2): [[12, 6, 1], [12, 7, 1]], # (2, 3): [[3, 11, 6, 1], [3, 12, 6, 1], [3, 12, 7, 1]], # (2, 4): [[8, 2, 11, 6, 1], [8, 3, 11, 6, 1], # [8, 3, 12, 6, 1], [8, 3, 12, 7, 1]], # (3, 1): [[3, 7, 1]], # (3, 2): [[8, 12, 6, 1], [8, 12, 7, 1], [8, 3, 7, 1]], # (3, 3): [[4, 3, 11, 6, 1], [4, 3, 12, 6, 1], # [4, 3, 12, 7, 1], [4, 8, 12, 6, 1], # [4, 8, 12, 7, 1], [4, 8, 3, 7, 1]], # (3, 4): [[9, 8, 2, 11, 6, 1], [9, 8, 3, 11, 6, 1], # [9, 8, 3, 12, 6, 1], [9, 8, 3, 12, 7, 1], # [9, 4, 3, 11, 6, 1], [9, 4, 3, 12, 6, 1], # [9, 4, 3, 12, 7, 1], [9, 4, 8, 12, 6, 1], # [9, 4, 8, 12, 7, 1], [9, 4, 8, 3, 7, 1]]}) def diccionarioCaminos(p: list[list[int]]) -> dict[tuple[int, int], list[list[int]]]: m = len(p) n = len(p[0]) q = defaultdict(list) for i in range(1, m + 1): for j in range(1, n + 1): if i == 1: q[(i, j)] = [[p[0][z-1] for z in range(j, 0, -1)]] elif j == 1: q[(i, j)] = [[p[z-1][0] for z in range(i, 0, -1)]] else: q[(i, j)] = [[p[i-1][j-1]] + cs for cs in q[(i-1, j)] + q[(i, j-1)]] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('caminos1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 2.20 segundos # >>> tiempo('caminos2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])') # 0.64 segundos # Verificación # ============ def test_caminos() -> None: 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]] assert caminos1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r assert caminos2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == r print("Verificado") # La verificación es # >>> test_caminos() # Verificado |