Caminos en una retícula (con programación dinámica)

José A. Alonso

09-10-2023

Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3x4 se numera como sigue:

   |-------+-------+-------+-------|
   | (1,1) | (1,2) | (1,3) | (1,4) |
   | (2,1) | (2,2) | (2,3) | (2,4) |
   | (3,1) | (3,2) | (3,3) | (3,4) |
   |-------+-------+-------+-------|

Definir la función

   caminos :: (Int,Int) -> [[(Int,Int)]]

tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,

   λ> caminos (2,3)
   [[(1,1),(1,2),(1,3),(2,3)],
    [(1,1),(1,2),(2,2),(2,3)],
    [(1,1),(2,1),(2,2),(2,3)]]
   λ> mapM_ print (caminos (3,4))
   [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

module Programacion_dinamica_Caminos_en_una_reticula where

import Data.Array (Array, (!), array)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª solución (por recursión)
-- ===========================

caminos1 :: (Int,Int) -> [[(Int,Int)]]
caminos1 p = map reverse (caminos1Aux p)
  where
    caminos1Aux (1,y) = [[(1,z) | z <- [y,y-1..1]]]
    caminos1Aux (x,1) = [[(z,1) | z <- [x,x-1..1]]]
    caminos1Aux (x,y) = [(x,y) : cs | cs <- caminos1Aux (x-1,y) ++
                                            caminos1Aux (x,y-1)]

-- 2ª solución (con programación dinámica)
-- =======================================

caminos2 :: (Int,Int) -> [[(Int,Int)]]
caminos2 p = map reverse (matrizCaminos p ! p)

matrizCaminos :: (Int,Int) -> Array (Int,Int) [[(Int,Int)]]
matrizCaminos (m,n) = q
  where
    q = array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    f 1 y = [[(1,z) | z <- [y,y-1..1]]]
    f x 1 = [[(z,1) | z <- [x,x-1..1]]]
    f x y = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> maximum (head (caminos1 (2000,2000)))
--    (2000,2000)
--    (0.01 secs, 3,459,576 bytes)
--    λ> maximum (head (caminos2 (2000,2000)))
--    (2000,2000)
--    (2.79 secs, 1,507,636,688 bytes)

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminos1 (2,3) `shouldBe`
    [[(1,1),(1,2),(1,3),(2,3)],
     [(1,1),(1,2),(2,2),(2,3)],
     [(1,1),(2,1),(2,2),(2,3)]]
  it "e2" $
    caminos2 (2,3) `shouldBe`
    [[(1,1),(1,2),(1,3),(2,3)],
     [(1,1),(1,2),(2,2),(2,3)],
     [(1,1),(2,1),(2,2),(2,3)]]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.0010 seconds
--    2 examples, 0 failures

Soluciones en Python

from collections import defaultdict
from sys import setrecursionlimit
from timeit import Timer, default_timer

setrecursionlimit(10**6)

# 1ª solución (por recursión)
# ===========================

def caminos1(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
    def aux(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
        (x, y) = p
        if x == 1:
            return [[(1,z) for z in range(y, 0, -1)]]
        if y == 1:
            return [[(z,1) for z in range(x, 0, -1)]]
        return [[(x,y)] + cs for cs in aux((x-1,y)) + aux((x,y-1))]

    return [list(reversed(ps)) for ps in aux(p)]

# 2ª solución (con programación dinámica)
# =======================================

def caminos2(p: tuple[int, int]) -> list[list[tuple[int, int]]]:
    return [list(reversed(ps)) for ps in diccionarioCaminos(p)[p]]


# diccionarioCaminos((m,n)) es el diccionario cuyas claves son los
# puntos de la retícula mxn y sus valores son los caminos a dichos
# puntos. Por ejemplo,
#    >>> diccionarioCaminos((2,3))
#    defaultdict(<class 'list'>,
#                {(1,1): [[(1,1)]],
#                 (1,2): [[(1,2),(1,1)]],
#                 (1,3): [[(1,3),(1,2),(1,1)]],
#                 (2,1): [[(2,1),(1,1)]],
#                 (2,2): [[(2,2),(1,2),(1,1)],
#                         [(2,2),(2,1),(1,1)]],
#                 (2,3): [[(2,3),(1,3),(1,2),(1,1)],
#                         [(2,3),(2,2),(1,2),(1,1)],
#                         [(2,3),(2,2),(2,1),(1,1)]]})
def diccionarioCaminos(p: tuple[int, int]) -> dict[tuple[int, int], list[list[tuple[int, int]]]]:
    m, n = p
    q = defaultdict(list)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1:
                q[(i, j)] = [[(1, z) for z in range(j, 0, -1)]]
            elif j == 1:
                q[(i, j)] = [[(z, 1) for z in range(i, 0, -1)]]
            else:
                q[(i, j)] = [[(i, j)] + 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('max(caminos1((13,13))[0])')
#    26.75 segundos
#    >>> tiempo('max(caminos2((13,13))[0])')
#    7.40 segundos

# Verificación
# ============

def test_caminos() -> None:
    assert caminos1((2,3)) == \
        [[(1,1),(1,2),(1,3),(2,3)],
         [(1,1),(1,2),(2,2),(2,3)],
         [(1,1),(2,1),(2,2),(2,3)]]
    assert caminos2((2,3)) == \
        [[(1,1),(1,2),(1,3),(2,3)],
         [(1,1),(1,2),(2,2),(2,3)],
         [(1,1),(2,1),(2,2),(2,3)]]
    print("Verificado")

# La verificación es
#    >>> test_caminos()
#    Verificado