Programación dinámica

Camino de máxima suma en una matriz

PorJosé A. Alonso 24-octubre-20236-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 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia la derecha o hacia 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]

[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 suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   caminoMaxSuma :: Matrix Int -> [Int]

1	caminoMaxSuma :: Matrix Int -> [Int]

tal que caminoMaxSuma m es un camino de máxima suma 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,

   λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [1,7,12,8,4,9]
   λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

[1,7,12,8,4,9]

λ> sum (caminoMaxSuma (fromList 500 500 [1..]))

187001249

Soluciones

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

Soluciones en Haskell

module Camino_de_maxima_suma_en_una_matriz where

import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición de caminoMaxSuma (con caminos1)
-- =============================================

caminoMaxSuma1 :: Matrix Int -> [Int]
caminoMaxSuma1 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos1 m
        k  = maximum (map sum cs)

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ª definición de caminoMaxSuma (con caminos2)
-- =============================================

caminoMaxSuma2 :: Matrix Int -> [Int]
caminoMaxSuma2 m =
  head [c | c <- cs, sum c == k]
  where cs = caminos2 m
        k  = maximum (map sum cs)

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)]

-- 3ª definición de caminoMaxSuma (con programación dinámica)
-- ==========================================================

caminoMaxSuma3 :: Matrix Int -> [Int]
caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))
  where nf = nrows m
        nc = ncols m
        q  = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])
caminoMaxSumaAux m = q
  where
    nf = nrows m
    nc = ncols m
    q  = matrix nf nc f
      where
        f (1,1) = (m!(1,1),[m!(1,1)])
        f (1,j) = (k + m!(1,j), m!(1,j):xs)
          where (k,xs) = q!(1,j-1)
        f (i,1) = (k + m!(i,1), m!(i,1):xs)
          where (k,xs) = q!(i-1,1)
        f (i,j) | k1 > k2   = (k1 + m!(i,j), m!(i,j):xs)
                | otherwise = (k2 + m!(i,j), m!(i,j):ys)
          where (k1,xs) = q!(i,j-1)
                (k2,ys) = q!(i-1,j)

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

-- La comparación es
--    λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))
--    21
--    (3.92 secs, 1,778,557,904 bytes)
--    λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))
--    21
--    (1.16 secs, 798,889,488 bytes)
--    λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))
--    21
--    (0.00 secs, 680,256 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e2" $
    caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]
  it "e3" $
    caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
    `shouldBe` [1,7,12,8,4,9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0007 seconds
--    3 examples, 0 failures

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

module Camino_de_maxima_suma_en_una_matriz where

import Data.Matrix (Matrix, (!), fromLists, matrix, nrows, ncols)

import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición de caminoMaxSuma (con caminos1)

-- =============================================

caminoMaxSuma1 :: Matrix Int -> [Int]

caminoMaxSuma1 m =

head [c | c <- cs, sum c == k]

where cs = caminos1 m

k = maximum (map sum cs)

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ª definición de caminoMaxSuma (con caminos2)

-- =============================================

caminoMaxSuma2 :: Matrix Int -> [Int]

caminoMaxSuma2 m =

head [c | c <- cs, sum c == k]

where cs = caminos2 m

k = maximum (map sum cs)

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)]

-- 3ª definición de caminoMaxSuma (con programación dinámica)

-- ==========================================================

caminoMaxSuma3 :: Matrix Int -> [Int]

caminoMaxSuma3 m = reverse (snd (q ! (nf,nc)))

where nf = nrows m

nc = ncols m

q = caminoMaxSumaAux m

caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int])

caminoMaxSumaAux m = q

where

nf = nrows m

nc = ncols m

q = matrix nf nc f

where

f (1,1) = (m!(1,1),[m!(1,1)])

f (1,j) = (k + m!(1,j), m!(1,j):xs)

where (k,xs) = q!(1,j-1)

f (i,1) = (k + m!(i,1), m!(i,1):xs)

where (k,xs) = q!(i-1,1)

f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs)

| otherwise = (k2 + m!(i,j), m!(i,j):ys)

where (k1,xs) = q!(i,j-1)

(k2,ys) = q!(i-1,j)

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (caminoMaxSuma1 (fromList 11 11 [1..]))

-- 21

-- (3.92 secs, 1,778,557,904 bytes)

-- λ> length (caminoMaxSuma2 (fromList 11 11 [1..]))

-- 21

-- (1.16 secs, 798,889,488 bytes)

-- λ> length (caminoMaxSuma3 (fromList 11 11 [1..]))

-- 21

-- (0.00 secs, 680,256 bytes)

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

caminoMaxSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

it "e2" $

caminoMaxSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

it "e3" $

caminoMaxSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

`shouldBe` [1,7,12,8,4,9]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0007 seconds

-- 3 examples, 0 failures

Soluciones en Python

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

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definición de caminoMaxSuma (con caminos1)
# =============================================

def caminoMaxSuma1(m: list[list[int]]) -> list[int]:
    cs = caminos1(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos1 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 2ª definición de caminoMaxSuma (con caminos2)
# =============================================

def caminoMaxSuma2(m: list[list[int]]) -> list[int]:
    cs = caminos2(m)
    k = max((sum(c) for c in cs))
    return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos2 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 3ª definición de caminoMaxSuma (con programación dinámica)
# ==========================================================

def caminoMaxSuma3(m: list[list[int]]) -> list[int]:
    nf = len(m)
    nc = len(m[0])
    return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))

# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los
# puntos de la matriz p y sus valores son los pares formados por la
# máxima suma de los caminos hasta dicho punto y uno de los caminos con
# esa suma. Por ejemplo,
#    >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])
#    {(1, 1): (1, [1]),
#     (1, 2): (7, [6, 1]),
#     (1, 3): (18, [11, 6, 1]),
#     (1, 4): (20, [2, 11, 6, 1]),
#     (2, 1): (8, [7, 1]),
#     (3, 1): (11, [3, 7, 1]),
#     (2, 2): (20, [12, 7, 1]),
#     (2, 3): (23, [3, 12, 7, 1]),
#     (2, 4): (31, [8, 3, 12, 7, 1]),
#     (3, 2): (28, [8, 12, 7, 1]),
#     (3, 3): (32, [4, 8, 12, 7, 1]),
#     (3, 4): (41, [9, 4, 8, 12, 7, 1])}
def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:
    m = len(p)
    n = len(p[0])
    q: dict[tuple[int, int], tuple[int, list[int]]] = {}
    q[(1, 1)] = (p[0][0], [p[0][0]])
    for j in range(2, n + 1):
        (k, xs) = q[(1, j-1)]
        q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)
    for i in range(2, m + 1):
        (k,xs) = q[(i-1,1)]
        q[(i, 1)] =  (k + p[i-1][0], [p[i-1][0]] + xs)
    for i in range(2, m + 1):
        for j in range(2, n + 1):
            (k1,xs) = q[(i,j-1)]
            (k2,ys) = q[(i-1,j)]
            if k1 > k2:
                q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)
            else:
                q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)
    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('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    1.92 segundos
#    >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.65 segundos
#    >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')
#    0.00 segundos

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

def test_caminoMaxSuma() -> None:
    assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \
        [1, 7, 12, 8, 4, 9]
    print("Verificado")

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

100

101

102

103

104

105

106

107

108

109

from collections import defaultdict

from sys import setrecursionlimit

from timeit import Timer, default_timer

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definición de caminoMaxSuma (con caminos1)

# =============================================

def caminoMaxSuma1(m: list[list[int]]) -> list[int]:

cs = caminos1(m)

k = max((sum(c) for c in cs))

return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos1 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 2ª definición de caminoMaxSuma (con caminos2)

# =============================================

def caminoMaxSuma2(m: list[list[int]]) -> list[int]:

cs = caminos2(m)

k = max((sum(c) for c in cs))

return [c for c in cs if sum(c) == k][0]

# Se usa la función caminos2 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 3ª definición de caminoMaxSuma (con programación dinámica)

# ==========================================================

def caminoMaxSuma3(m: list[list[int]]) -> list[int]:

nf = len(m)

nc = len(m[0])

return list(reversed(diccionarioCaminoMaxSuma(m)[(nf, nc)][1]))

# diccionarioCaminoMaxSuma(p) es el diccionario cuyas claves son los

# puntos de la matriz p y sus valores son los pares formados por la

# máxima suma de los caminos hasta dicho punto y uno de los caminos con

# esa suma. Por ejemplo,

# >>> diccionarioCaminoMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])

# {(1, 1): (1, [1]),

# (1, 2): (7, [6, 1]),

# (1, 3): (18, [11, 6, 1]),

# (1, 4): (20, [2, 11, 6, 1]),

# (2, 1): (8, [7, 1]),

# (3, 1): (11, [3, 7, 1]),

# (2, 2): (20, [12, 7, 1]),

# (2, 3): (23, [3, 12, 7, 1]),

# (2, 4): (31, [8, 3, 12, 7, 1]),

# (3, 2): (28, [8, 12, 7, 1]),

# (3, 3): (32, [4, 8, 12, 7, 1]),

# (3, 4): (41, [9, 4, 8, 12, 7, 1])}

def diccionarioCaminoMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], tuple[int, list[int]]]:

m = len(p)

n = len(p[0])

q: dict[tuple[int, int], tuple[int, list[int]]] = {}

q[(1, 1)] = (p[0][0], [p[0][0]])

for j in range(2, n + 1):

(k, xs) = q[(1, j-1)]

q[(1, j)] = (k + p[0][j-1], [p[0][j-1]] + xs)

for i in range(2, m + 1):

(k,xs) = q[(i-1,1)]

q[(i, 1)] = (k + p[i-1][0], [p[i-1][0]] + xs)

for i in range(2, m + 1):

for j in range(2, n + 1):

(k1,xs) = q[(i,j-1)]

(k2,ys) = q[(i-1,j)]

if k1 > k2:

q[(i,j)] = (k1 + p[i-1][j-1], [p[i-1][j-1]] + xs)

else:

q[(i,j)] = (k2 + p[i-1][j-1], [p[i-1][j-1]] + ys)

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('caminoMaxSuma1([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 1.92 segundos

# >>> tiempo('caminoMaxSuma2([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 0.65 segundos

# >>> tiempo('caminoMaxSuma3([list(range(11*n+1, 11*(n+1)+1)) for n in range(12)])')

# 0.00 segundos

# # Verificación

# # ============

def test_caminoMaxSuma() -> None:

assert caminoMaxSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

assert caminoMaxSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

assert caminoMaxSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == \

[1, 7, 12, 8, 4, 9]

print("Verificado")

# La verificación es

# >>> test_caminoMaxSuma()

# Verificado

Máxima suma de los caminos en una matriz

PorJosé A. Alonso 19-octubre-20234-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 )

( 1 6 11 2 )

( 7 12 3 8 )

( 3 8 4 9 )

moviéndose en cada paso una casilla hacia la derecha o hacia 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]

[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 suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

   maximaSuma :: Matrix Int -> Int

1	maximaSuma :: Matrix Int -> Int

tal que maximaSuma m es el máximo de las sumas 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 a derecha. Por ejemplo,

   λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   41
   λ> maximaSuma (fromList 800 800 [1..])
   766721999

λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

λ> maximaSuma (fromList 800 800 [1..])

766721999

Soluciones

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

Soluciones en Haskell

module Maxima_suma_de_los_caminos_en_una_matriz where

import Data.Matrix (Matrix, (!), fromList, fromLists, matrix, nrows, ncols)
import Test.Hspec (Spec, hspec, it, shouldBe)
import Caminos_en_una_matriz (caminos1, caminos2)

-- 1ª definicion de maximaSuma (con caminos1)
-- ==========================================

maximaSuma1 :: Matrix Int -> Int
maximaSuma1 =
  maximum . map sum . caminos1

-- Se usa la función caminos1 del ejercicio
-- "Caminos en una matriz" que se encuentra en
-- https://bit.ly/45bYoYE


-- 2ª definición de maximaSuma (con caminos2)
-- ==========================================

maximaSuma2 :: Matrix Int -> Int
maximaSuma2 =
  maximum . map sum . caminos2

-- Se usa la función caminos2 del ejercicio
-- "Caminos en una matriz" que se encuentra en
-- https://bit.ly/45bYoYE

-- 3ª definicion de maximaSuma (por recursión)
-- ===========================================

maximaSuma3 :: Matrix Int -> Int
maximaSuma3 m = maximaSuma3Aux m (nf,nc)
  where nf = nrows m
        nc = ncols m

-- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la
-- posición p. Por ejemplo,
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)
--    41
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)
--    32
--    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)
--    31
maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int
maximaSuma3Aux m (1,1) = m ! (1,1)
maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)
maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)
maximaSuma3Aux m (i,j) =
  max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)

-- 4ª solución (mediante programación dinámica)
-- ============================================

maximaSuma4 :: Matrix Int -> Int
maximaSuma4 m = q ! (nf,nc)
  where nf = nrows m
        nc = ncols m
        q  = matrizMaximaSuma m

-- (matrizMaximaSuma m) es la matriz donde en cada posición p se
-- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la
-- matriz m. Por ejemplo,
--    λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
--    (  1  7 18 20 )
--    (  8 20 23 31 )
--    ( 11 28 32 41 )
matrizMaximaSuma :: Matrix Int -> Matrix Int
matrizMaximaSuma m = q
  where nf = nrows m
        nc = ncols m
        q  = matrix nf nc f
          where  f (1,1) = m ! (1,1)
                 f (1,j) = q ! (1,j-1) + m ! (1,j)
                 f (i,1) = q ! (i-1,1) + m ! (i,1)
                 f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)

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

-- La comparación es
--    λ> maximaSuma1 (fromList 11 11 [1..])
--    1781
--    (3.88 secs, 1,525,812,680 bytes)
--    λ> maximaSuma2 (fromList 11 11 [1..])
--    1781
--    (1.08 secs, 546,144,264 bytes)
--    λ> maximaSuma3 (fromList 11 11 [1..])
--    1781
--    (0.55 secs, 217,712,280 bytes)
--    λ> maximaSuma4 (fromList 11 11 [1..])
--    1781
--    (0.01 secs, 643,832 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    maximaSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41
  it "e2" $
    maximaSuma1 (fromList 4 4 [1..]) `shouldBe` 73
  it "e3" $
    maximaSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41
  it "e4" $
    maximaSuma2 (fromList 4 4 [1..]) `shouldBe` 73
  it "e5" $
    maximaSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41
  it "e6" $
    maximaSuma3 (fromList 4 4 [1..]) `shouldBe` 73
  it "e7" $
    maximaSuma4 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41
  it "e8" $
    maximaSuma4 (fromList 4 4 [1..]) `shouldBe` 73

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--    e7
--    e8
--
--    Finished in 0.0034 seconds
--    8 examples, 0 failures

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

128

129

130

131

132

133

134

module Maxima_suma_de_los_caminos_en_una_matriz where

import Data.Matrix (Matrix, (!), fromList, fromLists, matrix, nrows, ncols)

import Test.Hspec (Spec, hspec, it, shouldBe)

import Caminos_en_una_matriz (caminos1, caminos2)

-- 1ª definicion de maximaSuma (con caminos1)

-- ==========================================

maximaSuma1 :: Matrix Int -> Int

maximaSuma1 =

maximum . map sum . caminos1

-- Se usa la función caminos1 del ejercicio

-- "Caminos en una matriz" que se encuentra en

-- https://bit.ly/45bYoYE

-- 2ª definición de maximaSuma (con caminos2)

-- ==========================================

maximaSuma2 :: Matrix Int -> Int

maximaSuma2 =

maximum . map sum . caminos2

-- Se usa la función caminos2 del ejercicio

-- "Caminos en una matriz" que se encuentra en

-- https://bit.ly/45bYoYE

-- 3ª definicion de maximaSuma (por recursión)

-- ===========================================

maximaSuma3 :: Matrix Int -> Int

maximaSuma3 m = maximaSuma3Aux m (nf,nc)

where nf = nrows m

nc = ncols m

-- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la

-- posición p. Por ejemplo,

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)

-- 41

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)

-- 32

-- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)

-- 31

maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int

maximaSuma3Aux m (1,1) = m ! (1,1)

maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j)

maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1)

maximaSuma3Aux m (i,j) =

max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j)

-- 4ª solución (mediante programación dinámica)

-- ============================================

maximaSuma4 :: Matrix Int -> Int

maximaSuma4 m = q ! (nf,nc)

where nf = nrows m

nc = ncols m

q = matrizMaximaSuma m

-- (matrizMaximaSuma m) es la matriz donde en cada posición p se

-- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la

-- matriz m. Por ejemplo,

-- λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])

-- ( 1 7 18 20 )

-- ( 8 20 23 31 )

-- ( 11 28 32 41 )

matrizMaximaSuma :: Matrix Int -> Matrix Int

matrizMaximaSuma m = q

where nf = nrows m

nc = ncols m

q = matrix nf nc f

where f (1,1) = m ! (1,1)

f (1,j) = q ! (1,j-1) + m ! (1,j)

f (i,1) = q ! (i-1,1) + m ! (i,1)

f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j)

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> maximaSuma1 (fromList 11 11 [1..])

-- 1781

-- (3.88 secs, 1,525,812,680 bytes)

-- λ> maximaSuma2 (fromList 11 11 [1..])

-- 1781

-- (1.08 secs, 546,144,264 bytes)

-- λ> maximaSuma3 (fromList 11 11 [1..])

-- 1781

-- (0.55 secs, 217,712,280 bytes)

-- λ> maximaSuma4 (fromList 11 11 [1..])

-- 1781

-- (0.01 secs, 643,832 bytes)

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

maximaSuma1 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41

it "e2" $

maximaSuma1 (fromList 4 4 [1..]) `shouldBe` 73

it "e3" $

maximaSuma2 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41

it "e4" $

maximaSuma2 (fromList 4 4 [1..]) `shouldBe` 73

it "e5" $

maximaSuma3 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41

it "e6" $

maximaSuma3 (fromList 4 4 [1..]) `shouldBe` 73

it "e7" $

maximaSuma4 (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) `shouldBe` 41

it "e8" $

maximaSuma4 (fromList 4 4 [1..]) `shouldBe` 73

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- e7

-- e8

-- Finished in 0.0034 seconds

-- 8 examples, 0 failures

Soluciones en Python

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

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definicion de maximaSuma (con caminos1)
# ==========================================

def maximaSuma1(m: list[list[int]]) -> int:
    return max((sum(xs) for xs in caminos1(m)))

# Se usa la función caminos1 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 2ª definición de maximaSuma (con caminos2)
# ==========================================

def maximaSuma2(m: list[list[int]]) -> int:
    return max((sum(xs) for xs in caminos2(m)))

# Se usa la función caminos2 del ejercicio
# "Caminos en una matriz" que se encuentra en
# https://bit.ly/45bYoYE

# 3ª definicion de maximaSuma (por recursión)
# ===========================================

def maximaSuma3(m: list[list[int]]) -> int:
    nf = len(m)
    nc = len(m[0])
    return maximaSuma3Aux(m, (nf,nc))

# (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la
# posición p. Por ejemplo,
#    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)
#    41
#    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)
#    32
#    λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)
#    31
def maximaSuma3Aux(m: list[list[int]], p: tuple[int, int]) -> int:
    (i, j) = p
    if (i, j) == (1, 1):
        return m[0][0]
    if i == 1:
        return maximaSuma3Aux(m, (1,j-1)) + m[0][j-1]
    if j == 1:
        return maximaSuma3Aux(m, (i-1,1)) + m[i-1][0]
    return max(maximaSuma3Aux(m, (i,j-1)), maximaSuma3Aux(m, (i-1,j))) + m[i-1][j-1]

# 4ª solución (mediante programación dinámica)
# ============================================

def maximaSuma4(p: list[list[int]]) -> int:
    m = len(p)
    n = len(p[0])
    return diccionarioMaxSuma(p)[(m,n)]

# diccionarioMaxSuma(p) es el diccionario cuyas claves son los
# puntos de la matriz p y sus valores son las máximas sumas de los
# caminos a dichos puntos. Por ejemplo,
#    diccionarioMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])
#    defaultdict(<class 'int'>,
#                {(1, 0): 0,
#                 (1, 1): 1,  (1, 2): 7,  (1, 3): 18, (1, 4): 20,
#                 (2, 1): 8,  (2, 2): 20, (2, 3): 23, (2, 4): 31,
#                 (3, 1): 11, (3, 2): 28, (3, 3): 32, (3, 4): 41})
def diccionarioMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], int]:
    m = len(p)
    n = len(p[0])
    q: dict[tuple[int, int], int] = defaultdict(int)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == 1:
                q[(i, j)] = q[(1,j-1)] + p[0][j-1]
            elif j == 1:
                q[(i, j)] = q[(i-1,1)] + p[i-1][0]
            else:
                q[(i, j)] = max(q[(i,j-1)], q[(i-1,j)]) + p[i-1][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('maximaSuma1([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')
#    4.95 segundos
#    >>> tiempo('maximaSuma2([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')
#    1.49 segundos
#    >>> tiempo('maximaSuma3([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')
#    0.85 segundos
#    >>> tiempo('maximaSuma4([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')
#    0.00 segundos

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

def test_maximaSuma() -> None:
    assert maximaSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41
    assert maximaSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41
    assert maximaSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41
    assert maximaSuma4([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41
    print("Verificado")

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

from collections import defaultdict

from sys import setrecursionlimit

from timeit import Timer, default_timer

from src.Caminos_en_una_matriz import caminos1, caminos2

setrecursionlimit(10**6)

# 1ª definicion de maximaSuma (con caminos1)

# ==========================================

def maximaSuma1(m: list[list[int]]) -> int:

return max((sum(xs) for xs in caminos1(m)))

# Se usa la función caminos1 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 2ª definición de maximaSuma (con caminos2)

# ==========================================

def maximaSuma2(m: list[list[int]]) -> int:

return max((sum(xs) for xs in caminos2(m)))

# Se usa la función caminos2 del ejercicio

# "Caminos en una matriz" que se encuentra en

# https://bit.ly/45bYoYE

# 3ª definicion de maximaSuma (por recursión)

# ===========================================

def maximaSuma3(m: list[list[int]]) -> int:

nf = len(m)

nc = len(m[0])

return maximaSuma3Aux(m, (nf,nc))

# (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la

# posición p. Por ejemplo,

# λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4)

# 41

# λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3)

# 32

# λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4)

# 31

def maximaSuma3Aux(m: list[list[int]], p: tuple[int, int]) -> int:

(i, j) = p

if (i, j) == (1, 1):

return m[0][0]

if i == 1:

return maximaSuma3Aux(m, (1,j-1)) + m[0][j-1]

if j == 1:

return maximaSuma3Aux(m, (i-1,1)) + m[i-1][0]

return max(maximaSuma3Aux(m, (i,j-1)), maximaSuma3Aux(m, (i-1,j))) + m[i-1][j-1]

# 4ª solución (mediante programación dinámica)

# ============================================

def maximaSuma4(p: list[list[int]]) -> int:

m = len(p)

n = len(p[0])

return diccionarioMaxSuma(p)[(m,n)]

# diccionarioMaxSuma(p) es el diccionario cuyas claves son los

# puntos de la matriz p y sus valores son las máximas sumas de los

# caminos a dichos puntos. Por ejemplo,

# diccionarioMaxSuma([[1,6,11,2],[7,12,3,8],[3,8,4,9]])

# defaultdict(<class 'int'>,

# {(1, 0): 0,

# (1, 1): 1, (1, 2): 7, (1, 3): 18, (1, 4): 20,

# (2, 1): 8, (2, 2): 20, (2, 3): 23, (2, 4): 31,

# (3, 1): 11, (3, 2): 28, (3, 3): 32, (3, 4): 41})

def diccionarioMaxSuma(p: list[list[int]]) -> dict[tuple[int, int], int]:

m = len(p)

n = len(p[0])

q: dict[tuple[int, int], int] = defaultdict(int)

for i in range(1, m + 1):

for j in range(1, n + 1):

if i == 1:

q[(i, j)] = q[(1,j-1)] + p[0][j-1]

elif j == 1:

q[(i, j)] = q[(i-1,1)] + p[i-1][0]

else:

q[(i, j)] = max(q[(i,j-1)], q[(i-1,j)]) + p[i-1][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('maximaSuma1([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')

# 4.95 segundos

# >>> tiempo('maximaSuma2([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')

# 1.49 segundos

# >>> tiempo('maximaSuma3([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')

# 0.85 segundos

# >>> tiempo('maximaSuma4([list(range(12*n+1, 12*(n+1)+1)) for n in range(12)])')

# 0.00 segundos

# Verificación

# ============

def test_maximaSuma() -> None:

assert maximaSuma1([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41

assert maximaSuma2([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41

assert maximaSuma3([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41

assert maximaSuma4([[1,6,11,2],[7,12,3,8],[3,8,4,9]]) == 41

print("Verificado")

# La verificación es

# >>> test_maximaSuma()

# Verificado

Caminos en una matriz (con programación dinámica)

PorJosé A. Alonso 14-octubre-202330-septiembre-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 )

( 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]

[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]]

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,

   λ> 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

λ> 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.

Soluciones en Haskell

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

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

Soluciones en Python

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

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

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

PorJosé A. Alonso 9-octubre-202318-septiembre-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 3×4 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) |
   |-------+-------+-------+-------|

|-------+-------+-------+-------|

| (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)]]

1	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)]

λ> 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

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

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

La distancia Levenshtein (con programación dinámica)

PorJosé A. Alonso 4-octubre-202315-septiembre-2023

La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:

insertar un carácter (por ejemplo, de «abc» a «abca»)
eliminar un carácter (por ejemplo, de «abc» a «ac»)
sustituir un carácter (por ejemplo, de «abc» a «adc»)

Por ejemplo, la distancia de Levenshtein entre «casa» y «calle» es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:

   "casa"  --> "cala"  (sustitución de 's' por 'l')
   "cala"  --> "calla" (inserción de 'l' entre 'l' y 'a')
   "calla" --> "calle" (sustitución de 'a' por 'e')

"casa" --> "cala" (sustitución de 's' por 'l')

"cala" --> "calla" (inserción de 'l' entre 'l' y 'a')

"calla" --> "calle" (sustitución de 'a' por 'e')

Definir la función

   levenshtein :: String -> String -> Int

1	levenshtein :: String -> String -> Int

tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,

   levenshtein "casa"  "calle"    ==  3
   levenshtein "calle" "casa"     ==  3
   levenshtein "casa"  "casa"     ==  0
   levenshtein "ana" "maria"      ==  3
   levenshtein "agua" "manantial" ==  7

levenshtein "casa" "calle" == 3

levenshtein "calle" "casa" == 3

levenshtein "casa" "casa" == 0

levenshtein "ana" "maria" == 3

levenshtein "agua" "manantial" == 7

Soluciones

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

Soluciones en Haskell

module Levenshtein where

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

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

levenshtein1 :: String -> String -> Int
levenshtein1 "" ys = length ys
levenshtein1 xs "" = length xs
levenshtein1 c1@(x:xs) c2@(y:ys)
  | x == y    = levenshtein1 xs ys
  | otherwise = 1 + minimum [ levenshtein1 xs c2
                            , levenshtein1 c1 ys
                            , levenshtein1 xs ys]

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

levenshtein2 :: String -> String -> Int
levenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n)
  where  m = length xs
         n = length ys

-- (matrizLevenshtein xs ys) es la matriz cuyo número de filas es la
-- longitud de xs, cuyo número de columnas es la longitud de ys y en
-- valor en la posición (i,j) es la distancia de Levenshtein entre los
-- primeros i caracteres de xs y los j primeros caracteres de ys. Por
-- ejemplo,
--    λ> elems (matrizLevenshtein "casa" "calle")
--    [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3]
-- Gráficamente,
--       c a l l e
--     0,1,2,3,4,5,
--  c  1,0,1,2,3,4,
--  a  2,1,0,1,2,3,
--  s  3,2,1,1,2,3,
--  a  4,3,2,2,2,3
matrizLevenshtein :: String -> String -> Array (Int,Int) Int
matrizLevenshtein xs ys = q where
  q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]]
  m = length xs
  n = length ys
  f 0 j = j
  f i 0 = i
  f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1)
        | otherwise                  = 1 + minimum [ q ! (i-1,j)
                                                   , q ! (i,j-1)
                                                   , q ! (i-1,j-1)]

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

-- La comparación es
--    λ> levenshtein1 (show (2^33)) (show (3^33))
--    12
--    (16.19 secs, 11,766,254,536 bytes)
--    λ> levenshtein2 (show (2^33)) (show (3^33))
--    12
--    (0.02 secs, 0 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "ej1" $
    levenshtein1 "casa"  "calle"    `shouldBe`  3
  it "ej2" $
    levenshtein1 "calle" "casa"     `shouldBe`  3
  it "ej3" $
    levenshtein1 "casa"  "casa"     `shouldBe`  0
  it "ej4" $
    levenshtein1 "ana" "maria"      `shouldBe`  3
  it "ej5" $
    levenshtein1 "agua" "manantial" `shouldBe`  7
  it "ej6" $
    levenshtein2 "casa"  "calle"    `shouldBe`  3
  it "ej7" $
    levenshtein2 "calle" "casa"     `shouldBe`  3
  it "ej8" $
    levenshtein2 "casa"  "casa"     `shouldBe`  0
  it "ej9" $
    levenshtein2 "ana" "maria"      `shouldBe`  3
  it "ej10" $
    levenshtein2 "agua" "manantial" `shouldBe`  7

-- La verificación es
--    λ> verifica
--
--    ej1
--    ej2
--    ej3
--    ej4
--    ej5
--    ej6
--    ej7
--    ej8
--    ej9
--    ej10
--
--    Finished in 0.0024 seconds
--    10 examples, 0 failures

100

101

102

103

104

105

106

107

module Levenshtein where

import Data.Array(Array, (!), array)

import Test.Hspec (Spec, hspec, it, shouldBe)

-- 1ª definición (por recursión)

-- =============================

levenshtein1 :: String -> String -> Int

levenshtein1 "" ys = length ys

levenshtein1 xs "" = length xs

levenshtein1 c1@(x:xs) c2@(y:ys)

| x == y = levenshtein1 xs ys

| otherwise = 1 + minimum [ levenshtein1 xs c2

, levenshtein1 c1 ys

, levenshtein1 xs ys]

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

-- =========================================

levenshtein2 :: String -> String -> Int

levenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n)

where m = length xs

n = length ys

-- (matrizLevenshtein xs ys) es la matriz cuyo número de filas es la

-- longitud de xs, cuyo número de columnas es la longitud de ys y en

-- valor en la posición (i,j) es la distancia de Levenshtein entre los

-- primeros i caracteres de xs y los j primeros caracteres de ys. Por

-- ejemplo,

-- λ> elems (matrizLevenshtein "casa" "calle")

-- [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3]

-- Gráficamente,

-- c a l l e

-- 0,1,2,3,4,5,

-- c 1,0,1,2,3,4,

-- a 2,1,0,1,2,3,

-- s 3,2,1,1,2,3,

-- a 4,3,2,2,2,3

matrizLevenshtein :: String -> String -> Array (Int,Int) Int

matrizLevenshtein xs ys = q where

q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]]

m = length xs

n = length ys

f 0 j = j

f i 0 = i

f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1)

| otherwise = 1 + minimum [ q ! (i-1,j)

, q ! (i,j-1)

, q ! (i-1,j-1)]

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> levenshtein1 (show (2^33)) (show (3^33))

-- 12

-- (16.19 secs, 11,766,254,536 bytes)

-- λ> levenshtein2 (show (2^33)) (show (3^33))

-- 12

-- (0.02 secs, 0 bytes)

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "ej1" $

levenshtein1 "casa" "calle" `shouldBe` 3

it "ej2" $

levenshtein1 "calle" "casa" `shouldBe` 3

it "ej3" $

levenshtein1 "casa" "casa" `shouldBe` 0

it "ej4" $

levenshtein1 "ana" "maria" `shouldBe` 3

it "ej5" $

levenshtein1 "agua" "manantial" `shouldBe` 7

it "ej6" $

levenshtein2 "casa" "calle" `shouldBe` 3

it "ej7" $

levenshtein2 "calle" "casa" `shouldBe` 3

it "ej8" $

levenshtein2 "casa" "casa" `shouldBe` 0

it "ej9" $

levenshtein2 "ana" "maria" `shouldBe` 3

it "ej10" $

levenshtein2 "agua" "manantial" `shouldBe` 7

-- La verificación es

-- λ> verifica

-- ej1

-- ej2

-- ej3

-- ej4

-- ej5

-- ej6

-- ej7

-- ej8

-- ej9

-- ej10

-- Finished in 0.0024 seconds

-- 10 examples, 0 failures

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

setrecursionlimit(10**6)

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

def levenshtein1(xs: str, ys: str) -> int:
    if not xs:
        return len(ys)
    if not ys:
        return len(xs)
    if xs[0] == ys[0]:
        return levenshtein1(xs[1:], ys[1:])
    return 1 + min([levenshtein1(xs[1:], ys),
                    levenshtein1(xs, ys[1:]),
                    levenshtein1(xs[1:], ys[1:])])


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

# matrizLevenshtein(xs, ys) es la matriz cuyo número de filas es la
# longitud de xs, cuyo número de columnas es la longitud de ys y en
# valor en la posición (i,j) es la distancia de Levenshtein entre los
# primeros i caracteres de xs y los j primeros caracteres de ys. Por
# ejemplo,
#    >>> matrizLevenshtein("casa", "calle")
#    [[0, 1, 2, 3, 4, 5],
#     [1, 0, 1, 2, 3, 4],
#     [2, 1, 0, 1, 2, 3],
#     [3, 2, 1, 1, 2, 3],
#     [4, 3, 2, 2, 2, 3]]
# Gráficamente,
#       c a l l e
#     0,1,2,3,4,5,
#  c  1,0,1,2,3,4,
#  a  2,1,0,1,2,3,
#  s  3,2,1,1,2,3,
#  a  4,3,2,2,2,3
def matrizLevenshtein(xs: str, ys: str) -> list[list[int]]:
    n = len(xs)
    m = len(ys)
    q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        q[i][0] = i
    for j in range(m + 1):
        q[0][j] = j
    for i in range(1,n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = q[i - 1][j - 1]
            else:
                q[i][j] = 1 + min([q[i-1][j],  q[i][j-1], q[i-1][j-1]])
    return q

def levenshtein2(xs: str, ys: str) -> int:
    m = len(xs)
    n = len(ys)
    return matrizLevenshtein(xs, ys)[m][n]

# 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('levenshtein1(str(2**33), str(3**33))')
#    13.78 segundos
#    >>> tiempo('levenshtein2(str(2**33), str(3**33))')
#    0.00 segundos

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

def test_levenshtein() -> None:
    assert levenshtein1("casa",  "calle")     ==  3
    assert levenshtein1("calle", "casa")      ==  3
    assert levenshtein1("casa",  "casa")      ==  0
    assert levenshtein1("ana",   "maria")     ==  3
    assert levenshtein1("agua",  "manantial") ==  7
    assert levenshtein2("casa",  "calle")     ==  3
    assert levenshtein2("calle", "casa")      ==  3
    assert levenshtein2("casa",  "casa")      ==  0
    assert levenshtein2("ana",   "maria")     ==  3
    assert levenshtein2("agua",  "manantial") ==  7
    print("Verificado")

from sys import setrecursionlimit

from timeit import Timer, default_timer

setrecursionlimit(10**6)

# 1ª definición (por recursión)

# =============================

def levenshtein1(xs: str, ys: str) -> int:

if not xs:

return len(ys)

if not ys:

return len(xs)

if xs[0] == ys[0]:

return levenshtein1(xs[1:], ys[1:])

return 1 + min([levenshtein1(xs[1:], ys),

levenshtein1(xs, ys[1:]),

levenshtein1(xs[1:], ys[1:])])

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

# =========================================

# matrizLevenshtein(xs, ys) es la matriz cuyo número de filas es la

# longitud de xs, cuyo número de columnas es la longitud de ys y en

# valor en la posición (i,j) es la distancia de Levenshtein entre los

# primeros i caracteres de xs y los j primeros caracteres de ys. Por

# ejemplo,

# >>> matrizLevenshtein("casa", "calle")

# [[0, 1, 2, 3, 4, 5],

# [1, 0, 1, 2, 3, 4],

# [2, 1, 0, 1, 2, 3],

# [3, 2, 1, 1, 2, 3],

# [4, 3, 2, 2, 2, 3]]

# Gráficamente,

# c a l l e

# 0,1,2,3,4,5,

# c 1,0,1,2,3,4,

# a 2,1,0,1,2,3,

# s 3,2,1,1,2,3,

# a 4,3,2,2,2,3

def matrizLevenshtein(xs: str, ys: str) -> list[list[int]]:

n = len(xs)

m = len(ys)

q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

for i in range(n + 1):

q[i][0] = i

for j in range(m + 1):

q[0][j] = j

for i in range(1,n + 1):

for j in range(1, m + 1):

if xs[i - 1] == ys[j - 1]:

q[i][j] = q[i - 1][j - 1]

else:

q[i][j] = 1 + min([q[i-1][j], q[i][j-1], q[i-1][j-1]])

return q

def levenshtein2(xs: str, ys: str) -> int:

m = len(xs)

n = len(ys)

return matrizLevenshtein(xs, ys)[m][n]

# 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('levenshtein1(str(2**33), str(3**33))')

# 13.78 segundos

# >>> tiempo('levenshtein2(str(2**33), str(3**33))')

# 0.00 segundos

# Verificación

# ============

def test_levenshtein() -> None:

assert levenshtein1("casa", "calle") == 3

assert levenshtein1("calle", "casa") == 3

assert levenshtein1("casa", "casa") == 0

assert levenshtein1("ana", "maria") == 3

assert levenshtein1("agua", "manantial") == 7

assert levenshtein2("casa", "calle") == 3

assert levenshtein2("calle", "casa") == 3

assert levenshtein2("casa", "casa") == 0

assert levenshtein2("ana", "maria") == 3

assert levenshtein2("agua", "manantial") == 7

print("Verificado")

Programación dinámica

Camino de máxima suma en una matriz

Máxima suma de los caminos en una matriz

Caminos en una matriz (con programación dinámica)

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

La distancia Levenshtein (con programación dinámica)

Entradas recientes

Buscar

Correo electrónico