El mes de septiembre en Exercitium (Ejercicios con Haskell y Python)

Durante el mes de septiembre he publicado en Exercitium las soluciones de los siguientes problemas:

1. Problema de suma cero (mediante espacio de estados)
2. Problema de las jarras (mediante espacios de estados)
3. La función de Fibonacci por programación dinámica
4. Coeficientes binomiales (con programación dinámica)
5. Longitud de la subsecuencia común máxima (con programación dinámica)
6. Subsecuencia común máxima (con programación dinámica)

A continuación se muestran las soluciones.

1. Problema de suma cero (mediante espacio de estados)

El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.

Usando el procedimiento de búsqueda en profundidad, definir la función

   suma0 :: [Int] -> [[Int]]

1	suma0 :: [Int] -> [[Int]]

tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,

   λ> suma0 [-7,-3,-2,5,8]
   [[-3,-2,5]]
   λ> suma0 [-7,-3,-2,5,8,-1]
   [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
   λ> suma0 [-7,-3,1,5,8]
   []

λ> suma0 [-7,-3,-2,5,8]

[[-3,-2,5]]

λ> suma0 [-7,-3,-2,5,8,-1]

[[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]

λ> suma0 [-7,-3,1,5,8]

[]

Soluciones

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

Soluciones en Haskell

module Problema_de_suma_cero where

import BusquedaEnProfundidad (buscaProfundidad)
import Data.List (delete, nub, sort)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- Los estados son ternas formadas por los números seleccionados, su
-- suma y los restantes números.
type Estado = ([Int], Int, [Int])

inicial :: [Int] -> Estado
inicial ns = ([],0,ns)

esFinal :: Estado -> Bool
esFinal (xs,s,_) =
  not (null xs) && s == 0

sucesores :: Estado -> [Estado]
sucesores (xs,s,ns) =
  [(n:xs, n+s, delete n ns) | n <- ns]

soluciones :: [Int] -> [Estado]
soluciones ns =
  buscaProfundidad sucesores esFinal (inicial ns)

suma0 :: [Int] -> [[Int]]
suma0 ns =
  nub [sort xs | (xs,_,_) <- soluciones ns]

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    suma0 [-7,-3,-2,5,8] `shouldBe`
    [[-3,-2,5]]
  it "e2" $
    suma0 [-7,-3,-2,5,8,-1] `shouldBe`
    [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
  it "e3" $
    suma0 [-7,-3,1,5,8] `shouldBe`
    []

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

module Problema_de_suma_cero where

import BusquedaEnProfundidad (buscaProfundidad)

import Data.List (delete, nub, sort)

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

-- Los estados son ternas formadas por los números seleccionados, su

-- suma y los restantes números.

type Estado = ([Int], Int, [Int])

inicial :: [Int] -> Estado

inicial ns = ([],0,ns)

esFinal :: Estado -> Bool

esFinal (xs,s,_) =

not (null xs) && s == 0

sucesores :: Estado -> [Estado]

sucesores (xs,s,ns) =

[(n:xs, n+s, delete n ns) | n <- ns]

soluciones :: [Int] -> [Estado]

soluciones ns =

buscaProfundidad sucesores esFinal (inicial ns)

suma0 :: [Int] -> [[Int]]

suma0 ns =

nub [sort xs | (xs,_,_) <- soluciones ns]

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

suma0 [-7,-3,-2,5,8] `shouldBe`

[[-3,-2,5]]

it "e2" $

suma0 [-7,-3,-2,5,8,-1] `shouldBe`

[[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]

it "e3" $

suma0 [-7,-3,1,5,8] `shouldBe`

[]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0098 seconds

-- 3 examples, 0 failures

Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad

# Los estados son ternas formadas por los números seleccionados, su
# suma y los restantes números.
Estado = tuple[list[int], int, list[int]]

def inicial(ns: list[int]) -> Estado:
    return ([], 0, ns)

def esFinal(e: Estado) -> bool:
    (xs,s,_) = e
    return xs != [] and s == 0

def sucesores(e: Estado) -> list[Estado]:
    (xs, s, ns) = e
    return [([n] + xs, n + s, [m for m in ns if m !=n])
            for n in ns]

def soluciones(ns: list[int]) -> list[Estado]:
    return buscaProfundidad(sucesores, esFinal, inicial(ns))

def suma0(ns: list[int]) -> list[list[int]]:
    xss = [list(sorted(s[0])) for s in soluciones(ns)]
    r = []
    for xs in xss:
        if xs not in r:
            r.append(xs)
    return r

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

def test_suma0() -> None:
    assert suma0([-7,-3,-2,5,8]) == \
        [[-3,-2,5]]
    assert suma0([-7,-3,-2,5,8,-1]) == \
        [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]
    assert not suma0([-7,-3,1,5,8])
    print("Verificado")

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

from src.BusquedaEnProfundidad import buscaProfundidad

# Los estados son ternas formadas por los números seleccionados, su

# suma y los restantes números.

Estado = tuple[list[int], int, list[int]]

def inicial(ns: list[int]) -> Estado:

return ([], 0, ns)

def esFinal(e: Estado) -> bool:

(xs,s,_) = e

return xs != [] and s == 0

def sucesores(e: Estado) -> list[Estado]:

(xs, s, ns) = e

return [([n] + xs, n + s, [m for m in ns if m !=n])

for n in ns]

def soluciones(ns: list[int]) -> list[Estado]:

return buscaProfundidad(sucesores, esFinal, inicial(ns))

def suma0(ns: list[int]) -> list[list[int]]:

xss = [list(sorted(s[0])) for s in soluciones(ns)]

r = []

for xs in xss:

if xs not in r:

r.append(xs)

return r

# Verificación

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

def test_suma0() -> None:

assert suma0([-7,-3,-2,5,8]) == \

[[-3,-2,5]]

assert suma0([-7,-3,-2,5,8,-1]) == \

[[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]

assert not suma0([-7,-3,1,5,8])

print("Verificado")

# La verificación es

# >>> test_suma0()

# Verificado

2. Problema de las jarras (mediante espacios de estados)

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.

Usando el procedimiento de búsqueda en anchura, definir la función

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

1	jarras :: (Int,Int,Int) -> [[(Int,Int)]]

tal jarras (a,b,c) es la lista de las soluciones del problema de las jarras (a,b,c). Por ejemplo,

   λ> take 3 (jarras (4,3,2))
   [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],
    [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

λ> take 3 (jarras (4,3,2))

[[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],

[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],

[(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:

(0,0) se inicia con las dos jarras vacías,
(4,0) se llena la jarra de 4 con el grifo,
(1,3) se llena la de 3 con la de 4,
(1,0) se vacía la de 3,
(0,1) se pasa el contenido de la primera a la segunda,
(4,1) se llena la primera con el grifo,
(2,3) se llena la segunda con la primera.

Otros ejemplos

   λ> length (jarras (15,10,5))
   8
   λ> map length (jarras (15,10,5))
   [3,5,5,7,7,7,8,9]
   λ> jarras (15,10,4)
   []

λ> length (jarras (15,10,5))

λ> map length (jarras (15,10,5))

[3,5,5,7,7,7,8,9]

λ> jarras (15,10,4)

[]

Soluciones

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

Soluciones en Haskell

module Problema_de_las_jarras where

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

-- Un problema es una lista de 3 números enteros (a,b,c) tales que a es
-- la capacidad de la primera jarra, b es la capacidad de la segunda
-- jarra y c es el número de litros que se desea obtener en la primera
-- jarra.
type Problema = (Int,Int,Int)

-- Una configuracion es una lista de dos números. El primero es el
-- contenido de la primera jarra y el segundo el de la segunda.
type Configuracion = (Int,Int)

-- Inicialmente, las dos jarras están vacías.
configuracionInicial :: Configuracion
configuracionInicial = (0,0)

-- (esConfiguracionFinal p e) se verifica si e es un configuracion final
-- del problema p.
esConfiguracionFinal :: Problema -> Configuracion -> Bool
esConfiguracionFinal (_,_,c) (x,_) = x == c

-- (sucesorasConfiguracion p c) son las sucesoras de la configuración c
-- del problema p. Por ejemplo,
--    sucesorasConfiguracion (4,3,2) (0,0)  ==  [(4,0),(0,3)]
--    sucesorasConfiguracion (4,3,2) (4,0)  ==  [(4,3),(0,0),(1,3)]
--    sucesorasConfiguracion (4,3,2) (4,3)  ==  [(0,3),(4,0)]
sucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion]
sucesorasConfiguracion (a,b,_) (x,y) =
    [(a,y) | x < a] ++
    [(x,b) | y < b] ++
    [(0,y) | x > 0] ++
    [(x,0) | y > 0] ++
    [(a,y-(a-x)) | x < a, y > 0, x + y > a] ++
    [(x-(b-y),b) | x > 0, y < b, x + y > b] ++
    [(x+y,0) | y > 0, x + y <= a] ++
    [(0,x+y) | x > 0, x + y <= b]

-- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que
-- c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una
-- sucesora de c_(i-1).
type Estado = [Configuracion]

-- inicial es el estado cuyo único elemento es la configuración
-- inicial.
inicial :: Estado
inicial = [configuracionInicial]

-- (esFinal p e) se verifica si e es un estado final; es decir, su
-- primer elemento es una configuración final.
esFinal :: Problema -> Estado -> Bool
esFinal p (e:_) = esConfiguracionFinal p e

-- (sucesores p e) es la lista de los sucesores del estado e en el
-- problema p. Por ejemplo,
--    λ> sucesores (4,3,2) [(0,0)]
--    [[(4,0),(0,0)],[(0,3),(0,0)]]
--    λ> sucesores (4,3,2) [(4,0),(0,0)]
--    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]
--    λ> sucesores (4,3,2) [(4,3),(4,0),(0,0)]
--    [[(0,3),(4,3),(4,0),(0,0)]]
sucesores :: Problema -> Estado -> [Estado]
sucesores p e@(c:_) =
    [c':e | c' <- sucesorasConfiguracion p c,
            c' `notElem` e]

jarras :: Problema -> [Estado]
jarras p = map reverse soluciones
  where
     soluciones = buscaAnchura (sucesores p) (esFinal p) inicial

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    take 3 (jarras (4,3,2)) `shouldBe`
    [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],
     [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],
     [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]
  it "e2" $
    length (jarras (15,10,5)) `shouldBe` 8
  it "e3" $
    map length (jarras (15,10,5)) `shouldBe`
    [3,5,5,7,7,7,8,9]
  it "e4" $
    jarras (15,10,4) `shouldBe` []

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0080 seconds
--    4 examples, 0 failures

100

101

102

103

104

module Problema_de_las_jarras where

import BusquedaEnAnchura (buscaAnchura)

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

-- Un problema es una lista de 3 números enteros (a,b,c) tales que a es

-- la capacidad de la primera jarra, b es la capacidad de la segunda

-- jarra y c es el número de litros que se desea obtener en la primera

-- jarra.

type Problema = (Int,Int,Int)

-- Una configuracion es una lista de dos números. El primero es el

-- contenido de la primera jarra y el segundo el de la segunda.

type Configuracion = (Int,Int)

-- Inicialmente, las dos jarras están vacías.

configuracionInicial :: Configuracion

configuracionInicial = (0,0)

-- (esConfiguracionFinal p e) se verifica si e es un configuracion final

-- del problema p.

esConfiguracionFinal :: Problema -> Configuracion -> Bool

esConfiguracionFinal (_,_,c) (x,_) = x == c

-- (sucesorasConfiguracion p c) son las sucesoras de la configuración c

-- del problema p. Por ejemplo,

-- sucesorasConfiguracion (4,3,2) (0,0) == [(4,0),(0,3)]

-- sucesorasConfiguracion (4,3,2) (4,0) == [(4,3),(0,0),(1,3)]

-- sucesorasConfiguracion (4,3,2) (4,3) == [(0,3),(4,0)]

sucesorasConfiguracion :: Problema -> Configuracion -> [Configuracion]

sucesorasConfiguracion (a,b,_) (x,y) =

[(a,y) | x < a] ++

[(x,b) | y < b] ++

[(0,y) | x > 0] ++

[(x,0) | y > 0] ++

[(a,y-(a-x)) | x < a, y > 0, x + y > a] ++

[(x-(b-y),b) | x > 0, y < b, x + y > b] ++

[(x+y,0) | y > 0, x + y <= a] ++

[(0,x+y) | x > 0, x + y <= b]

-- Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que

-- c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una

-- sucesora de c_(i-1).

type Estado = [Configuracion]

-- inicial es el estado cuyo único elemento es la configuración

-- inicial.

inicial :: Estado

inicial = [configuracionInicial]

-- (esFinal p e) se verifica si e es un estado final; es decir, su

-- primer elemento es una configuración final.

esFinal :: Problema -> Estado -> Bool

esFinal p (e:_) = esConfiguracionFinal p e

-- (sucesores p e) es la lista de los sucesores del estado e en el

-- problema p. Por ejemplo,

-- λ> sucesores (4,3,2) [(0,0)]

-- [[(4,0),(0,0)],[(0,3),(0,0)]]

-- λ> sucesores (4,3,2) [(4,0),(0,0)]

-- [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]

-- λ> sucesores (4,3,2) [(4,3),(4,0),(0,0)]

-- [[(0,3),(4,3),(4,0),(0,0)]]

sucesores :: Problema -> Estado -> [Estado]

sucesores p e@(c:_) =

[c':e | c' <- sucesorasConfiguracion p c,

c' `notElem` e]

jarras :: Problema -> [Estado]

jarras p = map reverse soluciones

where

soluciones = buscaAnchura (sucesores p) (esFinal p) inicial

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

take 3 (jarras (4,3,2)) `shouldBe`

[[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)],

[(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)],

[(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]]

it "e2" $

length (jarras (15,10,5)) `shouldBe` 8

it "e3" $

map length (jarras (15,10,5)) `shouldBe`

[3,5,5,7,7,7,8,9]

it "e4" $

jarras (15,10,4) `shouldBe` []

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0080 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.BusquedaEnAnchura import buscaAnchura

# Un problema es una lista de 3 números enteros (a,b,c) tales que a es
# la capacidad de la primera jarra, b es la capacidad de la segunda
# jarra y c es el número de litros que se desea obtener en la primera
# jarra.
Problema = tuple[int, int, int]

# Una configuracion es una lista de dos números. El primero es el
# contenido de la primera jarra y el segundo el de la segunda.
Configuracion = tuple[int, int]

# Inicialmente, las dos jarras están vacías.
configuracionInicial: Configuracion = (0,0)

# esConfiguracionFinal(p, e) se verifica si e es un configuracion final
# del problema p.
def esConfiguracionFinal(p: Problema, c: Configuracion) -> bool:
    return p[2] == c[0]

# sucesorasConfiguracion(p, c) son las sucesoras de la configuración c
# del problema p. Por ejemplo,
#    sucesorasConfiguracion((4,3,2), (0,0))  ==  [(4,0),(0,3)]
#    sucesorasConfiguracion((4,3,2), (4,0))  ==  [(4,3),(0,0),(1,3)]
#    sucesorasConfiguracion((4,3,2), (4,3))  ==  [(0,3),(4,0)]
def sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]:
    (a, b, _) = p
    (x, y) = c
    r = []
    if x < a:
        r.append((a, y))
    if y < b:
        r.append((x, b))
    if x > 0:
        r.append((0, y))
    if y > 0:
        r.append((x, 0))
    if x < a and y > 0 and x + y > a:
        r.append((a, y - (a - x)))
    if x > 0 and y < b and x + y > b:
        r.append((x - (b - y), b))
    if y > 0 and x + y <= a:
        r.append((x + y, 0))
    if x > 0 and x + y <= b:
        r.append((0, x + y))
    return r

# Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que
# c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una
# sucesora de c_(i-1).
Estado = list[Configuracion]

# inicial es el estado cuyo único elemento es la configuración
# inicial.
inicial: Estado = [configuracionInicial]

# esFinal(p, e) se verifica si e es un estado final; es decir, su
# primer elemento es una configuración final.
def esFinal(p: Problema, e: Estado) -> bool:
    return esConfiguracionFinal(p, e[0])

# sucesores(p, e) es la lista de los sucesores del estado e en el
# problema p. Por ejemplo,
#    λ> sucesores((4,3,2), [(0,0)])
#    [[(4,0),(0,0)],[(0,3),(0,0)]]
#    λ> sucesores((4,3,2), [(4,0),(0,0)])
#    [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]
#    λ> sucesores((4,3,2), [(4,3),(4,0),(0,0)])
#    [[(0,3),(4,3),(4,0),(0,0)]]
def sucesores(p: Problema, e: Estado) -> list[Estado]:
    return [[c] + e
            for c in sucesorasConfiguracion(p, e[0])
            if c not in e]

def jarras(p: Problema) -> list[Estado]:
    soluciones = buscaAnchura(lambda e: sucesores(p, e),
                              lambda e: esFinal(p, e),
                              inicial)
    return [list(reversed(e)) for e in soluciones]

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

def test_jarras() -> None:
    assert jarras((4,3,2))[:3] == \
        [[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)],
         [(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)],
         [(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]]
    assert len(jarras((15,10,5))) == 8
    assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9]
    assert jarras((15,10,4)) == []
    print("Verificado")

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

from src.BusquedaEnAnchura import buscaAnchura

# Un problema es una lista de 3 números enteros (a,b,c) tales que a es

# la capacidad de la primera jarra, b es la capacidad de la segunda

# jarra y c es el número de litros que se desea obtener en la primera

# jarra.

Problema = tuple[int, int, int]

# Una configuracion es una lista de dos números. El primero es el

# contenido de la primera jarra y el segundo el de la segunda.

Configuracion = tuple[int, int]

# Inicialmente, las dos jarras están vacías.

configuracionInicial: Configuracion = (0,0)

# esConfiguracionFinal(p, e) se verifica si e es un configuracion final

# del problema p.

def esConfiguracionFinal(p: Problema, c: Configuracion) -> bool:

return p[2] == c[0]

# sucesorasConfiguracion(p, c) son las sucesoras de la configuración c

# del problema p. Por ejemplo,

# sucesorasConfiguracion((4,3,2), (0,0)) == [(4,0),(0,3)]

# sucesorasConfiguracion((4,3,2), (4,0)) == [(4,3),(0,0),(1,3)]

# sucesorasConfiguracion((4,3,2), (4,3)) == [(0,3),(4,0)]

def sucesorasConfiguracion(p: Problema, c: Configuracion) -> list[Configuracion]:

(a, b, _) = p

(x, y) = c

r = []

if x < a:

r.append((a, y))

if y < b:

r.append((x, b))

if x > 0:

r.append((0, y))

if y > 0:

r.append((x, 0))

if x < a and y > 0 and x + y > a:

r.append((a, y - (a - x)))

if x > 0 and y < b and x + y > b:

r.append((x - (b - y), b))

if y > 0 and x + y <= a:

r.append((x + y, 0))

if x > 0 and x + y <= b:

r.append((0, x + y))

return r

# Los estados son listas de configuraciones [c_n,...c_2,c_1] tales que

# c_1 es la configuración inicial y, para 2 <= i <= n, c_i es una

# sucesora de c_(i-1).

Estado = list[Configuracion]

# inicial es el estado cuyo único elemento es la configuración

# inicial.

inicial: Estado = [configuracionInicial]

# esFinal(p, e) se verifica si e es un estado final; es decir, su

# primer elemento es una configuración final.

def esFinal(p: Problema, e: Estado) -> bool:

return esConfiguracionFinal(p, e[0])

# sucesores(p, e) es la lista de los sucesores del estado e en el

# problema p. Por ejemplo,

# λ> sucesores((4,3,2), [(0,0)])

# [[(4,0),(0,0)],[(0,3),(0,0)]]

# λ> sucesores((4,3,2), [(4,0),(0,0)])

# [[(4,3),(4,0),(0,0)],[(1,3),(4,0),(0,0)]]

# λ> sucesores((4,3,2), [(4,3),(4,0),(0,0)])

# [[(0,3),(4,3),(4,0),(0,0)]]

def sucesores(p: Problema, e: Estado) -> list[Estado]:

return [[c] + e

for c in sucesorasConfiguracion(p, e[0])

if c not in e]

def jarras(p: Problema) -> list[Estado]:

soluciones = buscaAnchura(lambda e: sucesores(p, e),

lambda e: esFinal(p, e),

inicial)

return [list(reversed(e)) for e in soluciones]

# Verificación

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

def test_jarras() -> None:

assert jarras((4,3,2))[:3] == \

[[(0, 0), (4, 0), (1, 3), (1, 0), (0, 1), (4, 1), (2, 3)],

[(0, 0), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)],

[(0, 0), (4, 0), (4, 3), (0, 3), (3, 0), (3, 3), (4, 2), (0, 2), (2, 0)]]

assert len(jarras((15,10,5))) == 8

assert [len(e) for e in jarras((15,10,5))] == [3, 5, 5, 7, 7, 7, 8, 9]

assert jarras((15,10,4)) == []

print("Verificado")

# La verificación es

# >>> test_jarras()

# Verificado

3. La función de Fibonacci por programación dinámica

Los primeros términos de la sucesión de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

1	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función

   fib :: Integer -> Integer

1	fib :: Integer -> Integer

tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

   fib 6 == 8

1	fib 6 == 8

Comparar la eficiencia de las dos definiciones.

Soluciones

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

Soluciones en Haskell

module La_funcion_de_Fibonacci_por_programacion_dinamica where

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

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

fib1 :: Integer -> Integer
fib1 0 = 0
fib1 1 = 1
fib1 n = fib1 (n-1) + fib1 (n-2)

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

fib2 :: Integer -> Integer
fib2 n = vectorFib2 n ! n

-- (vectorFib2 n) es el vector con índices de 0 a n tal que el valor
-- de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
--    λ> vectorFib2 7
--    array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)]
vectorFib2 :: Integer -> Array Integer Integer
vectorFib2 n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 0
  f 1 = 1
  f m = v!(m-1) + v!(m-2)

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

-- La comparación es
--    λ> fib1 34
--    5702887
--    (11.82 secs, 3,504,944,704 bytes)
--    λ> fib2 34
--    5702887
--    (0.01 secs, 587,808 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    fib1 6 `shouldBe` 8
  it "e2" $
    fib2 6 `shouldBe` 8
  it "e3" $
    map fib1 [0..9] `shouldBe` map fib2 [0..9]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0007 seconds
--    3 examples, 0 failures
--    (0.01 secs, 788,952 bytes)

module La_funcion_de_Fibonacci_por_programacion_dinamica where

import Data.Array

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

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

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

fib1 :: Integer -> Integer

fib1 0 = 0

fib1 1 = 1

fib1 n = fib1 (n-1) + fib1 (n-2)

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

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

fib2 :: Integer -> Integer

fib2 n = vectorFib2 n ! n

-- (vectorFib2 n) es el vector con índices de 0 a n tal que el valor

-- de la posición i es el i-ésimo número de Finonacci. Por ejemplo,

-- λ> vectorFib2 7

-- array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)]

vectorFib2 :: Integer -> Array Integer Integer

vectorFib2 n = v where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 0

f 1 = 1

f m = v!(m-1) + v!(m-2)

-- Comparación de eficiencia

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

-- La comparación es

-- λ> fib1 34

-- 5702887

-- (11.82 secs, 3,504,944,704 bytes)

-- λ> fib2 34

-- 5702887

-- (0.01 secs, 587,808 bytes)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

fib1 6 `shouldBe` 8

it "e2" $

fib2 6 `shouldBe` 8

it "e3" $

map fib1 [0..9] `shouldBe` map fib2 [0..9]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0007 seconds

-- 3 examples, 0 failures

-- (0.01 secs, 788,952 bytes)

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

import numpy as np
import numpy.typing as npt

setrecursionlimit(10**6)

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

def fib1(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib1(n - 1) + fib1(n - 2)

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

def fib2(n: int) -> int:
    return vectorFib2(n)[n]

# (vectorFib2 n) es el vector con índices de 0 a n tal que el valor
# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
#    >>> vectorFib2(7)
#    [0, 1, 1, 2, 3, 5, 8, 13]
def vectorFib2(n: int) -> list[int]:
    v = [0] * (n + 1)
    v[0] = 0
    v[1] = 1
    for i in range(2, n + 1):
        v[i] = v[i - 1] + v[i - 2]
    return v

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

def fib3(n: int) -> int:
    return vectorFib3(n)[n]

# (vectorFib3 n) es el vector con índices de 0 a n tal que el valor
# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,
#    >>> vectorFib3(7)
#    array([ 0,  1,  1,  2,  3,  5,  8, 13])
def vectorFib3(n: int) -> npt.NDArray[np.complex64]:
    v = np.zeros(n + 1, dtype=int)
    v[0] = 0
    v[1] = 1
    for i in range(2, n + 1):
        v[i] = v[i - 1] + v[i - 2]
    return v

# 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('fib1(34)')
#    2.10 segundos
#    >>> tiempo('fib2(34)')
#    0.00 segundos
#    >>> tiempo('fib3(34)')
#    0.00 segundos
#
#    >>> tiempo('fib2(100000)')
#    0.37 segundos
#    >>> tiempo('fib3(100000)')
#    0.08 segundos

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

def test_fib() -> None:
    assert fib1(6) == 8
    assert fib2(6) == 8
    assert fib3(6) == 8
    print("Verificado")

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

from sys import setrecursionlimit

from timeit import Timer, default_timer

import numpy as np

import numpy.typing as npt

setrecursionlimit(10**6)

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

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

def fib1(n: int) -> int:

if n == 0:

return 0

if n == 1:

return 1

return fib1(n - 1) + fib1(n - 2)

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

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

def fib2(n: int) -> int:

return vectorFib2(n)[n]

# (vectorFib2 n) es el vector con índices de 0 a n tal que el valor

# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,

# >>> vectorFib2(7)

# [0, 1, 1, 2, 3, 5, 8, 13]

def vectorFib2(n: int) -> list[int]:

v = [0] * (n + 1)

v[0] = 0

v[1] = 1

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

v[i] = v[i - 1] + v[i - 2]

return v

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

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

def fib3(n: int) -> int:

return vectorFib3(n)[n]

# (vectorFib3 n) es el vector con índices de 0 a n tal que el valor

# de la posición i es el i-ésimo número de Finonacci. Por ejemplo,

# >>> vectorFib3(7)

# array([ 0, 1, 1, 2, 3, 5, 8, 13])

def vectorFib3(n: int) -> npt.NDArray[np.complex64]:

v = np.zeros(n + 1, dtype=int)

v[0] = 0

v[1] = 1

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

v[i] = v[i - 1] + v[i - 2]

return v

# 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('fib1(34)')

# 2.10 segundos

# >>> tiempo('fib2(34)')

# 0.00 segundos

# >>> tiempo('fib3(34)')

# 0.00 segundos

# >>> tiempo('fib2(100000)')

# 0.37 segundos

# >>> tiempo('fib3(100000)')

# 0.08 segundos

# Verificación

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

def test_fib() -> None:

assert fib1(6) == 8

assert fib2(6) == 8

assert fib3(6) == 8

print("Verificado")

# La verificación es

# >>> test_fib()

# Verificado

4. Coeficientes binomiales (con programación dinámica)

El coeficiente binomial n sobre k es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Definir la función

   binomial :: Integer -> Integer -> Integer

1	binomial :: Integer -> Integer -> Integer

tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,

   binomial 6 3 == 20
   binomial 5 2 == 10
   binomial 5 3 == 10

binomial 6 3 == 20

binomial 5 2 == 10

binomial 5 3 == 10

Soluciones

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

Soluciones en Haskell

module Coeficientes_binomiales where

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

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

binomial1 :: Integer -> Integer -> Integer
binomial1 _ 0 = 1
binomial1 n k
  | n == k    = 1
  | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k

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

binomial2 :: Integer -> Integer -> Integer
binomial2 n k = matrizBinomial2 n k ! (n,k)

-- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el
-- valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
-- sobre j. Por ejemplo,
--    λ> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]]
--    [[1],[1,1],[1,2,1],[1,3,3,1]]
matrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer
matrizBinomial2 n k = q where
  q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]]
  f _ 0 = 1
  f i j
    | i == j    = 1
    | otherwise = q!(i-1,j-1) + q!(i-1,j)

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

-- La comparación es
--    λ> binomial1 25 12
--    5200300
--    (6.45 secs, 2,654,797,776 bytes)
--    λ> binomial2 25 12
--    5200300
--    (0.00 secs, 826,272 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    binomial1 6 3 `shouldBe` 20
  it "e2" $
    binomial1 5 2 `shouldBe` 10
  it "e3" $
    binomial1 5 3 `shouldBe` 10
  it "e4" $
    binomial2 6 3 `shouldBe` 20
  it "e5" $
    binomial2 5 2 `shouldBe` 10
  it "e6" $
    binomial2 5 3 `shouldBe` 10

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0006 seconds
--    6 examples, 0 failures

module Coeficientes_binomiales where

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

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

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

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

binomial1 :: Integer -> Integer -> Integer

binomial1 _ 0 = 1

binomial1 n k

| n == k = 1

| otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k

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

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

binomial2 :: Integer -> Integer -> Integer

binomial2 n k = matrizBinomial2 n k ! (n,k)

-- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el

-- valor en la posición (i,j) (con j <= i) es el coeficiente binomial i

-- sobre j. Por ejemplo,

-- λ> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]]

-- [[1],[1,1],[1,2,1],[1,3,3,1]]

matrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer

matrizBinomial2 n k = q where

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

f _ 0 = 1

f i j

| i == j = 1

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

-- Comparación de eficiencia

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

-- La comparación es

-- λ> binomial1 25 12

-- 5200300

-- (6.45 secs, 2,654,797,776 bytes)

-- λ> binomial2 25 12

-- 5200300

-- (0.00 secs, 826,272 bytes)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

binomial1 6 3 `shouldBe` 20

it "e2" $

binomial1 5 2 `shouldBe` 10

it "e3" $

binomial1 5 3 `shouldBe` 10

it "e4" $

binomial2 6 3 `shouldBe` 20

it "e5" $

binomial2 5 2 `shouldBe` 10

it "e6" $

binomial2 5 3 `shouldBe` 10

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0006 seconds

-- 6 examples, 0 failures

Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer

import numpy as np
import numpy.typing as npt

setrecursionlimit(10**6)

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

def binomial1(n: int, k: int) -> int:
    if k == 0:
        return 1
    if n == k:
        return 1
    return binomial1(n-1, k-1) + binomial1(n-1, k)

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

def binomial2(n: int, k: int) -> int:
    return matrizBinomial2(n, k)[n][k]

# (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el
# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
# sobre j. Por ejemplo,
#    >>> matrizBinomial2(3, 3)
#    [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]]
def matrizBinomial2(n: int, k: int) -> list[list[int]]:
    q = [[0 for i in range(k + 1)] for j in range(n + 1)]

    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0:
                q[i][j] = 1
            elif i == j:
                q[i][j] = 1
            else:
                q[i][j] = q[i - 1][j - 1] + q[i - 1][j]

    return q

# 3ª definición (con programación dinámica y numpy)
# ================================================

def binomial3(n: int, k: int) -> int:
    return matrizBinomial3(n, k)[n][k]

# (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el
# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i
# sobre j. Por ejemplo,
#    >>> matrizBinomial3(3, 3)
#    array([[1, 0, 0, 0],
#           [1, 1, 0, 0],
#           [1, 2, 1, 0],
#           [1, 3, 3, 1]])
def matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]:
    q = np.zeros((n + 1, k + 1), dtype=object)

    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0:
                q[i, j] = 1
            elif i == j:
                q[i, j] = 1
            else:
                q[i, j] = q[i - 1, j - 1] + q[i - 1, j]

    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('binomial1(27, 12)')
#    4.26 segundos
#    >>> tiempo('binomial2(27, 12)')
#    0.00 segundos
#    >>> tiempo('binomial3(27, 12)')
#    0.00 segundos
#
# >>> tiempo('binomial2(50000, 12)')
# 0.18 segundos
# >>> tiempo('binomial3(50000, 12)')
# 0.26 segundos

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

def test_binomial() -> None:
    assert binomial1(6, 3) == 20
    assert binomial1(5, 2) == 10
    assert binomial1(5, 3) == 10
    assert binomial2(6, 3) == 20
    assert binomial2(5, 2) == 10
    assert binomial2(5, 3) == 10
    assert binomial3(6, 3) == 20
    assert binomial3(5, 2) == 10
    assert binomial3(5, 3) == 10
    print("Verificado")

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

100

101

102

103

104

105

106

107

108

109

110

from sys import setrecursionlimit

from timeit import Timer, default_timer

import numpy as np

import numpy.typing as npt

setrecursionlimit(10**6)

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

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

def binomial1(n: int, k: int) -> int:

if k == 0:

return 1

if n == k:

return 1

return binomial1(n-1, k-1) + binomial1(n-1, k)

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

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

def binomial2(n: int, k: int) -> int:

return matrizBinomial2(n, k)[n][k]

# (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el

# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i

# sobre j. Por ejemplo,

# >>> matrizBinomial2(3, 3)

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

def matrizBinomial2(n: int, k: int) -> list[list[int]]:

q = [[0 for i in range(k + 1)] for j in range(n + 1)]

for i in range(n + 1):

for j in range(min(i, k) + 1):

if j == 0:

q[i][j] = 1

elif i == j:

q[i][j] = 1

else:

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

return q

# 3ª definición (con programación dinámica y numpy)

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

def binomial3(n: int, k: int) -> int:

return matrizBinomial3(n, k)[n][k]

# (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el

# valor en la posición (i,j) (con j <= i) es el coeficiente binomial i

# sobre j. Por ejemplo,

# >>> matrizBinomial3(3, 3)

# array([[1, 0, 0, 0],

# [1, 1, 0, 0],

# [1, 2, 1, 0],

# [1, 3, 3, 1]])

def matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]:

q = np.zeros((n + 1, k + 1), dtype=object)

for i in range(n + 1):

for j in range(min(i, k) + 1):

if j == 0:

q[i, j] = 1

elif i == j:

q[i, j] = 1

else:

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

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('binomial1(27, 12)')

# 4.26 segundos

# >>> tiempo('binomial2(27, 12)')

# 0.00 segundos

# >>> tiempo('binomial3(27, 12)')

# 0.00 segundos

# >>> tiempo('binomial2(50000, 12)')

# 0.18 segundos

# >>> tiempo('binomial3(50000, 12)')

# 0.26 segundos

# Verificación

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

def test_binomial() -> None:

assert binomial1(6, 3) == 20

assert binomial1(5, 2) == 10

assert binomial1(5, 3) == 10

assert binomial2(6, 3) == 20

assert binomial2(5, 2) == 10

assert binomial2(5, 3) == 10

assert binomial3(6, 3) == 20

assert binomial3(5, 2) == 10

assert binomial3(5, 3) == 10

print("Verificado")

# La verificación es

# >>> test_binomial()

# Verificado

5. Longitud de la subsecuencia común máxima (con programación dinámica)

Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, “aaoa” es una subsecuencia de la secuencia “amapola”.

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = “amapola” e Y = “matamoscas”, la secuencia “aaoa” es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 “maoa” o “amoa”.

Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.

Definir la función

   longitudSCM :: Eq a => [a] -> [a] -> Int

1	longitudSCM :: Eq a => [a] -> [a] -> Int

tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,

   longitudSCM "amapola" "matamoscas" == 4
   longitudSCM "atamos" "matamoscas"  == 6
   longitudSCM "aaa" "bbbb"           == 0

longitudSCM "amapola" "matamoscas" == 4

longitudSCM "atamos" "matamoscas" == 6

longitudSCM "aaa" "bbbb" == 0

Soluciones

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

Soluciones en Haskell

module Longitud_SCM where

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

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

longitudSCM1 :: Eq a => [a] -> [a] -> Int
longitudSCM1 [] _ = 0
longitudSCM1 _ [] = 0
longitudSCM1 (x:xs) (y:ys)
  | x == y    = 1 + longitudSCM1 xs ys
  | otherwise = max (longitudSCM1 (x:xs) ys) (longitudSCM1 xs (y:ys))

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

longitudSCM2 :: Eq a => [a] -> [a] -> Int
longitudSCM2 xs ys = matrizLongitudSCM2 xs ys ! (n,m)
  where n = length xs
        m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es la longitud de la SCM de los i
-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizLongitudSCM2 "amapola" "matamoscas")
--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,
--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,
--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]
-- Gráficamente,
--       m a t a m o s c a s
--    [0,0,0,0,0,0,0,0,0,0,0,
-- a   0,0,1,1,1,1,1,1,1,1,1,
-- m   0,1,1,1,1,2,2,2,2,2,2,
-- a   0,1,2,2,2,2,2,2,2,3,3,
-- p   0,1,2,2,2,2,2,2,2,3,3,
-- o   0,1,2,2,2,2,3,3,3,3,3,
-- l   0,1,2,2,2,2,3,3,3,3,3,
-- a   0,1,2,2,3,3,3,3,3,4,4]
matrizLongitudSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) Int
matrizLongitudSCM2 xs ys = q
  where
    n = length xs
    m = length ys
    v = listArray (1,n) xs
    w = listArray (1,m) ys
    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
      where f 0 _ = 0
            f _ 0 = 0
            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)
                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))

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

-- La comparación es
--    λ> longitudSCM1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))
--    9
--    (13.90 secs, 8,883,660,048 bytes)
--    λ> longitudSCM2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))
--    9
--    (0.01 secs, 953,880 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    longitudSCM1 "amapola" "matamoscas" `shouldBe` 4
  it "e2" $
    longitudSCM1 "atamos" "matamoscas"  `shouldBe` 6
  it "e3" $
    longitudSCM1 "aaa" "bbbb"           `shouldBe` 0
  it "e4" $
    longitudSCM2 "amapola" "matamoscas" `shouldBe` 4
  it "e5" $
    longitudSCM2 "atamos" "matamoscas"  `shouldBe` 6
  it "e6" $
    longitudSCM2 "aaa" "bbbb"           `shouldBe` 0

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0025 seconds
--    6 examples, 0 failures

module Longitud_SCM where

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

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

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

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

longitudSCM1 :: Eq a => [a] -> [a] -> Int

longitudSCM1 [] _ = 0

longitudSCM1 _ [] = 0

longitudSCM1 (x:xs) (y:ys)

| x == y = 1 + longitudSCM1 xs ys

| otherwise = max (longitudSCM1 (x:xs) ys) (longitudSCM1 xs (y:ys))

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

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

longitudSCM2 :: Eq a => [a] -> [a] -> Int

longitudSCM2 xs ys = matrizLongitudSCM2 xs ys ! (n,m)

where n = length xs

m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n

-- y m son los números de elementos de xs e ys, respectivamente) tal que

-- el valor en la posición (i,j) es la longitud de la SCM de los i

-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,

-- λ> elems (matrizLongitudSCM2 "amapola" "matamoscas")

-- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,

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

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

-- Gráficamente,

-- m a t a m o s c a s

-- [0,0,0,0,0,0,0,0,0,0,0,

-- a 0,0,1,1,1,1,1,1,1,1,1,

-- m 0,1,1,1,1,2,2,2,2,2,2,

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

-- p 0,1,2,2,2,2,2,2,2,3,3,

-- o 0,1,2,2,2,2,3,3,3,3,3,

-- l 0,1,2,2,2,2,3,3,3,3,3,

-- a 0,1,2,2,3,3,3,3,3,4,4]

matrizLongitudSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) Int

matrizLongitudSCM2 xs ys = q

where

n = length xs

m = length ys

v = listArray (1,n) xs

w = listArray (1,m) ys

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

where f 0 _ = 0

f _ 0 = 0

f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)

| otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

-- Comparación de eficiencia

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

-- La comparación es

-- λ> longitudSCM1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))

-- 9

-- (13.90 secs, 8,883,660,048 bytes)

-- λ> longitudSCM2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3]))

-- 9

-- (0.01 secs, 953,880 bytes)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

longitudSCM1 "amapola" "matamoscas" `shouldBe` 4

it "e2" $

longitudSCM1 "atamos" "matamoscas" `shouldBe` 6

it "e3" $

longitudSCM1 "aaa" "bbbb" `shouldBe` 0

it "e4" $

longitudSCM2 "amapola" "matamoscas" `shouldBe` 4

it "e5" $

longitudSCM2 "atamos" "matamoscas" `shouldBe` 6

it "e6" $

longitudSCM2 "aaa" "bbbb" `shouldBe` 0

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0025 seconds

-- 6 examples, 0 failures

Soluciones en Python

from timeit import Timer, default_timer

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

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

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

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

# matrizLongitudSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n
# y m son los números de elementos de xs e ys, respectivamente) tal que
# el valor en la posición (i,j) es la longitud de la SCM de los i
# primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
#    >>> matrizLongitudSCM2("amapola", "matamoscas")
#    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#     [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2],
#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],
#     [0, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3],
#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],
#     [0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3],
#     [0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4]]
#    # Gráficamente,
#       m a t a m o s c a s
#    [0,0,0,0,0,0,0,0,0,0,0,
# a   0,0,1,1,1,1,1,1,1,1,1,
# m   0,1,1,1,1,2,2,2,2,2,2,
# a   0,1,2,2,2,2,2,2,2,3,3,
# p   0,1,2,2,2,2,2,2,2,3,3,
# o   0,1,2,2,2,2,3,3,3,3,3,
# l   0,1,2,2,2,2,3,3,3,3,3,
# a   0,1,2,2,3,3,3,3,3,4,4]
def matrizLongitudSCM2(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(1, n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = 1 + q[i - 1][j - 1]
            else:
                q[i][j] = max(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('longitudSCM1([1,3]*9, [2,3]*9)')
#    8.04 segundos
#    >>> tiempo('longitudSCM2([1,3]*9, [2,3]*9)')
#    0.00 segundos

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

def test_longitudSCM() -> None:
    assert longitudSCM1("amapola", "matamoscas") == 4
    assert longitudSCM1("atamos", "matamoscas")  == 6
    assert longitudSCM1("aaa", "bbbb")           == 0
    assert longitudSCM2("amapola", "matamoscas") == 4
    assert longitudSCM2("atamos", "matamoscas")  == 6
    assert longitudSCM2("aaa", "bbbb")           == 0
    print("Verificado")

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

from timeit import Timer, default_timer

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

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

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

if not xs:

return 0

if not ys:

return 0

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

return 1 + longitudSCM1(xs[1:], ys[1:])

return max(longitudSCM1(xs, ys[1:]), longitudSCM1(xs[1:], ys))

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

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

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

n = len(xs)

m = len(ys)

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

# matrizLongitudSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n

# y m son los números de elementos de xs e ys, respectivamente) tal que

# el valor en la posición (i,j) es la longitud de la SCM de los i

# primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,

# >>> matrizLongitudSCM2("amapola", "matamoscas")

# [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

# [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],

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

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

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

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

# # Gráficamente,

# m a t a m o s c a s

# [0,0,0,0,0,0,0,0,0,0,0,

# a 0,0,1,1,1,1,1,1,1,1,1,

# m 0,1,1,1,1,2,2,2,2,2,2,

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

# p 0,1,2,2,2,2,2,2,2,3,3,

# o 0,1,2,2,2,2,3,3,3,3,3,

# l 0,1,2,2,2,2,3,3,3,3,3,

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

def matrizLongitudSCM2(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(1, n + 1):

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

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

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

else:

q[i][j] = max(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('longitudSCM1([1,3]*9, [2,3]*9)')

# 8.04 segundos

# >>> tiempo('longitudSCM2([1,3]*9, [2,3]*9)')

# 0.00 segundos

# Verificación

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

def test_longitudSCM() -> None:

assert longitudSCM1("amapola", "matamoscas") == 4

assert longitudSCM1("atamos", "matamoscas") == 6

assert longitudSCM1("aaa", "bbbb") == 0

assert longitudSCM2("amapola", "matamoscas") == 4

assert longitudSCM2("atamos", "matamoscas") == 6

assert longitudSCM2("aaa", "bbbb") == 0

print("Verificado")

# La verificación es

# >>> test_longitudSCM()

# Verificado

6. Subsecuencia común máxima (con programación dinámica)

Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, “aaoa” es una subsecuencia de la secuencia “amapola”.

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = “amapola” e Y = “matamoscas”, la secuencia “aaoa” es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 “maoa” o “amoa”.

Definir la función

   scm :: Eq a => [a] -> [a] -> [a]

1	scm :: Eq a => [a] -> [a] -> [a]

tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,

   scm "amapola" "matamoscas" == "amoa"
   scm "atamos" "matamoscas"  == "atamos"
   scm "aaa" "bbbb"           == ""

scm "amapola" "matamoscas" == "amoa"

scm "atamos" "matamoscas" == "atamos"

scm "aaa" "bbbb" == ""

Soluciones

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

Soluciones en Haskell

module Subsecuencia_comun_maxima where

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

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

scm1 :: Eq a => [a] -> [a] -> [a]
scm1 [] _ = []
scm1 _ [] = []
scm1 (x:xs) (y:ys)
  | x == y    = x : scm1 xs ys
  | otherwise = mayor (scm1 (x:xs) ys) (scm1 xs (y:ys))

-- (mayor xs ys) es la cadena más larga de xs e ys.
--    mayor "hola" "buenas"  ==  "buenas"
--    mayor "hola" "pera"    ==  "hola"
mayor :: [a] -> [a] -> [a]
mayor xs ys
  | length xs >= length ys = xs
  | otherwise              = ys

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

scm2 :: Eq a => [a] -> [a] -> [a]
scm2 xs ys = reverse (matrizSCM2 xs ys ! (n,m))
  where n = length xs
        m = length ys

-- (matrizSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es una SCM de los i primeros
-- elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizSCM2 "amapola" "matamoscas")
--    ["","","","","","","","","","","","","","a","a","a","a","a","a",
--     "a","a","a","","m","a","a","a","ma","ma","ma","ma","ma","ma","",
--     "m","am","am","aa","ma","ma","ma","ma","ama","ama","","m","am",
--     "am","aa","ma","ma","ma","ma","ama","ama","","m","am","am","aa",
--     "ma","oma","oma","oma","ama","ama","","m","am","am","aa","ma",
--     "oma","oma","oma","ama","ama","","m","am","am","aam","aam","oma",
--     "oma","oma","aoma","aoma"]
-- Gráficamente,
--        m   a    t    a     m     o     s     c     a      s
--    ["","" ,""  ,""  ,""   ,""   ,""   ,""   ,""   ,""    ,"",
-- a   "","" ,"a" ,"a" ,"a"  ,"a"  ,"a"  ,"a"  ,"a"  ,"a"   ,"a",
-- m   "","m","a" ,"a" ,"a"  ,"ma" ,"ma" ,"ma" ,"ma" ,"ma"  ,"ma",
-- a   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
-- p   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
-- o   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
-- l   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
-- a   "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]
matrizSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) [a]
matrizSCM2 xs ys = q where
  q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
  n = length xs
  m = length ys
  v = listArray (1,n) xs
  w = listArray (1,m) ys
  f 0 _ = []
  f _ 0 = []
  f i j | v ! i == w ! j = (v!i) : (q ! (i-1,j-1))
        | otherwise      = mayor (q ! (i-1,j)) (q ! (i,j-1))

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

-- La comparación es
--    λ> length (scm1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))
--    9
--    (20.17 secs, 11,436,759,992 bytes)
--    λ> length (scm2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))
--    9
--    (0.00 secs, 1,013,624 bytes)

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    scm1 "amapola" "matamoscas" `shouldBe` "amoa"
  it "e2" $
    scm1 "atamos" "matamoscas"  `shouldBe` "atamos"
  it "e3" $
    scm1 "aaa" "bbbb"           `shouldBe` ""
  it "e4" $
    scm2 "amapola" "matamoscas" `shouldBe` "amoa"
  it "e5" $
    scm2 "atamos" "matamoscas"  `shouldBe` "atamos"
  it "e6" $
    scm2 "aaa" "bbbb"           `shouldBe` ""

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--    e5
--    e6
--
--    Finished in 0.0026 seconds
--    6 examples, 0 failures

100

101

102

103

104

105

106

107

108

109

module Subsecuencia_comun_maxima where

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

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

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

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

scm1 :: Eq a => [a] -> [a] -> [a]

scm1 [] _ = []

scm1 _ [] = []

scm1 (x:xs) (y:ys)

| x == y = x : scm1 xs ys

| otherwise = mayor (scm1 (x:xs) ys) (scm1 xs (y:ys))

-- (mayor xs ys) es la cadena más larga de xs e ys.

-- mayor "hola" "buenas" == "buenas"

-- mayor "hola" "pera" == "hola"

mayor :: [a] -> [a] -> [a]

mayor xs ys

| length xs >= length ys = xs

| otherwise = ys

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

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

scm2 :: Eq a => [a] -> [a] -> [a]

scm2 xs ys = reverse (matrizSCM2 xs ys ! (n,m))

where n = length xs

m = length ys

-- (matrizSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n

-- y m son los números de elementos de xs e ys, respectivamente) tal que

-- el valor en la posición (i,j) es una SCM de los i primeros

-- elementos de xs y los j primeros elementos de ys. Por ejemplo,

-- λ> elems (matrizSCM2 "amapola" "matamoscas")

-- ["","","","","","","","","","","","","","a","a","a","a","a","a",

-- "a","a","a","","m","a","a","a","ma","ma","ma","ma","ma","ma","",

-- "m","am","am","aa","ma","ma","ma","ma","ama","ama","","m","am",

-- "am","aa","ma","ma","ma","ma","ama","ama","","m","am","am","aa",

-- "ma","oma","oma","oma","ama","ama","","m","am","am","aa","ma",

-- "oma","oma","oma","ama","ama","","m","am","am","aam","aam","oma",

-- "oma","oma","aoma","aoma"]

-- Gráficamente,

-- m a t a m o s c a s

-- ["","" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ,"",

-- a "","" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a",

-- m "","m","a" ,"a" ,"a" ,"ma" ,"ma" ,"ma" ,"ma" ,"ma" ,"ma",

-- a "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",

-- p "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",

-- o "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",

-- l "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",

-- a "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]

matrizSCM2 :: Eq a => [a] -> [a] -> Array (Int,Int) [a]

matrizSCM2 xs ys = q where

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

n = length xs

m = length ys

v = listArray (1,n) xs

w = listArray (1,m) ys

f 0 _ = []

f _ 0 = []

f i j | v ! i == w ! j = (v!i) : (q ! (i-1,j-1))

| otherwise = mayor (q ! (i-1,j)) (q ! (i,j-1))

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (scm1 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))

-- 9

-- (20.17 secs, 11,436,759,992 bytes)

-- λ> length (scm2 (take 18 (cycle [1,3])) (take 18 (cycle [2,3])))

-- 9

-- (0.00 secs, 1,013,624 bytes)

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

scm1 "amapola" "matamoscas" `shouldBe` "amoa"

it "e2" $

scm1 "atamos" "matamoscas" `shouldBe` "atamos"

it "e3" $

scm1 "aaa" "bbbb" `shouldBe` ""

it "e4" $

scm2 "amapola" "matamoscas" `shouldBe` "amoa"

it "e5" $

scm2 "atamos" "matamoscas" `shouldBe` "atamos"

it "e6" $

scm2 "aaa" "bbbb" `shouldBe` ""

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- e5

-- e6

-- Finished in 0.0026 seconds

-- 6 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)
# =============================

# (mayor xs ys) es la cadena más larga de xs e ys.
#    mayor "hola" "buenas"  ==  "buenas"
#    mayor "hola" "pera"    ==  "hola"
def mayor(xs: str, ys: str) -> str:
    if len(xs) >= len(ys):
        return xs
    return ys

def scm1(xs: str, ys: str) -> str:
    if not xs:
        return ""
    if not ys:
        return ""
    if xs[0] == ys[0]:
        return xs[0] + scm1(xs[1:], ys[1:])
    return mayor(scm1(xs, ys[1:]), scm1(xs[1:], ys))

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

def scm2(xs: str, ys: str) -> str:
    n = len(xs)
    m = len(ys)
    return (matrizSCM2(xs, ys)[n][m])[::-1]

# matrizSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n
# y m son los números de elementos de xs e ys, respectivamente) tal que
# el valor en la posición (i,j) es una SCM de los i primeros
# elementos de xs y los j primeros elementos de ys. Por ejemplo,
#    >>> matrizSCM2("amapola", "matamoscas")
#    [['', '', '', '', '', '', '', '', '', '', ''],
#     ['', '', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],
#     ['', 'm', 'a', 'a', 'a', 'ma', 'ma', 'ma', 'ma', 'ma', 'ma'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],
#     ['', 'm', 'am', 'am', 'aam', 'aam', 'oma', 'oma', 'oma', 'aoma', 'aoma']]
# Gráficamente,
#        m   a    t    a     m     o     s     c     a      s
#    ["","" ,""  ,""  ,""   ,""   ,""   ,""   ,""   ,""    ,"",
# a   "","" ,"a" ,"a" ,"a"  ,"a"  ,"a"  ,"a"  ,"a"  ,"a"   ,"a",
# m   "","m","a" ,"a" ,"a"  ,"ma" ,"ma" ,"ma" ,"ma" ,"ma"  ,"ma",
# a   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
# p   "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",
# o   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
# l   "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",
# a   "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]
def matrizSCM2(xs: str, ys: str) -> list[list[str]]:
    n = len(xs)
    m = len(ys)
    q = [["" for _ in range(m + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if xs[i - 1] == ys[j - 1]:
                q[i][j] = xs[i - 1] + q[i - 1][j - 1]
            else:
                q[i][j] = mayor(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('scm1(["1","3"]*9, ["2","3"]*9)')
#    8.44 segundos
#    >>> tiempo('scm2(["1","3"]*9, ["2","3"]*9)')
#    0.00 segundos

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

def test_scm() -> None:
    assert scm1("amapola", "matamoscas") == "amoa"
    assert scm1("atamos", "matamoscas")  == "atamos"
    assert scm1("aaa", "bbbb")           == ""
    assert scm2("amapola", "matamoscas") == "amoa"
    assert scm2("atamos", "matamoscas")  == "atamos"
    assert scm2("aaa", "bbbb")           == ""
    print("Verificado")

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

from sys import setrecursionlimit

from timeit import Timer, default_timer

setrecursionlimit(10**6)

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

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

# (mayor xs ys) es la cadena más larga de xs e ys.

# mayor "hola" "buenas" == "buenas"

# mayor "hola" "pera" == "hola"

def mayor(xs: str, ys: str) -> str:

if len(xs) >= len(ys):

return xs

return ys

def scm1(xs: str, ys: str) -> str:

if not xs:

return ""

if not ys:

return ""

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

return xs[0] + scm1(xs[1:], ys[1:])

return mayor(scm1(xs, ys[1:]), scm1(xs[1:], ys))

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

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

def scm2(xs: str, ys: str) -> str:

n = len(xs)

m = len(ys)

return (matrizSCM2(xs, ys)[n][m])[::-1]

# matrizSCM2(xs, ys) es la matriz de orden (n+1)x(m+1) (donde n

# y m son los números de elementos de xs e ys, respectivamente) tal que

# el valor en la posición (i,j) es una SCM de los i primeros

# elementos de xs y los j primeros elementos de ys. Por ejemplo,

# >>> matrizSCM2("amapola", "matamoscas")

# [['', '', '', '', '', '', '', '', '', '', ''],

# ['', '', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'],

# ['', 'm', 'a', 'a', 'a', 'ma', 'ma', 'ma', 'ma', 'ma', 'ma'],

# ['', 'm', 'am', 'am', 'aa', 'ma', 'ma', 'ma', 'ma', 'ama', 'ama'],

# ['', 'm', 'am', 'am', 'aa', 'ma', 'oma', 'oma', 'oma', 'ama', 'ama'],

# ['', 'm', 'am', 'am', 'aam', 'aam', 'oma', 'oma', 'oma', 'aoma', 'aoma']]

# Gráficamente,

# m a t a m o s c a s

# ["","" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ,"" ,"",

# a "","" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a" ,"a",

# m "","m","a" ,"a" ,"a" ,"ma" ,"ma" ,"ma" ,"ma" ,"ma" ,"ma",

# a "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",

# p "","m","am","am","aa" ,"ma" ,"ma" ,"ma" ,"ma" ,"ama" ,"ama",

# o "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",

# l "","m","am","am","aa" ,"ma" ,"oma","oma","oma","ama" ,"ama",

# a "","m","am","am","aam","aam","oma","oma","oma","aoma","aoma"]

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

n = len(xs)

m = len(ys)

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

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

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

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

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

else:

q[i][j] = mayor(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('scm1(["1","3"]*9, ["2","3"]*9)')

# 8.44 segundos

# >>> tiempo('scm2(["1","3"]*9, ["2","3"]*9)')

# 0.00 segundos

# Verificación

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

def test_scm() -> None:

assert scm1("amapola", "matamoscas") == "amoa"

assert scm1("atamos", "matamoscas") == "atamos"

assert scm1("aaa", "bbbb") == ""

assert scm2("amapola", "matamoscas") == "amoa"

assert scm2("atamos", "matamoscas") == "atamos"

assert scm2("aaa", "bbbb") == ""

print("Verificado")

# La verificación es

# >>> test_scm()

# Verificado

1. Problema de suma cero (mediante espacio de estados)

2. Problema de las jarras (mediante espacios de estados)

3. La función de Fibonacci por programación dinámica

4. Coeficientes binomiales (con programación dinámica)

5. Longitud de la subsecuencia común máxima (con programación dinámica)

6. Subsecuencia común máxima (con programación dinámica)

Se puede imprimir o compartir con