4-agosto-2023 – Exercitium

Problema de las monedas por búsqueda en escalada

PorJosé A. Alonso 4-agosto-20232-agosto-2023

El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).

En la representación se usarán los siguientes tipos:

Moneda, que es un número entero representado el valor de la moneda
Solucion, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista más corta con la misma suma.

Usando la búsqueda en escalada, definir la función

   cambio :: Int -> Solucion

1	cambio :: Int -> Solucion

tal que (cambio n) es la solución del problema de las monedas, para obtener la cantidad n, por búsqueda en escalada. Por ejemplo,

   cambio 199  ==  [2,2,5,20,20,50,100]

1	cambio 199 == [2,2,5,20,20,50,100]

Soluciones

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

Soluciones en Haskell

module Escalada_Monedas where

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

-- Las monedas son números enteros.
type Moneda = Int

-- monedas es la lista del tipo de monedas disponibles. Se supone que
-- hay un número infinito de monedas de cada tipo.
monedas :: [Moneda]
monedas = [1,2,5,10,20,50,100]

-- Las soluciones son listas de monedas.
type Solucion = [Moneda]

-- Los estados son pares formados por la cantidad que falta y la lista
-- de monedas usadas.
type Estado = (Int, [Moneda])

-- (inicial n) es el estado inicial del problema de las monedas, para
-- obtener la cantidad n.
inicial :: Int -> Estado
inicial n = (n, [])

-- (esFinal e) se verifica si e es un estado final del problema
-- de las monedas.
esFinal :: Estado -> Bool
esFinal (v,_) = v == 0

-- (sucesores e) es la lista de los sucesores del estado e en el
-- problema de las monedas. Por ejemplo,
--   λ> sucesores (199,[])
--   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),
--    (179,[20]),(149,[50]),(99,[100])]
sucesores :: Estado -> [Estado]
sucesores (r,p) =
  [(r-c,c:p) | c <- monedas, r-c >= 0]

cambio :: Int -> Solucion
cambio n =
  snd (head (buscaEscalada sucesores
                           esFinal
                           (inicial n)))
-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    cambio 199  `shouldBe`  [2,2,5,20,20,50,100]

-- La verificación es
--    λ> verifica
--
--    e1
--
--    Finished in 0.0003 seconds
--    1 example, 0 failures

module Escalada_Monedas where

import BusquedaEnEscalada

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

-- Las monedas son números enteros.

type Moneda = Int

-- monedas es la lista del tipo de monedas disponibles. Se supone que

-- hay un número infinito de monedas de cada tipo.

monedas :: [Moneda]

monedas = [1,2,5,10,20,50,100]

-- Las soluciones son listas de monedas.

type Solucion = [Moneda]

-- Los estados son pares formados por la cantidad que falta y la lista

-- de monedas usadas.

type Estado = (Int, [Moneda])

-- (inicial n) es el estado inicial del problema de las monedas, para

-- obtener la cantidad n.

inicial :: Int -> Estado

inicial n = (n, [])

-- (esFinal e) se verifica si e es un estado final del problema

-- de las monedas.

esFinal :: Estado -> Bool

esFinal (v,_) = v == 0

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

-- problema de las monedas. Por ejemplo,

-- λ> sucesores (199,[])

-- [(198,[1]),(197,[2]),(194,[5]),(189,[10]),

-- (179,[20]),(149,[50]),(99,[100])]

sucesores :: Estado -> [Estado]

sucesores (r,p) =

[(r-c,c:p) | c <- monedas, r-c >= 0]

cambio :: Int -> Solucion

cambio n =

snd (head (buscaEscalada sucesores

esFinal

(inicial n)))

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

cambio 199 `shouldBe` [2,2,5,20,20,50,100]

-- La verificación es

-- λ> verifica

-- e1

-- Finished in 0.0003 seconds

-- 1 example, 0 failures

Soluciones en Python

from typing import Optional

from src.BusquedaEnEscalada import buscaEscalada

# Las monedas son números enteros.
Moneda = int

# monedas es la lista del tipo de monedas disponibles. Se supone que
# hay un número infinito de monedas de cada tipo.
monedas: list[Moneda] = [1,2,5,10,20,50,100]

# Las soluciones son listas de monedas.
Solucion = list[Moneda]

# Los estados son pares formados por la cantidad que falta y la lista
# de monedas usadas.
Estado = tuple[int, list[Moneda]]

# inicial(n) es el estado inicial del problema de las monedas, para
# obtener la cantidad n.
def inicial(n: int) -> Estado:
    return (n, [])

# esFinal(e) se verifica si e es un estado final del problema
# de las monedas.
def esFinal(e: Estado) -> bool:
    return e[0] == 0

# sucesores(e) es la lista de los sucesores del estado e en el
# problema de las monedas. Por ejemplo,
#   λ> sucesores((199,[]))
#   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),
#    (179,[20]),(149,[50]),(99,[100])]
def sucesores(e: Estado) -> list[Estado]:
    (r,p) = e
    return [(r - c, [c] + p) for c in monedas if r - c >= 0]

def cambio(n: int) -> Optional[Solucion]:
    r = buscaEscalada(sucesores, esFinal, inicial(n))
    if r is None:
        return None
    return r[1]

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

def test_monedas() -> None:
    assert cambio(199) == [2,2,5,20,20,50,100]

# La verificación es
#    src> poetry run pytest -q Escalada_Monedas.py
#    1 passed in 0.12s

from typing import Optional

from src.BusquedaEnEscalada import buscaEscalada

# Las monedas son números enteros.

Moneda = int

# monedas es la lista del tipo de monedas disponibles. Se supone que

# hay un número infinito de monedas de cada tipo.

monedas: list[Moneda] = [1,2,5,10,20,50,100]

# Las soluciones son listas de monedas.

Solucion = list[Moneda]

# Los estados son pares formados por la cantidad que falta y la lista

# de monedas usadas.

Estado = tuple[int, list[Moneda]]

# inicial(n) es el estado inicial del problema de las monedas, para

# obtener la cantidad n.

def inicial(n: int) -> Estado:

return (n, [])

# esFinal(e) se verifica si e es un estado final del problema

# de las monedas.

def esFinal(e: Estado) -> bool:

return e[0] == 0

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

# problema de las monedas. Por ejemplo,

# λ> sucesores((199,[]))

# [(198,[1]),(197,[2]),(194,[5]),(189,[10]),

# (179,[20]),(149,[50]),(99,[100])]

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

(r,p) = e

return [(r - c, [c] + p) for c in monedas if r - c >= 0]

def cambio(n: int) -> Optional[Solucion]:

r = buscaEscalada(sucesores, esFinal, inicial(n))

if r is None:

return None

return r[1]

# Verificación

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

def test_monedas() -> None:

assert cambio(199) == [2,2,5,20,20,50,100]

# La verificación es

# src> poetry run pytest -q Escalada_Monedas.py

# 1 passed in 0.12s

Búsqueda en escalada

PorJosé A. Alonso 4-agosto-20232-agosto-2023

En la búsqueda en escalada se supone que los estados están mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.

Definir la función

   buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

1	buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

tal que (buscaEscalada s o e) es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando en escalada.

Nota: La búsqueda en escalada se aplica en el problema de las monedas.

Soluciones

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

Soluciones en Haskell

module BusquedaEnEscalada (buscaEscalada)  where

import TAD.ColaDePrioridad (esVacia, inserta, primero, vacia)

buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]
buscaEscalada sucesores esFinal x = busca' (inserta x vacia) where
  busca' c
    | esVacia c           = []
    | esFinal (primero c) = [primero c]
    | otherwise           = busca' (foldr inserta vacia (sucesores (primero c)))

module BusquedaEnEscalada (buscaEscalada) where

import TAD.ColaDePrioridad (esVacia, inserta, primero, vacia)

buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

buscaEscalada sucesores esFinal x = busca' (inserta x vacia) where

busca' c

| esVacia c = []

| esFinal (primero c) = [primero c]

| otherwise = busca' (foldr inserta vacia (sucesores (primero c)))

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from functools import reduce
from typing import Callable, Optional, Protocol, TypeVar

from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,
                                     vacia)


class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def buscaEscalada(sucesores: Callable[[A], list[A]],
                  esFinal: Callable[[A], bool],
                  inicial: A) -> Optional[A]:
    c: CPrioridad[A] = inserta(inicial, vacia())

    while not esVacia(c):
        x = primero(c)
        if esFinal(x):
            return x

        c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia())

    return None

from __future__ import annotations

from abc import abstractmethod

from functools import reduce

from typing import Callable, Optional, Protocol, TypeVar

from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,

vacia)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def buscaEscalada(sucesores: Callable[[A], list[A]],

esFinal: Callable[[A], bool],

inicial: A) -> Optional[A]:

c: CPrioridad[A] = inserta(inicial, vacia())

while not esVacia(c):

x = primero(c)

if esFinal(x):

return x

c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia())

return None

Día: 4-agosto-2023

Problema de las monedas por búsqueda en escalada

Búsqueda en escalada

Entradas recientes

Buscar

Correo electrónico