Haskell y Python – Página 3

El tipo abstracto de datos de las colas de prioridad

PorJosé A. Alonso 5-julio-20237-julio-2023

1. El tipo abstracto de datos de las colas de prioridad

Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operación de extracción siempre elige el elemento de menor prioridad.

Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:

   vacia   :: Ord a => CPrioridad a
   inserta :: Ord a => a -> CPrioridad a -> CPrioridad a
   primero :: Ord a => CPrioridad a -> a
   resto   :: Ord a => CPrioridad a -> CPrioridad a
   esVacia :: Ord a => CPrioridad a -> Bool

vacia :: Ord a => CPrioridad a

inserta :: Ord a => a -> CPrioridad a -> CPrioridad a

primero :: Ord a => CPrioridad a -> a

resto :: Ord a => CPrioridad a -> CPrioridad a

esVacia :: Ord a => CPrioridad a -> Bool

tales que

vacia es la cola de prioridad vacía.
(inserta x c) añade el elemento x a la cola de prioridad c.
(primero c) es el primer elemento de la cola de prioridad c.
(resto c) es el resto de la cola de prioridad c.
(esVacia c) se verifica si la cola de prioridad c es vacía.

Las operaciones tienen que verificar las siguientes propiedades:

inserta x (inserta y c) == inserta y (inserta x c)
primero (inserta x vacia) == x
Si x <= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)
resto (inserta x vacia) == vacia
Si x <= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))
esVacia vacia
not (esVacia (inserta x c))

2. Las colas de prioridad en Haskell

2.1. El tipo abstracto de datos de las colas de prioridad en Haskell

El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:

module TAD.ColaDePrioridad
  (CPrioridad,
   vacia,   -- Ord a => CPrioridad a
   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a
   primero, -- Ord a => CPrioridad a -> a
   resto,   -- Ord a => CPrioridad a -> CPrioridad a
   esVacia, -- Ord a => CPrioridad a -> Bool
  ) where

import TAD.ColaDePrioridadConListas

module TAD.ColaDePrioridad

(CPrioridad,

vacia, -- Ord a => CPrioridad a

inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a

primero, -- Ord a => CPrioridad a -> a

resto, -- Ord a => CPrioridad a -> CPrioridad a

esVacia, -- Ord a => CPrioridad a -> Bool

) where

import TAD.ColaDePrioridadConListas

Para usar el TAD hay que usar una implementación concreta. En principio,
solo considearemos una que usa las listas.

2.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:

{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaDePrioridadConListas
  (CPrioridad,
   vacia,   -- Ord a => CPrioridad a
   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a
   primero, -- Ord a => CPrioridad a -> a
   resto,   -- Ord a => CPrioridad a -> CPrioridad a
   esVacia, -- Ord a => CPrioridad a -> Bool
  ) where

import Test.QuickCheck

-- Colas de prioridad mediante listas.
newtype CPrioridad a = CP [a]
  deriving Eq

-- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de
-- prioridad c. Por ejemplo,
--    λ> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia)))
--    "2 | 3 | 5"
escribeColaDePrioridad :: Show a => CPrioridad a -> String
escribeColaDePrioridad (CP [])     = "-"
escribeColaDePrioridad (CP [x])    = show x
escribeColaDePrioridad (CP (x:xs)) = show x ++ " | " ++ escribeColaDePrioridad (CP xs)

-- Procedimiento de escritura de colas de prioridad.
instance Show a => Show (CPrioridad a) where
  show = escribeColaDePrioridad

-- Ejemplo de cola de prioridad
--    λ> inserta 5 (inserta 2 (inserta 3 vacia))
--    2 | 3 | 5

-- vacia es la cola de prioridad vacía. Por ejemplo,
--    λ> vacia
--    CP []
vacia :: Ord a => CPrioridad a
vacia = CP []

-- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola
-- de prioridad c. Por ejemplo,
--    λ> inserta 5 (foldr inserta vacia [3,1,7,2,9])
--    1 | 2 | 3 | 5 | 7 | 9
inserta :: Ord a => a -> CPrioridad a -> CPrioridad a
inserta x (CP q) = CP (ins x q)
  where ins y []                   = [y]
        ins y r@(e:r') | y < e     = y:r
                       | otherwise = e:ins y r'

-- (primero c) es el primer elemento de la cola de prioridad c. Por
-- ejemplo,
--    primero (foldr inserta vacia [3,1,7,2,9])  ==  1
primero :: Ord a => CPrioridad a -> a
primero (CP(x:_)) = x
primero _         = error "primero: cola de prioridad vacia"

-- (resto c) es la cola de prioridad obtenida eliminando el primer
-- elemento de la cola de prioridad c. Por ejemplo,
--    λ> resto (foldr inserta vacia [3,1,7,2,9])
--    2 | 3 | 7 | 9
resto :: Ord a => CPrioridad a -> CPrioridad a
resto (CP (_:xs)) = CP xs
resto _           = error "resto: cola de prioridad vacia"

-- (esVacia c) se verifica si la cola de prioridad c es vacía. Por
-- ejemplo,
--    esVacia (foldr inserta vacia [3,1,7,2,9]) ==  False
--    esVacia vacia                             ==  True
esVacia :: Ord a => CPrioridad a -> Bool
esVacia (CP xs) = null xs

-- Generador de colas de prioridad
-- ===============================

-- genCPrioridad es un generador de colas de enteros. Por ejemplo,
--    λ> sample genCPrioridad
--    -
--    0 | 0
--    4
--    -4 | -3 | 6 | 6
--    -7 | -6 | -2 | 0
--    -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10
--    -
--    -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14
--    -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16
--    -
--    -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7
genCPrioridad :: (Arbitrary a, Num a, Ord a) =>  Gen (CPrioridad a)
genCPrioridad = do
  xs <- listOf arbitrary
  return (foldr inserta vacia xs)

-- El tipo cola de prioridad es una instancia del arbitrario.
instance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where
  arbitrary = genCPrioridad

-- Propiedades de las colas de prioridad
-- =====================================

-- Propiedad. Si se añade dos elementos a una cola de prioridad se
-- obtiene la misma cola de prioridad idependientemente del orden en
-- que se añadan los elementos.
prop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool
prop_inserta_conmuta x y c =
  inserta x (inserta y c) == inserta y (inserta x c)

-- Comprobación.
--    λ> quickCheck prop_inserta_conmuta
--    +++ OK, passed 100 tests.

-- Propiedad. La cabeza de la cola de prioridad obtenida añadiendo un
-- elemento x a la cola de prioridad vacía es x.
prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool
prop_primero_inserta_vacia x _ =
  primero (inserta x vacia) == x

-- Comprobación.
--    λ> quickCheck prop_primero_inserta_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. El primer elemento de una cola de prioridad c no cambia
-- cuando se le añade un elemento mayor o igual que algún elemento de c.
prop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property
prop_primero_inserta x y c =
  x <= y ==> primero (inserta y c') == primero c'
  where c' = inserta x c

-- Comprobación.
--    λ> quickCheck prop_primero_inserta
--    +++ OK, passed 100 tests.

-- Propiedad. El resto de añadir un elemento a la cola de prioridad
-- vacía es la cola vacía.
prop_resto_inserta_vacia :: Int -> Bool
prop_resto_inserta_vacia x =
  resto (inserta x vacia) == vacia

-- Comprobación.
--    λ> quickCheck prop_resto_inserta_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. El resto de la cola de prioridad obtenida añadiendo un
-- elemento y a una cola c' (que tiene algún elemento menor o igual que
-- y) es la cola que se obtiene añadiendo y al resto de c'.
prop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property
prop_resto_inserta x y c =
  x <= y ==> resto (inserta y c') == inserta y (resto c')
  where c' = inserta x c

-- Comprobación:
--    λ> quickCheck prop_resto_inserta
--    +++ OK, passed 100 tests.

-- Propiedad. vacia es una cola vacía.
prop_vacia_es_vacia :: Bool
prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int)

-- Comprobación.
--    λ> quickCheck prop_vacia_es_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. Si se añade un elemento a una cola de prioridad se obtiene
-- una cola no vacía.
prop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool
prop_inserta_no_es_vacia x c =
  not (esVacia (inserta x c))

-- Comprobación.
--    λ> quickCheck prop_inserta_no_es_vacia
--    +++ OK, passed 100 tests.

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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

{-# LANGUAGE FlexibleInstances #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.ColaDePrioridadConListas

(CPrioridad,

vacia, -- Ord a => CPrioridad a

inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a

primero, -- Ord a => CPrioridad a -> a

resto, -- Ord a => CPrioridad a -> CPrioridad a

esVacia, -- Ord a => CPrioridad a -> Bool

) where

import Test.QuickCheck

-- Colas de prioridad mediante listas.

newtype CPrioridad a = CP [a]

deriving Eq

-- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de

-- prioridad c. Por ejemplo,

-- λ> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia)))

-- "2 | 3 | 5"

escribeColaDePrioridad :: Show a => CPrioridad a -> String

escribeColaDePrioridad (CP []) = "-"

escribeColaDePrioridad (CP [x]) = show x

escribeColaDePrioridad (CP (x:xs)) = show x ++ " | " ++ escribeColaDePrioridad (CP xs)

-- Procedimiento de escritura de colas de prioridad.

instance Show a => Show (CPrioridad a) where

show = escribeColaDePrioridad

-- Ejemplo de cola de prioridad

-- λ> inserta 5 (inserta 2 (inserta 3 vacia))

-- 2 | 3 | 5

-- vacia es la cola de prioridad vacía. Por ejemplo,

-- λ> vacia

-- CP []

vacia :: Ord a => CPrioridad a

vacia = CP []

-- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola

-- de prioridad c. Por ejemplo,

-- λ> inserta 5 (foldr inserta vacia [3,1,7,2,9])

-- 1 | 2 | 3 | 5 | 7 | 9

inserta :: Ord a => a -> CPrioridad a -> CPrioridad a

inserta x (CP q) = CP (ins x q)

where ins y [] = [y]

ins y r@(e:r') | y < e = y:r

| otherwise = e:ins y r'

-- (primero c) es el primer elemento de la cola de prioridad c. Por

-- ejemplo,

-- primero (foldr inserta vacia [3,1,7,2,9]) == 1

primero :: Ord a => CPrioridad a -> a

primero (CP(x:_)) = x

primero _ = error "primero: cola de prioridad vacia"

-- (resto c) es la cola de prioridad obtenida eliminando el primer

-- elemento de la cola de prioridad c. Por ejemplo,

-- λ> resto (foldr inserta vacia [3,1,7,2,9])

-- 2 | 3 | 7 | 9

resto :: Ord a => CPrioridad a -> CPrioridad a

resto (CP (_:xs)) = CP xs

resto _ = error "resto: cola de prioridad vacia"

-- (esVacia c) se verifica si la cola de prioridad c es vacía. Por

-- ejemplo,

-- esVacia (foldr inserta vacia [3,1,7,2,9]) == False

-- esVacia vacia == True

esVacia :: Ord a => CPrioridad a -> Bool

esVacia (CP xs) = null xs

-- Generador de colas de prioridad

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

-- genCPrioridad es un generador de colas de enteros. Por ejemplo,

-- λ> sample genCPrioridad

-- -

-- 0 | 0

-- 4

-- -4 | -3 | 6 | 6

-- -7 | -6 | -2 | 0

-- -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10

-- -

-- -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14

-- -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16

-- -

-- -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7

genCPrioridad :: (Arbitrary a, Num a, Ord a) => Gen (CPrioridad a)

genCPrioridad = do

xs <- listOf arbitrary

return (foldr inserta vacia xs)

-- El tipo cola de prioridad es una instancia del arbitrario.

instance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where

arbitrary = genCPrioridad

-- Propiedades de las colas de prioridad

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

-- Propiedad. Si se añade dos elementos a una cola de prioridad se

-- obtiene la misma cola de prioridad idependientemente del orden en

-- que se añadan los elementos.

prop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool

prop_inserta_conmuta x y c =

inserta x (inserta y c) == inserta y (inserta x c)

-- Comprobación.

-- λ> quickCheck prop_inserta_conmuta

-- +++ OK, passed 100 tests.

-- Propiedad. La cabeza de la cola de prioridad obtenida añadiendo un

-- elemento x a la cola de prioridad vacía es x.

prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool

prop_primero_inserta_vacia x _ =

primero (inserta x vacia) == x

-- Comprobación.

-- λ> quickCheck prop_primero_inserta_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. El primer elemento de una cola de prioridad c no cambia

-- cuando se le añade un elemento mayor o igual que algún elemento de c.

prop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property

prop_primero_inserta x y c =

x <= y ==> primero (inserta y c') == primero c'

where c' = inserta x c

-- Comprobación.

-- λ> quickCheck prop_primero_inserta

-- +++ OK, passed 100 tests.

-- Propiedad. El resto de añadir un elemento a la cola de prioridad

-- vacía es la cola vacía.

prop_resto_inserta_vacia :: Int -> Bool

prop_resto_inserta_vacia x =

resto (inserta x vacia) == vacia

-- Comprobación.

-- λ> quickCheck prop_resto_inserta_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. El resto de la cola de prioridad obtenida añadiendo un

-- elemento y a una cola c' (que tiene algún elemento menor o igual que

-- y) es la cola que se obtiene añadiendo y al resto de c'.

prop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property

prop_resto_inserta x y c =

x <= y ==> resto (inserta y c') == inserta y (resto c')

where c' = inserta x c

-- Comprobación:

-- λ> quickCheck prop_resto_inserta

-- +++ OK, passed 100 tests.

-- Propiedad. vacia es una cola vacía.

prop_vacia_es_vacia :: Bool

prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int)

-- Comprobación.

-- λ> quickCheck prop_vacia_es_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. Si se añade un elemento a una cola de prioridad se obtiene

-- una cola no vacía.

prop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool

prop_inserta_no_es_vacia x c =

not (esVacia (inserta x c))

-- Comprobación.

-- λ> quickCheck prop_inserta_no_es_vacia

-- +++ OK, passed 100 tests.

3. Las colas de prioridad en Python

3.1. El tipo abstracto de las colas de prioridad en Python

La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:

__all__ = [
   'CPrioridad',
   'vacia',
   'inserta',
   'primero',
   'resto',
   'esVacia',
    ]

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

__all__ = [

'CPrioridad',

'vacia',

'inserta',

'primero',

'resto',

'esVacia',

]

from src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta,

primero, resto, vacia)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.

3.2. Implementación de las colas de prioridad mediante listas

La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:

inserta(x) añade x a la cola.
primero() es el primero de la cola.
resto() elimina el primero de la cola.
esVacia() se verifica si la cola es vacía.

Por ejemplo,

   >>> c = CPrioridad()
   >>> c
   -
   >>> c.inserta(5)
   >>> c.inserta(2)
   >>> c.inserta(3)
   >>> c.inserta(4)
   >>> c
   2 | 3 | 4 | 5
   >>> c.primero()
   2
   >>> c.resto()
   >>> c
   3 | 4 | 5
   >>> c.esVacia()
   False
   >>> c = CPrioridad()
   >>> c.esVacia()
   True

>>> c = CPrioridad()

>>> c

>>> c.inserta(5)

>>> c.inserta(2)

>>> c.inserta(3)

>>> c.inserta(4)

>>> c

2 | 3 | 4 | 5

>>> c.primero()

>>> c.resto()

>>> c

3 | 4 | 5

>>> c.esVacia()

False

>>> c = CPrioridad()

>>> c.esVacia()

True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))
   2 | 3 | 4 | 5
   >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   2
   >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   3 | 4 | 5
   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

>>> vacia()

>>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))

2 | 3 | 4 | 5

>>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

>>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

3 | 4 | 5

>>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))

False

>>> esVacia(vacia())

True

Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.

from __future__ import annotations

__all__ = [
   'CPrioridad',
   'vacia',
   'inserta',
   'primero',
   'resto',
   'esVacia',
]

from abc import abstractmethod
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, Protocol, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st


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

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

# Clase de las colas de prioridad mediante listas
# ===============================================

@dataclass
class CPrioridad(Generic[A]):
    _elementos: list[A] = field(default_factory=list)

    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la cola separados por " | ".
        Si la cola está vacía, devuelve "-".
        """
        if not self._elementos:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)

    def esVacia(self) -> bool:
        """
        Comprueba si la cola está vacía.

        Devuelve True si la cola está vacía, False en caso contrario.
        """
        return not self._elementos

    def inserta(self, x: A) -> None:
        """
        Inserta el elemento x en la cola de prioridad.
        """
        self._elementos.append(x)
        self._elementos.sort()

    def primero(self) -> A:
        """
        Devuelve el primer elemento de la cola.
        """
        return self._elementos[0]

    def resto(self) -> None:
        """
        Elimina el primer elemento de la cola
        """
        self._elementos.pop(0)

# Funciones del tipo de las listas
# ================================

def vacia() -> CPrioridad[A]:
    """
    Crea y devuelve una cola vacía de tipo A.
    """
    c: CPrioridad[A] = CPrioridad()
    return c

def inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]:
    """
    Inserta un elemento x en la cola c y devuelve una nueva cola con
    el elemento insertado.
    """
    _aux = deepcopy(c)
    _aux.inserta(x)
    return _aux

def esVacia(c: CPrioridad[A]) -> bool:
    """
    Devuelve True si la cola está vacía, False si no lo está.
    """
    return c.esVacia()

def primero(c: CPrioridad[A]) -> A:
    """
    Devuelve el primer elemento de la cola c.
    """
    return c.primero()

def resto(c: CPrioridad[A]) -> CPrioridad[A]:
    """
    Elimina el primer elemento de la cola c y devuelve una copia de la
    cola resultante.
    """
    _aux = deepcopy(c)
    _aux.resto()
    return _aux

# Generador de colas de prioridad
# ===============================

def colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]:
    """
    Genera una estrategia de búsqueda para generar colas de enteros de
    forma aleatoria.

    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase cola.
    """
    return st.lists(st.integers()).map(CPrioridad)

# Comprobación de las propiedades de las colas
# ============================================

# Las propiedades son
@given(c=colaAleatoria(), x=st.integers(), y=st.integers())
def test_cola1(c: CPrioridad[int], x: int, y: int) -> None:
    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))
    assert primero(inserta(x, vacia())) == x
    assert resto(inserta(x, vacia())) == vacia()
    assert esVacia(vacia())
    assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers(), y=st.integers())
def test_cola2(c: CPrioridad[int], x: int, y: int) -> None:
    assume(not y < x)
    assert primero(inserta(y, (inserta(x, c)))) == \
        primero(inserta(x,c))
    assert resto(inserta(y, (inserta(x, c)))) == \
        inserta(y, resto(inserta(x, c)))

# La comprobación es
#    > poetry run pytest -q ColaDePrioridadConListas.py
#    2 passed in 0.54s

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

135

136

137

138

139

140

141

142

143

144

145

146

from __future__ import annotations

__all__ = [

'CPrioridad',

'vacia',

'inserta',

'primero',

'resto',

'esVacia',

]

from abc import abstractmethod

from copy import deepcopy

from dataclasses import dataclass, field

from typing import Generic, Protocol, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

class Comparable(Protocol):

@abstractmethod

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

pass

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

# Clase de las colas de prioridad mediante listas

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

@dataclass

class CPrioridad(Generic[A]):

_elementos: list[A] = field(default_factory=list)

def __repr__(self) -> str:

"""

Devuelve una cadena con los elementos de la cola separados por " | ".

Si la cola está vacía, devuelve "-".

"""

if not self._elementos:

return '-'

return ' | '.join(str(x) for x in self._elementos)

def esVacia(self) -> bool:

"""

Comprueba si la cola está vacía.

Devuelve True si la cola está vacía, False en caso contrario.

"""

return not self._elementos

def inserta(self, x: A) -> None:

"""

Inserta el elemento x en la cola de prioridad.

"""

self._elementos.append(x)

self._elementos.sort()

def primero(self) -> A:

"""

Devuelve el primer elemento de la cola.

"""

return self._elementos[0]

def resto(self) -> None:

"""

Elimina el primer elemento de la cola

"""

self._elementos.pop(0)

# Funciones del tipo de las listas

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

def vacia() -> CPrioridad[A]:

"""

Crea y devuelve una cola vacía de tipo A.

"""

c: CPrioridad[A] = CPrioridad()

return c

def inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]:

"""

Inserta un elemento x en la cola c y devuelve una nueva cola con

el elemento insertado.

"""

_aux = deepcopy(c)

_aux.inserta(x)

return _aux

def esVacia(c: CPrioridad[A]) -> bool:

"""

Devuelve True si la cola está vacía, False si no lo está.

"""

return c.esVacia()

def primero(c: CPrioridad[A]) -> A:

"""

Devuelve el primer elemento de la cola c.

"""

return c.primero()

def resto(c: CPrioridad[A]) -> CPrioridad[A]:

"""

Elimina el primer elemento de la cola c y devuelve una copia de la

cola resultante.

"""

_aux = deepcopy(c)

_aux.resto()

return _aux

# Generador de colas de prioridad

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

def colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]:

"""

Genera una estrategia de búsqueda para generar colas de enteros de

forma aleatoria.

Utiliza la librería Hypothesis para generar una lista de enteros y

luego se convierte en una instancia de la clase cola.

"""

return st.lists(st.integers()).map(CPrioridad)

# Comprobación de las propiedades de las colas

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

# Las propiedades son

@given(c=colaAleatoria(), x=st.integers(), y=st.integers())

def test_cola1(c: CPrioridad[int], x: int, y: int) -> None:

assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))

assert primero(inserta(x, vacia())) == x

assert resto(inserta(x, vacia())) == vacia()

assert esVacia(vacia())

assert not esVacia(inserta(x, c))

@given(c=colaAleatoria(), x=st.integers(), y=st.integers())

def test_cola2(c: CPrioridad[int], x: int, y: int) -> None:

assume(not y < x)

assert primero(inserta(y, (inserta(x, c)))) == \

primero(inserta(x,c))

assert resto(inserta(y, (inserta(x, c)))) == \

inserta(y, resto(inserta(x, c)))

# La comprobación es

# > poetry run pytest -q ColaDePrioridadConListas.py

# 2 passed in 0.54s

El problema de la mochila (mediante espacio de estados)

PorJosé A. Alonso 4-julio-20231-julio-2023

Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.

Para solucionar el problema se definen los siguientes tipos:

Una solución del problema de la mochila es una lista de objetos.

     type SolMoch = [Objeto]

1	type SolMoch = [Objeto]

Los objetos son pares formado por un peso y un valor

     type Objeto = (Peso,Valor)

1	type Objeto = (Peso,Valor)

Los pesos son número enteros

     type Peso = Int

1	type Peso = Int

Los valores son números reales.

     type Valor = Float

1	type Valor = Float

Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.

     type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

1	type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

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

   mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

1	mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

tal que mochila os l es la solución del problema de la mochila para la lista de objetos os y el límite de capacidad l. Por ejemplo,

   > mochila [(2,3),(3,5),(4,6),(5,10)] 8
   ([(5,10.0),(3,5.0)],15.0)
   > mochila [(2,3),(3,5),(5,6)] 10
   ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
   > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35
   ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)
   > mochila [(2,2.8),(3,4.4),(5,6.1)] 10
   ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

> mochila [(2,3),(3,5),(4,6),(5,10)] 8

([(5,10.0),(3,5.0)],15.0)

> mochila [(2,3),(3,5),(5,6)] 10

([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

> mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35

([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)

> mochila [(2,2.8),(3,4.4),(5,6.1)] 10

([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

Soluciones

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

Soluciones en Haskell

module BEE_Mochila where

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

type Peso     = Int
type Valor    = Float
type Objeto   = (Peso,Valor)
type SolMoch  = [Objeto]
type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

mochila :: [Objeto] -> Peso -> (SolMoch,Valor)
mochila os l = (sol,v)
  where
    (v,_,_,_,sol) =
      maximum (buscaProfundidad sucesoresMoch
                                esObjetivoMoch
                                (inicial os l))

-- (inicial os l) es el estado inicial del problema de la mochila
-- para la lista de objetos os y el límite de capacidad l
inicial :: [Objeto] -> Peso -> NodoMoch
inicial os l =
  (0,0,l,sort os,[])

-- (sucesoresMoch e) es la lista de los sucesores del estado e en el
-- problema de la mochila para la lista de objetos os y el límite de
-- capacidad l.
sucesoresMoch :: NodoMoch -> [NodoMoch]
sucesoresMoch (v,p,l,os,solp) =
  [( v+v',
     p+p',
     l,
     [o | o@(p'',_) <- os, p''>=p'],
     (p',v'):solp )
  | (p',v') <- os,
    p+p' <= l]

-- (esObjetivoMoch e) se verifica si e es un estado final el problema de
-- la mochila para la lista de objetos os y el límite de capacidad l .
esObjetivoMoch :: NodoMoch -> Bool
esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    mochila [(2,3),(3,5),(4,6),(5,10)] 8
    `shouldBe` ([(5,10.0),(3,5.0)],15.0)
  it "e2" $
    mochila [(2,3),(3,5),(5,6)] 10
    `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
  it "e3" $
    mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35
    `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)
  it "e4" $
    mochila [(2,2.8),(3,4.4),(5,6.1)] 10
    `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

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

module BEE_Mochila where

import BusquedaEnProfundidad (buscaProfundidad)

import Data.List (sort)

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

type Peso = Int

type Valor = Float

type Objeto = (Peso,Valor)

type SolMoch = [Objeto]

type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

mochila :: [Objeto] -> Peso -> (SolMoch,Valor)

mochila os l = (sol,v)

where

(v,_,_,_,sol) =

maximum (buscaProfundidad sucesoresMoch

esObjetivoMoch

(inicial os l))

-- (inicial os l) es el estado inicial del problema de la mochila

-- para la lista de objetos os y el límite de capacidad l

inicial :: [Objeto] -> Peso -> NodoMoch

inicial os l =

(0,0,l,sort os,[])

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

-- problema de la mochila para la lista de objetos os y el límite de

-- capacidad l.

sucesoresMoch :: NodoMoch -> [NodoMoch]

sucesoresMoch (v,p,l,os,solp) =

[( v+v',

p+p',

[o | o@(p'',_) <- os, p''>=p'],

(p',v'):solp )

| (p',v') <- os,

p+p' <= l]

-- (esObjetivoMoch e) se verifica si e es un estado final el problema de

-- la mochila para la lista de objetos os y el límite de capacidad l .

esObjetivoMoch :: NodoMoch -> Bool

esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

mochila [(2,3),(3,5),(4,6),(5,10)] 8

`shouldBe` ([(5,10.0),(3,5.0)],15.0)

it "e2" $

mochila [(2,3),(3,5),(5,6)] 10

`shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

it "e3" $

mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35

`shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)

it "e4" $

mochila [(2,2.8),(3,4.4),(5,6.1)] 10

`shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- e4

-- Finished in 0.0424 seconds

-- 4 examples, 0 failures

Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad

Peso = int
Valor = float
Objeto = tuple[Peso, Valor]
SolMoch = list[Objeto]
NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]

# inicial(os, l) es el estado inicial del problema de la mochila
# para la lista de objetos os y el límite de capacidad l
def inicial(os: list[Objeto], l: Peso) -> NodoMoch:
    return (0,0,l,sorted(os),[])

# sucesoresMoch(e) es la lista de los sucesores del estado e en el
# problema de la mochila para la lista de objetos os y el límite de
# capacidad l.
def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:
    (v,p,l,os,solp) = n
    return [( v+v1,
              p+p1,
              l,
              [(p2,v2) for (p2,v2) in os if p2 >= p1],
              [(p1,v1)] + solp )
            for (p1,v1) in os if p + p1 <= l]

# esObjetivoMoch(e) se verifica si e es un estado final el problema de
# la mochila para la lista de objetos os y el límite de capacidad l .
def esObjetivoMoch(e: NodoMoch) -> bool:
    (_, p, l, os, _) = e
    (p_, _) = os[0]
    return p + p_ > l

def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:
    (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,
                                         esObjetivoMoch,
                                         inicial(os, l)))
    return (sol, v)

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

def test_Mochila() -> None:
    assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \
        ([(5,10.0),(3,5.0)],15.0)
    assert mochila([(2,3),(3,5),(5,6)], 10) == \
        ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)
    assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \
        ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)
    print("Verificado")

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

from src.BusquedaEnProfundidad import buscaProfundidad

Peso = int

Valor = float

Objeto = tuple[Peso, Valor]

SolMoch = list[Objeto]

NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch]

# inicial(os, l) es el estado inicial del problema de la mochila

# para la lista de objetos os y el límite de capacidad l

def inicial(os: list[Objeto], l: Peso) -> NodoMoch:

return (0,0,l,sorted(os),[])

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

# problema de la mochila para la lista de objetos os y el límite de

# capacidad l.

def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]:

(v,p,l,os,solp) = n

return [( v+v1,

p+p1,

[(p2,v2) for (p2,v2) in os if p2 >= p1],

[(p1,v1)] + solp )

for (p1,v1) in os if p + p1 <= l]

# esObjetivoMoch(e) se verifica si e es un estado final el problema de

# la mochila para la lista de objetos os y el límite de capacidad l .

def esObjetivoMoch(e: NodoMoch) -> bool:

(_, p, l, os, _) = e

(p_, _) = os[0]

return p + p_ > l

def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]:

(v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch,

esObjetivoMoch,

inicial(os, l)))

return (sol, v)

# Verificación

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

def test_Mochila() -> None:

assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \

([(5,10.0),(3,5.0)],15.0)

assert mochila([(2,3),(3,5),(5,6)], 10) == \

([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)

assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \

([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)

print("Verificado")

# La verificación es

# >>> test_Mochila()

# Verificado

El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)

PorJosé A. Alonso 3-julio-202328-junio-2023

El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

   type Columna = Int
   type Fila    = Int

1 2	type Columna = Int type Fila = Int

Una solución del problema de las n reinas es una lista de posiciones.

   type SolNR = [(Columna,Fila)]

1	type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en anchura, definir las funciones

   solucionesNR      :: Columna -> [SolNR]
   primeraSolucionNR :: Columna -> SolNR
   nSolucionesNR     :: Columna -> Int

solucionesNR :: Columna -> [SolNR]

primeraSolucionNR :: Columna -> SolNR

nSolucionesNR :: Columna -> Int

tales que

solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en anchura. Por ejemplo,

     take 3 (solucionesNR 8)
     [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],
      [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],
      [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]

take 3 (solucionesNR 8)

[[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],

[(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],

[(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]

primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,

     λ> primeraSolucionNR 8
     [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]

1 2	λ> primeraSolucionNR 8 [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)]

nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

     nSolucionesNR 8  ==  92

1	nSolucionesNR 8 == 92

Soluciones

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

Soluciones en Haskell

module BEE_Reinas_Anchura where

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

type Columna = Int
type Fila    = Int
type SolNR = [(Columna,Fila)]

-- Los nodos del problema de las n reinas son ternas formadas por la
-- columna de la última reina colocada, el número de columnas del
-- tablero y la solución parcial de las reinas colocadas anteriormente.
type NodoNR = (Columna,Columna,SolNR)

solucionesNR :: Columna -> [SolNR]
solucionesNR n =
  map estado (buscaAnchura sucesoresNR esFinalNR (1,n,[]))
  where
    estado (_,_,e) = e

primeraSolucionNR :: Columna -> SolNR
primeraSolucionNR =
  head . solucionesNR

nSolucionesNR :: Columna -> Int
nSolucionesNR =
  length . solucionesNR

-- (valida sp p) se verifica si la posición p es válida respecto de la
-- solución parcial sp; es decir, la reina en la posición p no amenaza a
-- ninguna de las reinas de la sp (se supone que están en distintas
-- columnas). Por ejemplo,
--    valida [(1,1)] (2,2)  ==  False
--    valida [(1,1)] (2,3)  ==  True
valida :: SolNR -> (Columna,Fila) -> Bool
valida solp (c,r) = and [test s | s <- solp]
  where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r

-- (sucesoresNR e) es la lista de los sucesores del estado e en el
-- problema de las n reinas. Por ejemplo,
--    λ> sucesoresNR (1,4,[])
--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]
sucesoresNR :: NodoNR -> [NodoNR]
sucesoresNR (c,n,solp) =
  [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]

-- (esFinalNR e) se verifica si e es un estado final del problema de las
-- n reinas.
esFinalNR :: NodoNR -> Bool
esFinalNR (c,n,_) = c > n

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    take 3 (solucionesNR 8) `shouldBe`
    [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],
     [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],
     [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]
  it "e2" $
    nSolucionesNR 8 `shouldBe` 92

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

module BEE_Reinas_Anchura where

import BusquedaEnAnchura (buscaAnchura)

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

type Columna = Int

type Fila = Int

type SolNR = [(Columna,Fila)]

-- Los nodos del problema de las n reinas son ternas formadas por la

-- columna de la última reina colocada, el número de columnas del

-- tablero y la solución parcial de las reinas colocadas anteriormente.

type NodoNR = (Columna,Columna,SolNR)

solucionesNR :: Columna -> [SolNR]

solucionesNR n =

map estado (buscaAnchura sucesoresNR esFinalNR (1,n,[]))

where

estado (_,_,e) = e

primeraSolucionNR :: Columna -> SolNR

primeraSolucionNR =

head . solucionesNR

nSolucionesNR :: Columna -> Int

nSolucionesNR =

length . solucionesNR

-- (valida sp p) se verifica si la posición p es válida respecto de la

-- solución parcial sp; es decir, la reina en la posición p no amenaza a

-- ninguna de las reinas de la sp (se supone que están en distintas

-- columnas). Por ejemplo,

-- valida [(1,1)] (2,2) == False

-- valida [(1,1)] (2,3) == True

valida :: SolNR -> (Columna,Fila) -> Bool

valida solp (c,r) = and [test s | s <- solp]

where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r

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

-- problema de las n reinas. Por ejemplo,

-- λ> sucesoresNR (1,4,[])

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

sucesoresNR :: NodoNR -> [NodoNR]

sucesoresNR (c,n,solp) =

[(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]

-- (esFinalNR e) se verifica si e es un estado final del problema de las

-- n reinas.

esFinalNR :: NodoNR -> Bool

esFinalNR (c,n,_) = c > n

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

take 3 (solucionesNR 8) `shouldBe`

[[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],

[(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],

[(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]

it "e2" $

nSolucionesNR 8 `shouldBe` 92

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.2116 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.BusquedaEnAnchura import buscaAnchura

Columna = int
Fila = int
SolNR = list[tuple[Columna, Fila]]

# Los nodos del problema de las n reinas son ternas formadas por la
# columna de la última reina colocada, el número de columnas del
# tablero y la solución parcial de las reinas colocadas anteriormente.
NodoNR = tuple[Columna, Columna, SolNR]

# valida(sp, p) se verifica si la posición p es válida respecto de la
# solución parcial sp; es decir, la reina en la posición p no amenaza a
# ninguna de las reinas de la sp (se supone que están en distintas
# columnas). Por ejemplo,
#    valida([(1,1)], (2,2))  ==  False
#    valida([(1,1)], (2,3))  ==  True
def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:
    c, r = p
    def test(s: tuple[Columna, Fila]) -> bool:
        c1, r1 = s
        return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r

    return all(test(s) for s in sp)

# sucesoresNR(e) es la lista de los sucesores del estado e en el
# problema de las n reinas. Por ejemplo,
#    >>> sucesoresNR((1,4,[]))
#    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]
def sucesoresNR (nd: NodoNR) -> list[NodoNR]:
    c,n,solp = nd
    return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]

# esFinalNR(e) se verifica si e es un estado final del problema de las
# n reinas.
def esFinalNR(nd: NodoNR) -> bool:
    c, n, _ = nd
    return c > n

def solucionesNR(n: int) -> list[SolNR]:
    nInicial: NodoNR = (1,n,[])
    return [e for (_, _, e) in buscaAnchura(sucesoresNR,
                                            esFinalNR,
                                            nInicial)]

def primeraSolucionNR(n: int) -> SolNR:
    return solucionesNR(n)[0]

def nSolucionesNR(n: int) -> int:
    return len(solucionesNR(n))

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

def test_nReinas() -> None:
    assert solucionesNR(5)[:3] == \
        [[(1,1),(2,3),(3,5),(4,2),(5,4)],
         [(1,1),(2,4),(3,2),(4,5),(5,3)],
         [(1,2),(2,4),(3,1),(4,3),(5,5)]]
    assert nSolucionesNR(5) == 10
    print("Verificado")

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

from src.BusquedaEnAnchura import buscaAnchura

Columna = int

Fila = int

SolNR = list[tuple[Columna, Fila]]

# Los nodos del problema de las n reinas son ternas formadas por la

# columna de la última reina colocada, el número de columnas del

# tablero y la solución parcial de las reinas colocadas anteriormente.

NodoNR = tuple[Columna, Columna, SolNR]

# valida(sp, p) se verifica si la posición p es válida respecto de la

# solución parcial sp; es decir, la reina en la posición p no amenaza a

# ninguna de las reinas de la sp (se supone que están en distintas

# columnas). Por ejemplo,

# valida([(1,1)], (2,2)) == False

# valida([(1,1)], (2,3)) == True

def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:

c, r = p

def test(s: tuple[Columna, Fila]) -> bool:

c1, r1 = s

return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r

return all(test(s) for s in sp)

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

# problema de las n reinas. Por ejemplo,

# >>> sucesoresNR((1,4,[]))

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

def sucesoresNR (nd: NodoNR) -> list[NodoNR]:

c,n,solp = nd

return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]

# esFinalNR(e) se verifica si e es un estado final del problema de las

# n reinas.

def esFinalNR(nd: NodoNR) -> bool:

c, n, _ = nd

return c > n

def solucionesNR(n: int) -> list[SolNR]:

nInicial: NodoNR = (1,n,[])

return [e for (_, _, e) in buscaAnchura(sucesoresNR,

esFinalNR,

nInicial)]

def primeraSolucionNR(n: int) -> SolNR:

return solucionesNR(n)[0]

def nSolucionesNR(n: int) -> int:

return len(solucionesNR(n))

# Verificación

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

def test_nReinas() -> None:

assert solucionesNR(5)[:3] == \

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

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

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

assert nSolucionesNR(5) == 10

print("Verificado")

# La verificación es

# >>> test_nReinas()

# Verificado

Búsqueda por anchura en espacios de estados

PorJosé A. Alonso 30-junio-202328-junio-2023

Las características de los problemas de espacios de estados son:

un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
un nodo inicial y
un nodo objetivo que es la solución.

Definir la función

   buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                              -> nodo -> [nodo]

1 2	buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]

tal que buscaAnchura 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 mediante búsqueda en anchura.

Soluciones

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

Soluciones en Haskell

module BusquedaEnAnchura (buscaAnchura) where

import TAD.Cola (esVacia, inserta, primero, resto, vacia)

buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                               -> nodo -> [nodo]
buscaAnchura sucesores esFinal inicial =
  aux (inserta inicial vacia)
  where
    aux p
      | esVacia p        = []
      | esFinal (primero p) = primero p : aux (resto p)
      | otherwise        = aux (foldr
                                inserta
                                (resto p)
                                (sucesores (primero p)))

module BusquedaEnAnchura (buscaAnchura) where

import TAD.Cola (esVacia, inserta, primero, resto, vacia)

buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)

-> nodo -> [nodo]

buscaAnchura sucesores esFinal inicial =

aux (inserta inicial vacia)

where

aux p

| esVacia p = []

| esFinal (primero p) = primero p : aux (resto p)

| otherwise = aux (foldr

inserta

(resto p)

(sucesores (primero p)))

Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from typing import Callable, TypeVar

from src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia

A = TypeVar('A')

setrecursionlimit(10**6)

def buscaAnchura(sucesores: Callable[[A], list[A]],
                  esFinal: Callable[[A], bool],
                  inicial: A) -> list[A]:
    def aux(p: Cola[A]) -> list[A]:
        if esVacia(p):
            return []
        if esFinal(primero(p)):
            return [primero(p)] + aux(resto(p))
        return aux(reduce(lambda x, y: inserta(y, x),
                          sucesores(primero(p)),
                          resto(p)))

    return aux (inserta(inicial, vacia()))

from functools import reduce

from sys import setrecursionlimit

from typing import Callable, TypeVar

from src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia

A = TypeVar('A')

setrecursionlimit(10**6)

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

esFinal: Callable[[A], bool],

inicial: A) -> list[A]:

def aux(p: Cola[A]) -> list[A]:

if esVacia(p):

return []

if esFinal(primero(p)):

return [primero(p)] + aux(resto(p))

return aux(reduce(lambda x, y: inserta(y, x),

sucesores(primero(p)),

resto(p)))

return aux (inserta(inicial, vacia()))

El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)

PorJosé A. Alonso 29-junio-202328-junio-2023

El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.

Las posiciones de las reinas en el tablero se representan por su columna y su fila.

   type Columna = Int
   type Fila    = Int

1 2	type Columna = Int type Fila = Int

Una solución del problema de las n reinas es una lista de posiciones.

   type SolNR = [(Columna,Fila)]

1	type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en profundidad, definir las funciones

   solucionesNR      :: Columna -> [SolNR]
   primeraSolucionNR :: Columna -> SolNR
   nSolucionesNR     :: Columna -> Int

solucionesNR :: Columna -> [SolNR]

primeraSolucionNR :: Columna -> SolNR

nSolucionesNR :: Columna -> Int

tales que

solucionesNR n es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en profundidad. Por ejemplo,

     take 3 (solucionesNR 8)
     [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],
      [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],
      [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]

take 3 (solucionesNR 8)

[[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],

[(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],

[(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]

primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,

     λ> primeraSolucionNR 8
     [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)]

1 2	λ> primeraSolucionNR 8 [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)]

nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,

     nSolucionesNR 8  ==  92

1	nSolucionesNR 8 == 92

Soluciones

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

Soluciones en Haskell

module BEE_Reinas_Profundidad where

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

type Columna = Int
type Fila    = Int
type SolNR = [(Columna,Fila)]

-- Los nodos del problema de las n reinas son ternas formadas por la
-- columna de la última reina colocada, el número de columnas del
-- tablero y la solución parcial de las reinas colocadas anteriormente.
type NodoNR = (Columna,Columna,SolNR)

solucionesNR :: Columna -> [SolNR]
solucionesNR n =
  map estado (buscaProfundidad sucesoresNR esFinalNR (1,n,[]))
  where
    estado (_,_,e) = e

primeraSolucionNR :: Columna -> SolNR
primeraSolucionNR =
  head . solucionesNR

nSolucionesNR :: Columna -> Int
nSolucionesNR =
  length . solucionesNR

-- (valida sp p) se verifica si la posición p es válida respecto de la
-- solución parcial sp; es decir, la reina en la posición p no amenaza a
-- ninguna de las reinas de la sp (se supone que están en distintas
-- columnas). Por ejemplo,
--    valida [(1,1)] (2,2)  ==  False
--    valida [(1,1)] (2,3)  ==  True
valida :: SolNR -> (Columna,Fila) -> Bool
valida solp (c,r) = and [test s | s <- solp]
  where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r

-- (sucesoresNR e) es la lista de los sucesores del estado e en el
-- problema de las n reinas. Por ejemplo,
--    λ> sucesoresNR (1,4,[])
--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]
sucesoresNR :: NodoNR -> [NodoNR]
sucesoresNR (c,n,solp) =
  [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]

-- (esFinalNR e) se verifica si e es un estado final del problema de las
-- n reinas.
esFinalNR :: NodoNR -> Bool
esFinalNR (c,n,_) = c > n

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    take 3 (solucionesNR 8) `shouldBe`
    [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],
     [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],
     [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]
  it "e2" $
    nSolucionesNR 8 `shouldBe` 92

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

module BEE_Reinas_Profundidad where

import BusquedaEnProfundidad (buscaProfundidad)

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

type Columna = Int

type Fila = Int

type SolNR = [(Columna,Fila)]

-- Los nodos del problema de las n reinas son ternas formadas por la

-- columna de la última reina colocada, el número de columnas del

-- tablero y la solución parcial de las reinas colocadas anteriormente.

type NodoNR = (Columna,Columna,SolNR)

solucionesNR :: Columna -> [SolNR]

solucionesNR n =

map estado (buscaProfundidad sucesoresNR esFinalNR (1,n,[]))

where

estado (_,_,e) = e

primeraSolucionNR :: Columna -> SolNR

primeraSolucionNR =

head . solucionesNR

nSolucionesNR :: Columna -> Int

nSolucionesNR =

length . solucionesNR

-- (valida sp p) se verifica si la posición p es válida respecto de la

-- solución parcial sp; es decir, la reina en la posición p no amenaza a

-- ninguna de las reinas de la sp (se supone que están en distintas

-- columnas). Por ejemplo,

-- valida [(1,1)] (2,2) == False

-- valida [(1,1)] (2,3) == True

valida :: SolNR -> (Columna,Fila) -> Bool

valida solp (c,r) = and [test s | s <- solp]

where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r

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

-- problema de las n reinas. Por ejemplo,

-- λ> sucesoresNR (1,4,[])

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

sucesoresNR :: NodoNR -> [NodoNR]

sucesoresNR (c,n,solp) =

[(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)]

-- (esFinalNR e) se verifica si e es un estado final del problema de las

-- n reinas.

esFinalNR :: NodoNR -> Bool

esFinalNR (c,n,_) = c > n

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

take 3 (solucionesNR 8) `shouldBe`

[[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],

[(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],

[(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]

it "e2" $

nSolucionesNR 8 `shouldBe` 92

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.1173 seconds

-- 2 examples, 0 failures

Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad

Columna = int
Fila = int
SolNR = list[tuple[Columna, Fila]]

# Los nodos del problema de las n reinas son ternas formadas por la
# columna de la última reina colocada, el número de columnas del
# tablero y la solución parcial de las reinas colocadas anteriormente.
NodoNR = tuple[Columna, Columna, SolNR]

# valida(sp, p) se verifica si la posición p es válida respecto de la
# solución parcial sp; es decir, la reina en la posición p no amenaza a
# ninguna de las reinas de la sp (se supone que están en distintas
# columnas). Por ejemplo,
#    valida([(1,1)], (2,2))  ==  False
#    valida([(1,1)], (2,3))  ==  True
def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:
    c, r = p
    def test(s: tuple[Columna, Fila]) -> bool:
        c1, r1 = s
        return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r

    return all(test(s) for s in sp)

# sucesoresNR(e) es la lista de los sucesores del estado e en el
# problema de las n reinas. Por ejemplo,
#    >>> sucesoresNR((1,4,[]))
#    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]
def sucesoresNR (nd: NodoNR) -> list[NodoNR]:
    c,n,solp = nd
    return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]

# esFinalNR(e) se verifica si e es un estado final del problema de las
# n reinas.
def esFinalNR(nd: NodoNR) -> bool:
    c, n, _ = nd
    return c > n

def solucionesNR(n: int) -> list[SolNR]:
    nInicial: NodoNR = (1,n,[])
    return [e for (_, _, e) in buscaProfundidad(sucesoresNR,
                                                esFinalNR,
                                                nInicial)]

def primeraSolucionNR(n: int) -> SolNR:
    return solucionesNR(n)[0]

def nSolucionesNR(n: int) -> int:
    return len(solucionesNR(n))

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

def test_nReinas() -> None:
    assert solucionesNR(8)[:3] == \
        [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],
         [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],
         [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]
    assert nSolucionesNR(8) == 92
    print("Verificado")

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

from src.BusquedaEnProfundidad import buscaProfundidad

Columna = int

Fila = int

SolNR = list[tuple[Columna, Fila]]

# Los nodos del problema de las n reinas son ternas formadas por la

# columna de la última reina colocada, el número de columnas del

# tablero y la solución parcial de las reinas colocadas anteriormente.

NodoNR = tuple[Columna, Columna, SolNR]

# valida(sp, p) se verifica si la posición p es válida respecto de la

# solución parcial sp; es decir, la reina en la posición p no amenaza a

# ninguna de las reinas de la sp (se supone que están en distintas

# columnas). Por ejemplo,

# valida([(1,1)], (2,2)) == False

# valida([(1,1)], (2,3)) == True

def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool:

c, r = p

def test(s: tuple[Columna, Fila]) -> bool:

c1, r1 = s

return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r

return all(test(s) for s in sp)

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

# problema de las n reinas. Por ejemplo,

# >>> sucesoresNR((1,4,[]))

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

def sucesoresNR (nd: NodoNR) -> list[NodoNR]:

c,n,solp = nd

return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))]

# esFinalNR(e) se verifica si e es un estado final del problema de las

# n reinas.

def esFinalNR(nd: NodoNR) -> bool:

c, n, _ = nd

return c > n

def solucionesNR(n: int) -> list[SolNR]:

nInicial: NodoNR = (1,n,[])

return [e for (_, _, e) in buscaProfundidad(sucesoresNR,

esFinalNR,

nInicial)]

def primeraSolucionNR(n: int) -> SolNR:

return solucionesNR(n)[0]

def nSolucionesNR(n: int) -> int:

return len(solucionesNR(n))

# Verificación

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

def test_nReinas() -> None:

assert solucionesNR(8)[:3] == \

[[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)],

[(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)],

[(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]]

assert nSolucionesNR(8) == 92

print("Verificado")

# La verificación es

# >>> test_nReinas()

# Verificado

Búsqueda en espacios de estados por profundidad

PorJosé A. Alonso 28-junio-202327-junio-2023

Las características de los problemas de espacios de estados son:

un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
un nodo inicial y
un nodo objetivo que es la solución.

Definir la función

   buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                                  -> nodo -> [nodo]

1 2	buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]

tal que buscaProfundidad 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 mediante búsqueda en profundidad.

Soluciones

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

Soluciones en Haskell

module BusquedaEnProfundidad (buscaProfundidad) where

import TAD.Pila (apila, cima, desapila, esVacia, vacia)

buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                               -> nodo -> [nodo]
buscaProfundidad sucesores esFinal inicial =
  aux (apila inicial vacia)
  where
    aux p
      | esVacia p        = []
      | esFinal (cima p) = cima p : aux (desapila p)
      | otherwise        = aux (foldr
                                apila
                                (desapila p)
                                (sucesores (cima p)))

module BusquedaEnProfundidad (buscaProfundidad) where

import TAD.Pila (apila, cima, desapila, esVacia, vacia)

buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)

-> nodo -> [nodo]

buscaProfundidad sucesores esFinal inicial =

aux (apila inicial vacia)

where

aux p

| esVacia p = []

| esFinal (cima p) = cima p : aux (desapila p)

| otherwise = aux (foldr

apila

(desapila p)

(sucesores (cima p)))

Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from typing import Callable, TypeVar

from src.TAD.pila import Pila, apila, cima, desapila, esVacia, vacia

A = TypeVar('A')

setrecursionlimit(10**6)

def buscaProfundidad1(sucesores: Callable[[A], list[A]],
                      esFinal: Callable[[A], bool],
                      inicial: A) -> list[A]:
    def aux(p: Pila[A]) -> list[A]:
        if esVacia(p):
            return []
        if esFinal(cima(p)):
            return [cima(p)] + aux(desapila(p))
        return aux(reduce(lambda x, y: apila(y, x),
                          sucesores(cima(p)),
                          desapila(p)))

    return aux(apila(inicial, vacia()))

from functools import reduce

from sys import setrecursionlimit

from typing import Callable, TypeVar

from src.TAD.pila import Pila, apila, cima, desapila, esVacia, vacia

A = TypeVar('A')

setrecursionlimit(10**6)

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

esFinal: Callable[[A], bool],

inicial: A) -> list[A]:

def aux(p: Pila[A]) -> list[A]:

if esVacia(p):

return []

if esFinal(cima(p)):

return [cima(p)] + aux(desapila(p))

return aux(reduce(lambda x, y: apila(y, x),

sucesores(cima(p)),

desapila(p)))

return aux(apila(inicial, vacia()))

Rompecabeza del triominó mediante divide y vencerás

PorJosé A. Alonso 27-junio-202321-junio-2023

Un poliominó es una figura geométrica plana formada conectando dos o más cuadrados por alguno de sus lados. Los cuadrados se conectan lado con lado, pero no se pueden conectar ni por sus vértices, ni juntando solo parte de un lado de un cuadrado con parte de un lado de otro. Si unimos dos cuadrados se obtiene un dominó, si se juntan tres cuadrados se construye un triominó.

Sólo existen dos triominós, el I-triomino (por tener forma de I) y el L-triominó (por su forma de L) como se observa en las siguientes figuras

   X
   X     X
   X     XX

X X

X XX

El rompecabeza del triominó consiste en cubrir un tablero cuadrado con 2^n filas y 2^n columnas, en el que se ha eliminado una casilla, con L-triominós de formas que cubran todas las casillas excepto la eliminada y los triominós no se solapen.

La casilla eliminada se representará con -1 y los L-triominós sucesiones de tres números consecutivos en forma de L. Con esta representación una solución del rompecabeza del triominó con 4 filas y la fila eliminada en la posición (4,4) es

   (  3  3  2  2 )
   (  3  1  1  2 )
   (  4  1  5  5 )
   (  4  4  5 -1 )

( 3 3 2 2 )

( 3 1 1 2 )

( 4 1 5 5 )

( 4 4 5 -1 )

Definir la función

   triomino :: Int -> Posicion -> Tablero

1	triomino :: Int -> Posicion -> Tablero

tal que (triomino n p) es la solución, mediante divide y vencerás, del rompecabeza del triominó en un cuadrado nxn en el que se ha eliminado la casilla de la posición p. Por ejemplo,

   λ> triomino 4 (4,4)
   (  3  3  2  2 )
   (  3  1  1  2 )
   (  4  1  5  5 )
   (  4  4  5 -1 )

   λ> triomino 4 (2,3)
   (  3  3  2  2 )
   (  3  1 -1  2 )
   (  4  1  1  5 )
   (  4  4  5  5 )

   λ> triomino 16 (5,6)
   (  7  7  6  6  6  6  5  5  6  6  5  5  5  5  4  4 )
   (  7  5  5  6  6  4  4  5  6  4  4  5  5  3  3  4 )
   (  8  5  9  9  7  7  4  8  7  4  8  8  6  6  3  7 )
   (  8  8  9  3  3  7  8  8  7  7  8  2  2  6  7  7 )
   (  8  8  7  3  9 -1  8  8  7  7  6  6  2  8  7  7 )
   (  8  6  7  7  9  9  7  8  7  5  5  6  8  8  6  7 )
   (  9  6  6 10 10  7  7 11  8  8  5  9  9  6  6 10 )
   (  9  9 10 10 10 10 11 11  1  8  9  9  9  9 10 10 )
   (  8  8  7  7  7  7  6  1  1  9  8  8  8  8  7  7 )
   (  8  6  6  7  7  5  6  6  9  9  7  8  8  6  6  7 )
   (  9  6 10 10  8  5  5  9 10  7  7 11  9  9  6 10 )
   (  9  9 10  4  8  8  9  9 10 10 11 11  5  9 10 10 )
   (  9  9  8  4  4 10  9  9 10 10  9  5  5 11 10 10 )
   (  9  7  8  8 10 10  8  9 10  8  9  9 11 11  9 10 )
   ( 10  7  7 11 11  8  8 12 11  8  8 12 12  9  9 13 )
   ( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )

λ> triomino 4 (4,4)

( 3 3 2 2 )

( 3 1 1 2 )

( 4 1 5 5 )

( 4 4 5 -1 )

λ> triomino 4 (2,3)

( 3 3 2 2 )

( 3 1 -1 2 )

( 4 1 1 5 )

( 4 4 5 5 )

λ> triomino 16 (5,6)

( 7 7 6 6 6 6 5 5 6 6 5 5 5 5 4 4 )

( 7 5 5 6 6 4 4 5 6 4 4 5 5 3 3 4 )

( 8 5 9 9 7 7 4 8 7 4 8 8 6 6 3 7 )

( 8 8 9 3 3 7 8 8 7 7 8 2 2 6 7 7 )

( 8 8 7 3 9 -1 8 8 7 7 6 6 2 8 7 7 )

( 8 6 7 7 9 9 7 8 7 5 5 6 8 8 6 7 )

( 9 6 6 10 10 7 7 11 8 8 5 9 9 6 6 10 )

( 9 9 10 10 10 10 11 11 1 8 9 9 9 9 10 10 )

( 8 8 7 7 7 7 6 1 1 9 8 8 8 8 7 7 )

( 8 6 6 7 7 5 6 6 9 9 7 8 8 6 6 7 )

( 9 6 10 10 8 5 5 9 10 7 7 11 9 9 6 10 )

( 9 9 10 4 8 8 9 9 10 10 11 11 5 9 10 10 )

( 9 9 8 4 4 10 9 9 10 10 9 5 5 11 10 10 )

( 9 7 8 8 10 10 8 9 10 8 9 9 11 11 9 10 )

( 10 7 7 11 11 8 8 12 11 8 8 12 12 9 9 13 )

( 10 10 11 11 11 11 12 12 11 11 12 12 12 12 13 13 )

Soluciones

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

Soluciones en Haskell

module Rompecabeza_del_triomino_mediante_divide_y_venceras where

import DivideVenceras (divideVenceras)
import Data.Matrix
import Data.List (delete)
import Test.Hspec (Spec, hspec, it, shouldBe)

-- Los tableros son matrices de números enteros donde -1 representa el
-- hueco, 0 las posiciones sin rellenar y los números mayores que 0
-- representan los triominós.
type Tablero = Matrix Int

-- Los problemas se representarán mediante pares formados por un número
-- natural mayor que 0 (que indica el número con el que se formará el
-- siguiente triominó que se coloque) y un tablero.
type Problema = (Int,Tablero)

-- Las posiciones son pares de números enteros
type Posicion = (Int,Int)

triomino :: Int -> Posicion -> Tablero
triomino n p =
  divideVenceras ind resuelve divide combina (pbInicial n p)

-- (tablero n p) es el tablero inicial del problema del triominó
-- en un cuadrado nxn en el que se ha eliminado la casilla de la
-- posición (i,j). Por ejemplo,
--    λ> tablero 4 (3,4)
--    (  0  0  0  0 )
--    (  0  0  0  0 )
--    (  0  0  0 -1 )
--    (  0  0  0  0 )
tablero :: Int -> Posicion -> Tablero
tablero n (i,j) =
  setElem (-1) (i,j) (zero n n)

-- (pbInicial n p) es el problema inicial del rompecabeza del triominó
-- en un cuadrado nxn en el que se ha eliminado la casilla de la
-- posición p. Por ejemplo,
--    λ> pbInicial 4 (4,4)
--    (1,(  0  0  0  0 )
--       (  0  0  0  0 )
--       (  0  0  0  0 )
--       (  0  0  0 -1 ))
pbInicial :: Int -> Posicion -> Problema
pbInicial n p = (1,tablero n p)

-- (ind pb) se verifica si el problema pb es indivisible. Por ejemplo,
--    ind (pbInicial 2 (1,2))  ==  True
--    ind (pbInicial 4 (1,2))  ==  False
ind :: Problema -> Bool
ind (_,p) = ncols p == 2

-- (posicionHueco t) es la posición del hueco en el tablero t. Por
-- ejemplo,
--    posicionHueco (tablero 8 (5,2))  ==  (5,2)
posicionHueco :: Tablero -> Posicion
posicionHueco p =
  head [(i,j) | i <- [1..nrows p],
                j <- [1..ncols p],
                p!(i,j) /= 0]

-- (cuadranteHueco p) es el cuadrante donde se encuentra el hueco del
-- tablero t (donde la numeración de los cuadrantes es 1 el superior
-- izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el
-- inferior derecho). Por ejemplo,
--    cuadranteHueco (tablero 8 (4,4))  ==  1
--    cuadranteHueco (tablero 8 (5,2))  ==  2
--    cuadranteHueco (tablero 8 (3,6))  ==  3
--    cuadranteHueco (tablero 8 (6,6))  ==  4
cuadranteHueco :: Tablero -> Int
cuadranteHueco t
  | i <= x && j <= x = 1
  | i >  x && j <= x = 2
  | i <= x && j >  x = 3
  | otherwise        = 4
  where (i,j) = posicionHueco t
        x     = nrows t `div` 2

-- (centralHueco t) es la casilla central del cuadrante del tablero t
-- donde se encuentra el hueco. Por ejemplo,
--    centralHueco (tablero 8 (5,2))  ==  (5,4)
--    centralHueco (tablero 8 (4,4))  ==  (4,4)
--    centralHueco (tablero 8 (3,6))  ==  (4,5)
--    centralHueco (tablero 8 (6,6))  ==  (5,5)
centralHueco :: Tablero -> Posicion
centralHueco t =
  case cuadranteHueco t of
    1 -> (x,x)
    2 -> (x+1,x)
    3 -> (x,x+1)
    _ -> (x+1,x+1)
  where x = nrows t `div` 2

-- (centralesSinHueco t) son las posiciones centrales del tablero t de
-- los cuadrantes sin hueco. Por ejemplo,
--    centralesSinHueco (tablero 8 (5,2))  ==  [(4,4),(4,5),(5,5)]
centralesSinHueco :: Tablero -> [Posicion]
centralesSinHueco t =
  delete (i,j) [(x,x),(x+1,x),(x,x+1),(x+1,x+1)]
  where x     = nrows t `div` 2
        (i,j) = centralHueco t

-- (actualiza t ps) es la matriz obtenida cambiando en t los valores del
-- las posiciones indicadas en ps por sus correspondientes valores. Por
-- ejemplo,
--    λ> actualiza (identity 3) [((1,2),4),((3,1),5)]
--    ( 1 4 0 )
--    ( 0 1 0 )
--    ( 5 0 1 )
actualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a
actualiza p []             = p
actualiza p (((i,j),x):zs) = setElem x (i,j) (actualiza p zs)

-- (triominoCentral (n,t) es el tablero obtenido colocando el triominó
-- formado por el número n en las posiciones centrales de los 3
-- cuadrantes que no contienen el hueco. Por ejemplo,
--    λ> triominoCentral (7,tablero 4 (4,4))
--    (  0  0  0  0 )
--    (  0  7  7  0 )
--    (  0  7  0  0 )
--    (  0  0  0 -1 )
triominoCentral :: Problema -> Tablero
triominoCentral (n,t) =
  actualiza t [((i,j),n) | (i,j) <- centralesSinHueco t]

-- (resuelve p) es la solución del problema indivisible p. Por ejemplo,
--    λ> tablero 2 (2,2)
--    (  0  0 )
--    (  0 -1 )
--
--    λ> resuelve (5,tablero 2 (2,2))
--    (  5  5 )
--    (  5 -1 )
resuelve :: Problema -> Tablero
resuelve = triominoCentral

-- (divide (n,t)) es la lista de de los problemas obtenidos colocando el
-- triominó n en las casillas centrales de t que no contienen el hueco y
-- dividir el tablero en sus cuatros cuadrantes y aumentar en uno el
-- número del correspondiente triominó. Por ejemplo,
--    λ> divide (3,tablero 4 (4,4))
--    [(4,(  0  0 )
--        (  3  0 )),
--     (5,(  0  0 )
--        (  0  3 )),
--     (6,(  0  3 )
--        (  0  0 )),
--     (7,(  0  0 )
--        (  0 -1 ))]
divide :: Problema -> [Problema]
divide (n,t) =
  [(n+1, submatrix 1     x (x+1) m q),
   (n+2, submatrix 1     x 1     x q),
   (n+3, submatrix (x+1) m 1     x q),
   (n+4, submatrix (x+1) m (x+1) m q)]
  where q = triominoCentral (n,t)
        m = nrows t
        x = m `div` 2

-- (combina p ts) es la combinación de las soluciones ts de los
-- subproblemas del problema p. Por ejemplo,
--    λ> let inicial = (1,tablero 4 (4,4)) :: (Int,Matrix Int)
--    λ> let [p1,p2,p3,p4] = divide inicial
--    λ> let [s1,s2,s3,s4] = map resuelve [p1,p2,p3,p4]
--    λ> combina inicial [s1,s2,s3,s4]
--    (  3  3  2  2 )
--    (  3  1  1  2 )
--    (  4  1  5  5 )
--    (  4  4  5 -1 )
combina :: Problema -> [Tablero] -> Tablero
combina _ [s1,s2,s3,s4] = joinBlocks (s2,s1,s3,s4)
combina _ _             = error "Imposible"

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    toLists (triomino 4 (4,4)) `shouldBe`
    [[3,3,2,2],
     [3,1,1,2],
     [4,1,5,5],
     [4,4,5,-1]]
  it "e2" $
    toLists (triomino 4 (2,3)) `shouldBe`
    [[3,3,2,2],
     [3,1,-1,2],
     [4,1,1,5],
     [4,4,5,5]]
  it "e3" $
    toLists (triomino 16 (5,6)) `shouldBe`
    [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],
     [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],
     [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7],
     [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],
     [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],
     [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],
     [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],
     [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],
     [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],
     [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],
     [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],
     [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],
     [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],
     [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],
     [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],
     [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--
--    Finished in 0.0018 seconds
--    3 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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

module Rompecabeza_del_triomino_mediante_divide_y_venceras where

import DivideVenceras (divideVenceras)

import Data.Matrix

import Data.List (delete)

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

-- Los tableros son matrices de números enteros donde -1 representa el

-- hueco, 0 las posiciones sin rellenar y los números mayores que 0

-- representan los triominós.

type Tablero = Matrix Int

-- Los problemas se representarán mediante pares formados por un número

-- natural mayor que 0 (que indica el número con el que se formará el

-- siguiente triominó que se coloque) y un tablero.

type Problema = (Int,Tablero)

-- Las posiciones son pares de números enteros

type Posicion = (Int,Int)

triomino :: Int -> Posicion -> Tablero

triomino n p =

divideVenceras ind resuelve divide combina (pbInicial n p)

-- (tablero n p) es el tablero inicial del problema del triominó

-- en un cuadrado nxn en el que se ha eliminado la casilla de la

-- posición (i,j). Por ejemplo,

-- λ> tablero 4 (3,4)

-- ( 0 0 0 0 )

-- ( 0 0 0 -1 )

-- ( 0 0 0 0 )

tablero :: Int -> Posicion -> Tablero

tablero n (i,j) =

setElem (-1) (i,j) (zero n n)

-- (pbInicial n p) es el problema inicial del rompecabeza del triominó

-- en un cuadrado nxn en el que se ha eliminado la casilla de la

-- posición p. Por ejemplo,

-- λ> pbInicial 4 (4,4)

-- (1,( 0 0 0 0 )

-- ( 0 0 0 0 )

-- ( 0 0 0 -1 ))

pbInicial :: Int -> Posicion -> Problema

pbInicial n p = (1,tablero n p)

-- (ind pb) se verifica si el problema pb es indivisible. Por ejemplo,

-- ind (pbInicial 2 (1,2)) == True

-- ind (pbInicial 4 (1,2)) == False

ind :: Problema -> Bool

ind (_,p) = ncols p == 2

-- (posicionHueco t) es la posición del hueco en el tablero t. Por

-- ejemplo,

-- posicionHueco (tablero 8 (5,2)) == (5,2)

posicionHueco :: Tablero -> Posicion

posicionHueco p =

head [(i,j) | i <- [1..nrows p],

j <- [1..ncols p],

p!(i,j) /= 0]

-- (cuadranteHueco p) es el cuadrante donde se encuentra el hueco del

-- tablero t (donde la numeración de los cuadrantes es 1 el superior

-- izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el

-- inferior derecho). Por ejemplo,

-- cuadranteHueco (tablero 8 (4,4)) == 1

-- cuadranteHueco (tablero 8 (5,2)) == 2

-- cuadranteHueco (tablero 8 (3,6)) == 3

-- cuadranteHueco (tablero 8 (6,6)) == 4

cuadranteHueco :: Tablero -> Int

cuadranteHueco t

| i <= x && j <= x = 1

| i > x && j <= x = 2

| i <= x && j > x = 3

| otherwise = 4

where (i,j) = posicionHueco t

x = nrows t `div` 2

-- (centralHueco t) es la casilla central del cuadrante del tablero t

-- donde se encuentra el hueco. Por ejemplo,

-- centralHueco (tablero 8 (5,2)) == (5,4)

-- centralHueco (tablero 8 (4,4)) == (4,4)

-- centralHueco (tablero 8 (3,6)) == (4,5)

-- centralHueco (tablero 8 (6,6)) == (5,5)

centralHueco :: Tablero -> Posicion

centralHueco t =

case cuadranteHueco t of

1 -> (x,x)

2 -> (x+1,x)

3 -> (x,x+1)

_ -> (x+1,x+1)

where x = nrows t `div` 2

-- (centralesSinHueco t) son las posiciones centrales del tablero t de

-- los cuadrantes sin hueco. Por ejemplo,

-- centralesSinHueco (tablero 8 (5,2)) == [(4,4),(4,5),(5,5)]

centralesSinHueco :: Tablero -> [Posicion]

centralesSinHueco t =

delete (i,j) [(x,x),(x+1,x),(x,x+1),(x+1,x+1)]

where x = nrows t `div` 2

(i,j) = centralHueco t

-- (actualiza t ps) es la matriz obtenida cambiando en t los valores del

-- las posiciones indicadas en ps por sus correspondientes valores. Por

-- ejemplo,

-- λ> actualiza (identity 3) [((1,2),4),((3,1),5)]

-- ( 1 4 0 )

-- ( 0 1 0 )

-- ( 5 0 1 )

actualiza :: Matrix a -> [((Int,Int),a)] -> Matrix a

actualiza p [] = p

actualiza p (((i,j),x):zs) = setElem x (i,j) (actualiza p zs)

-- (triominoCentral (n,t) es el tablero obtenido colocando el triominó

-- formado por el número n en las posiciones centrales de los 3

-- cuadrantes que no contienen el hueco. Por ejemplo,

-- λ> triominoCentral (7,tablero 4 (4,4))

-- ( 0 0 0 0 )

-- ( 0 7 7 0 )

-- ( 0 7 0 0 )

-- ( 0 0 0 -1 )

triominoCentral :: Problema -> Tablero

triominoCentral (n,t) =

actualiza t [((i,j),n) | (i,j) <- centralesSinHueco t]

-- (resuelve p) es la solución del problema indivisible p. Por ejemplo,

-- λ> tablero 2 (2,2)

-- ( 0 0 )

-- ( 0 -1 )

-- λ> resuelve (5,tablero 2 (2,2))

-- ( 5 5 )

-- ( 5 -1 )

resuelve :: Problema -> Tablero

resuelve = triominoCentral

-- (divide (n,t)) es la lista de de los problemas obtenidos colocando el

-- triominó n en las casillas centrales de t que no contienen el hueco y

-- dividir el tablero en sus cuatros cuadrantes y aumentar en uno el

-- número del correspondiente triominó. Por ejemplo,

-- λ> divide (3,tablero 4 (4,4))

-- [(4,( 0 0 )

-- ( 3 0 )),

-- (5,( 0 0 )

-- ( 0 3 )),

-- (6,( 0 3 )

-- ( 0 0 )),

-- (7,( 0 0 )

-- ( 0 -1 ))]

divide :: Problema -> [Problema]

divide (n,t) =

[(n+1, submatrix 1 x (x+1) m q),

(n+2, submatrix 1 x 1 x q),

(n+3, submatrix (x+1) m 1 x q),

(n+4, submatrix (x+1) m (x+1) m q)]

where q = triominoCentral (n,t)

m = nrows t

x = m `div` 2

-- (combina p ts) es la combinación de las soluciones ts de los

-- subproblemas del problema p. Por ejemplo,

-- λ> let inicial = (1,tablero 4 (4,4)) :: (Int,Matrix Int)

-- λ> let [p1,p2,p3,p4] = divide inicial

-- λ> let [s1,s2,s3,s4] = map resuelve [p1,p2,p3,p4]

-- λ> combina inicial [s1,s2,s3,s4]

-- ( 3 3 2 2 )

-- ( 3 1 1 2 )

-- ( 4 1 5 5 )

-- ( 4 4 5 -1 )

combina :: Problema -> [Tablero] -> Tablero

combina _ [s1,s2,s3,s4] = joinBlocks (s2,s1,s3,s4)

combina _ _ = error "Imposible"

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

toLists (triomino 4 (4,4)) `shouldBe`

[[3,3,2,2],

[3,1,1,2],

[4,1,5,5],

[4,4,5,-1]]

it "e2" $

toLists (triomino 4 (2,3)) `shouldBe`

[[3,3,2,2],

[3,1,-1,2],

[4,1,1,5],

[4,4,5,5]]

it "e3" $

toLists (triomino 16 (5,6)) `shouldBe`

[[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],

[7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],

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

[8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],

[8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],

[8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],

[9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],

[9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],

[8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],

[8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],

[9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],

[9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],

[9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],

[9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],

[10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],

[10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- e3

-- Finished in 0.0018 seconds

-- 3 examples, 0 failures

Soluciones en Python

import numpy as np
import numpy.typing as npt

from src.DivideVenceras import divideVenceras

# Los tableros son matrices de números enteros donde -1 representa el
# hueco, 0 las posiciones sin rellenar y los números mayores que 0
# representan los triominós.
Tablero = npt.NDArray[np.complex64]

# Los problemas se representarán mediante pares formados por un número
# natural mayor que 0 (que indica el número con el que se formará el
# siguiente triominó que se coloque) y un tablero.
Problema = tuple[int, Tablero]

# Las posiciones son pares de números enteros
Posicion = tuple[int, int]

# tablero(n p) es el tablero inicial del problema del triominó
# en un cuadrado nxn en el que se ha eliminado la casilla de la
# posición p. Por ejemplo,
#    >>> tablero(4, (3,4))
#    array([[ 0,  0,  0,  0],
#           [ 0,  0,  0,  0],
#           [ 0,  0,  0, -1],
#           [ 0,  0,  0,  0]])
def tablero(n: int, p: Posicion) -> Tablero:
    (i, j) = p
    q = np.zeros((n, n), dtype=int)
    q[i - 1, j - 1] = -1
    return q

# pbInicial(n, p) es el problema inicial del rompecabeza del triominó
# en un cuadrado nxn en el que se ha eliminado la casilla de la
# posición p. Por ejemplo,
#    >>> pbInicial(4, (4,4))
#    (1, array([[ 0,  0,  0,  0],
#           [ 0,  0,  0,  0],
#           [ 0,  0,  0,  0],
#           [ 0,  0,  0, -1]]))
def pbInicial(n: int, p: Posicion) -> Problema:
    return 1, tablero(n, p)

# ind(pb) se verifica si el problema pb es indivisible. Por ejemplo,
#    ind(pbInicial(2, (1,2)))  ==  True
#    ind(pbInicial(4, (1,2)))  ==  False
def ind(pb: Problema) -> bool:
    _, p = pb
    return p.shape[1] == 2

# posicionHueco(t) es la posición del hueco en el tablero t. Por
# ejemplo,
#    posicionHueco(tablero(8, (5,2)))  ==  (5,2)
def posicionHueco(t: Tablero) -> Posicion:
    indices = np.argwhere(t != 0)
    (i, j) =  tuple(indices[0])
    return (i + 1, j + 1)

# cuadranteHueco(p) es el cuadrante donde se encuentra el hueco del
# tablero t (donde la numeración de los cuadrantes es 1 el superior
# izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el
# inferior derecho). Por ejemplo,
#    cuadranteHueco(tablero(8, (4,4)))  ==  1
#    cuadranteHueco(tablero(8, (5,2)))  ==  2
#    cuadranteHueco(tablero(8, (3,6)))  ==  3
#    cuadranteHueco(tablero(8, (6,6)))  ==  4
def cuadranteHueco(t: Tablero) -> int:
    i, j = posicionHueco(t)
    x = t.shape[0] // 2
    if j <= x:
        if i <= x:
            return 1
        return 2
    if i <= x:
        return 3
    return 4

# centralHueco(t) es la casilla central del cuadrante del tablero t
# donde se encuentra el hueco. Por ejemplo,
#    centralHueco(tablero(8, (5,2)))  ==  (5,4)
#    centralHueco(tablero(8, (4,4)))  ==  (4,4)
#    centralHueco(tablero(8, (3,6)))  ==  (4,5)
#    centralHueco(tablero(8, (6,6)))  ==  (5,5)
def centralHueco(t: Tablero) -> Posicion:
    x = t.shape[0] // 2
    cuadrante = cuadranteHueco(t)
    if cuadrante == 1:
        return (x, x)
    if cuadrante == 2:
        return (x+1, x)
    if cuadrante == 3:
        return (x, x+1)
    return (x+1, x+1)

# centralesSinHueco(t) son las posiciones centrales del tablero t de
# los cuadrantes sin hueco. Por ejemplo,
#    centralesSinHueco(tablero(8, (5,2)))  ==  [(4,4),(4,5),(5,5)]
def centralesSinHueco(t: Tablero) -> list[Posicion]:
    x = t.shape[0] // 2
    i, j = centralHueco(t)
    ps = [(x, x), (x+1, x), (x, x+1), (x+1, x+1)]
    return [p for p in ps if p != (i, j)]

# actualiza(t, ps) es la matriz obtenida cambiando en t los valores del
# las posiciones indicadas en ps por sus correspondientes valores. Por
# ejemplo,
#    >>> actualiza(np.identity(3, dtype=int), [((1,2),4),((3,1),5)])
#    array([[1, 4, 0],
#           [0, 1, 0],
#           [5, 0, 1]])
def actualiza(p: Tablero, ps: list[tuple[Posicion, int]]) -> Tablero:
    for (i, j), x in ps:
        p[i - 1, j - 1] = x
    return p

# triominoCentral(n,t) es el tablero obtenido colocando el triominó
# formado por el número n en las posiciones centrales de los 3
# cuadrantes que no contienen el hueco. Por ejemplo,
#    >>> triominoCentral((7, tablero(4, (4,4))))
#    array([[ 0,  0,  0,  0],
#           [ 0,  7,  7,  0],
#           [ 0,  7,  0,  0],
#           [ 0,  0,  0, -1]])
def triominoCentral(p: Problema) -> Tablero:
    n, t = p
    return actualiza(t, [((i,j),n) for (i,j) in centralesSinHueco(t)])

# resuelve(p) es la solución del problema indivisible p. Por ejemplo,
#    >>> tablero(2, (2,2))
#    array([[ 0,  0],
#           [ 0, -1]])
#    >>> resuelve((5,tablero(2, (2,2))))
#    array([[ 5,  5],
#           [ 5, -1]])
def resuelve(p: Problema) -> Tablero:
    return triominoCentral(p)

# divide(n,t) es la lista de de los problemas obtenidos colocando el
# triominó n en las casillas centrales de t que no contienen el hueco y
# dividir el tablero en sus cuatros cuadrantes y aumentar en uno el
# número del correspondiente triominó. Por ejemplo,
#    >>> divide((3,tablero(4, (4,4))))
#    [(4, array([[0, 0],
#                [3, 0]])),
#     (5, array([[0, 0],
#                [0, 3]])),
#     (6, array([[0, 3],
#                [0, 0]])),
#     (7, array([[ 0,  0],
#                [ 0, -1]]))]
def divide(p: Problema) -> list[Problema]:
    q = triominoCentral(p)
    n, t = p
    m = t.shape[0]
    x = m // 2
    subproblemas = [
        (n+1, q[0:x, x:m]),
        (n+2, q[0:x, 0:x]),
        (n+3, q[x:m, 0:x]),
        (n+4, q[x:m, x:m])
    ]
    return subproblemas

# combina(p, ts) es la combinación de las soluciones ts de los
# subproblemas del problema p. Por ejemplo,
#    >>> inicial = (1, tablero(4, (4, 4)))
#    >>> p1, p2, p3, p4 = divide(inicial)
#    >>> s1, s2, s3, s4 = map(resuelve, [p1, p2, p3, p4])
#    >>> combina(inicial, [s1, s2, s3, s4])
#    array([[ 3,  3,  2,  2],
#           [ 3,  1,  1,  2],
#           [ 4,  1,  5,  5],
#           [ 4,  4,  5, -1]])
def combina(_: Problema, ts: list[Tablero]) -> Tablero:
    s1, s2, s3, s4 = ts
    combined = np.block([[s2, s1], [s3, s4]])
    return combined

def triomino(n: int, p: Posicion) -> Tablero:
    return divideVenceras(ind, resuelve, divide, combina, pbInicial(n, p))

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

def test_triomino() -> None:
    def filas(p: Tablero) -> list[list[int]]:
        return p.tolist()

    assert filas(triomino(4, (4,4))) == \
        [[3,3,2,2],[3,1,1,2],[4,1,5,5],[4,4,5,-1]]
    assert filas(triomino(4, (2,3))) == \
        [[3,3,2,2],[3,1,-1,2],[4,1,1,5],[4,4,5,5]]
    assert filas(triomino(16, (5,6))) == \
        [[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],
         [7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],
         [8,5,9,9,7,7,4,8,7,4,8,8,6,6,3,7],
         [8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],
         [8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],
         [8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],
         [9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],
         [9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],
         [8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],
         [8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],
         [9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],
         [9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],
         [9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],
         [9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],
         [10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],
         [10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]
    print("Verificado")

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

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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

import numpy as np

import numpy.typing as npt

from src.DivideVenceras import divideVenceras

# Los tableros son matrices de números enteros donde -1 representa el

# hueco, 0 las posiciones sin rellenar y los números mayores que 0

# representan los triominós.

Tablero = npt.NDArray[np.complex64]

# Los problemas se representarán mediante pares formados por un número

# natural mayor que 0 (que indica el número con el que se formará el

# siguiente triominó que se coloque) y un tablero.

Problema = tuple[int, Tablero]

# Las posiciones son pares de números enteros

Posicion = tuple[int, int]

# tablero(n p) es el tablero inicial del problema del triominó

# en un cuadrado nxn en el que se ha eliminado la casilla de la

# posición p. Por ejemplo,

# >>> tablero(4, (3,4))

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

# [ 0, 0, 0, 0],

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

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

def tablero(n: int, p: Posicion) -> Tablero:

(i, j) = p

q = np.zeros((n, n), dtype=int)

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

return q

# pbInicial(n, p) es el problema inicial del rompecabeza del triominó

# en un cuadrado nxn en el que se ha eliminado la casilla de la

# posición p. Por ejemplo,

# >>> pbInicial(4, (4,4))

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

# [ 0, 0, 0, 0],

# [ 0, 0, 0, -1]]))

def pbInicial(n: int, p: Posicion) -> Problema:

return 1, tablero(n, p)

# ind(pb) se verifica si el problema pb es indivisible. Por ejemplo,

# ind(pbInicial(2, (1,2))) == True

# ind(pbInicial(4, (1,2))) == False

def ind(pb: Problema) -> bool:

_, p = pb

return p.shape[1] == 2

# posicionHueco(t) es la posición del hueco en el tablero t. Por

# ejemplo,

# posicionHueco(tablero(8, (5,2))) == (5,2)

def posicionHueco(t: Tablero) -> Posicion:

indices = np.argwhere(t != 0)

(i, j) = tuple(indices[0])

return (i + 1, j + 1)

# cuadranteHueco(p) es el cuadrante donde se encuentra el hueco del

# tablero t (donde la numeración de los cuadrantes es 1 el superior

# izquierdo, 2 el inferior izquierdo, 3 el superior derecho y 4 el

# inferior derecho). Por ejemplo,

# cuadranteHueco(tablero(8, (4,4))) == 1

# cuadranteHueco(tablero(8, (5,2))) == 2

# cuadranteHueco(tablero(8, (3,6))) == 3

# cuadranteHueco(tablero(8, (6,6))) == 4

def cuadranteHueco(t: Tablero) -> int:

i, j = posicionHueco(t)

x = t.shape[0] // 2

if j <= x:

if i <= x:

return 1

return 2

if i <= x:

return 3

return 4

# centralHueco(t) es la casilla central del cuadrante del tablero t

# donde se encuentra el hueco. Por ejemplo,

# centralHueco(tablero(8, (5,2))) == (5,4)

# centralHueco(tablero(8, (4,4))) == (4,4)

# centralHueco(tablero(8, (3,6))) == (4,5)

# centralHueco(tablero(8, (6,6))) == (5,5)

def centralHueco(t: Tablero) -> Posicion:

x = t.shape[0] // 2

cuadrante = cuadranteHueco(t)

if cuadrante == 1:

return (x, x)

if cuadrante == 2:

return (x+1, x)

if cuadrante == 3:

return (x, x+1)

return (x+1, x+1)

# centralesSinHueco(t) son las posiciones centrales del tablero t de

# los cuadrantes sin hueco. Por ejemplo,

# centralesSinHueco(tablero(8, (5,2))) == [(4,4),(4,5),(5,5)]

def centralesSinHueco(t: Tablero) -> list[Posicion]:

x = t.shape[0] // 2

i, j = centralHueco(t)

ps = [(x, x), (x+1, x), (x, x+1), (x+1, x+1)]

return [p for p in ps if p != (i, j)]

# actualiza(t, ps) es la matriz obtenida cambiando en t los valores del

# las posiciones indicadas en ps por sus correspondientes valores. Por

# ejemplo,

# >>> actualiza(np.identity(3, dtype=int), [((1,2),4),((3,1),5)])

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

# [0, 1, 0],

# [5, 0, 1]])

def actualiza(p: Tablero, ps: list[tuple[Posicion, int]]) -> Tablero:

for (i, j), x in ps:

p[i - 1, j - 1] = x

return p

# triominoCentral(n,t) es el tablero obtenido colocando el triominó

# formado por el número n en las posiciones centrales de los 3

# cuadrantes que no contienen el hueco. Por ejemplo,

# >>> triominoCentral((7, tablero(4, (4,4))))

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

# [ 0, 7, 7, 0],

# [ 0, 7, 0, 0],

# [ 0, 0, 0, -1]])

def triominoCentral(p: Problema) -> Tablero:

n, t = p

return actualiza(t, [((i,j),n) for (i,j) in centralesSinHueco(t)])

# resuelve(p) es la solución del problema indivisible p. Por ejemplo,

# >>> tablero(2, (2,2))

# array([[ 0, 0],

# [ 0, -1]])

# >>> resuelve((5,tablero(2, (2,2))))

# array([[ 5, 5],

# [ 5, -1]])

def resuelve(p: Problema) -> Tablero:

return triominoCentral(p)

# divide(n,t) es la lista de de los problemas obtenidos colocando el

# triominó n en las casillas centrales de t que no contienen el hueco y

# dividir el tablero en sus cuatros cuadrantes y aumentar en uno el

# número del correspondiente triominó. Por ejemplo,

# >>> divide((3,tablero(4, (4,4))))

# [(4, array([[0, 0],

# [3, 0]])),

# (5, array([[0, 0],

# [0, 3]])),

# (6, array([[0, 3],

# [0, 0]])),

# (7, array([[ 0, 0],

# [ 0, -1]]))]

def divide(p: Problema) -> list[Problema]:

q = triominoCentral(p)

n, t = p

m = t.shape[0]

x = m // 2

subproblemas = [

(n+1, q[0:x, x:m]),

(n+2, q[0:x, 0:x]),

(n+3, q[x:m, 0:x]),

(n+4, q[x:m, x:m])

]

return subproblemas

# combina(p, ts) es la combinación de las soluciones ts de los

# subproblemas del problema p. Por ejemplo,

# >>> inicial = (1, tablero(4, (4, 4)))

# >>> p1, p2, p3, p4 = divide(inicial)

# >>> s1, s2, s3, s4 = map(resuelve, [p1, p2, p3, p4])

# >>> combina(inicial, [s1, s2, s3, s4])

# array([[ 3, 3, 2, 2],

# [ 3, 1, 1, 2],

# [ 4, 1, 5, 5],

# [ 4, 4, 5, -1]])

def combina(_: Problema, ts: list[Tablero]) -> Tablero:

s1, s2, s3, s4 = ts

combined = np.block([[s2, s1], [s3, s4]])

return combined

def triomino(n: int, p: Posicion) -> Tablero:

return divideVenceras(ind, resuelve, divide, combina, pbInicial(n, p))

# Verificación

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

def test_triomino() -> None:

def filas(p: Tablero) -> list[list[int]]:

return p.tolist()

assert filas(triomino(4, (4,4))) == \

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

assert filas(triomino(4, (2,3))) == \

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

assert filas(triomino(16, (5,6))) == \

[[7,7,6,6,6,6,5,5,6,6,5,5,5,5,4,4],

[7,5,5,6,6,4,4,5,6,4,4,5,5,3,3,4],

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

[8,8,9,3,3,7,8,8,7,7,8,2,2,6,7,7],

[8,8,7,3,9,-1,8,8,7,7,6,6,2,8,7,7],

[8,6,7,7,9,9,7,8,7,5,5,6,8,8,6,7],

[9,6,6,10,10,7,7,11,8,8,5,9,9,6,6,10],

[9,9,10,10,10,10,11,11,1,8,9,9,9,9,10,10],

[8,8,7,7,7,7,6,1,1,9,8,8,8,8,7,7],

[8,6,6,7,7,5,6,6,9,9,7,8,8,6,6,7],

[9,6,10,10,8,5,5,9,10,7,7,11,9,9,6,10],

[9,9,10,4,8,8,9,9,10,10,11,11,5,9,10,10],

[9,9,8,4,4,10,9,9,10,10,9,5,5,11,10,10],

[9,7,8,8,10,10,8,9,10,8,9,9,11,11,9,10],

[10,7,7,11,11,8,8,12,11,8,8,12,12,9,9,13],

[10,10,11,11,11,11,12,12,11,11,12,12,12,12,13,13]]

print("Verificado")

# La verificación es

# >>> test_triomino()

# Verificado

Algoritmo divide y vencerás

PorJosé A. Alonso 26-junio-202319-junio-2023

La técnica divide y vencerás consta de los siguientes pasos:

Dividir el problema en subproblemas menores.
Resolver por separado cada uno de los subproblemas:
- si los subproblemas son complejos, usar la misma técnica recursivamente;
- si son simples, resolverlos directamente.
Combinar todas las soluciones de los subproblemas en una solución simple.

Definir la función

   divideVenceras :: (p -> Bool)
                  -> (p -> s)
                  -> (p -> [p])
                  -> (p -> [s] -> s)
                  -> p
                  -> s

divideVenceras :: (p -> Bool)

-> (p -> s)

-> (p -> [p])

-> (p -> [s] -> s)

-> p

-> s

tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde

ind pb se verifica si el problema pb es indivisible
resuelve pb es la solución del problema indivisible pb
divide pb es la lista de subproblemas de pb
combina pb ss es la combinación de las soluciones ss de los subproblemas del problema pb.
pbInicial es el problema inicial

Usando la función DivideVenceras, definir las funciones

   ordenaPorMezcla :: Ord a => [a] -> [a]
   ordenaRapida    :: Ord a => [a] -> [a]

1 2	ordenaPorMezcla :: Ord a => [a] -> [a] ordenaRapida :: Ord a => [a] -> [a]

tales que

ordenaPorMezcla xs es la lista obtenida ordenando xs por el procedimiento de ordenación por mezcla. Por ejemplo,

     λ> ordenaPorMezcla [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

1 2	λ> ordenaPorMezcla [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]

ordenaRapida xs es la lista obtenida ordenando xs por el procedimiento de ordenación rápida. Por ejemplo,

     λ> ordenaRapida [3,1,4,1,5,9,2,8]
     [1,1,2,3,4,5,8,9]

1 2	λ> ordenaRapida [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9]

Soluciones

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

Soluciones en Haskell

module DivideVenceras (divideVenceras) where

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

divideVenceras :: (p -> Bool)
               -> (p -> s)
               -> (p -> [p])
               -> (p -> [s] -> s)
               -> p
               -> s
divideVenceras ind resuelve divide combina = dv'
  where
    dv' pb
      | ind pb    = resuelve pb
      | otherwise = combina pb [dv' sp | sp <- divide pb]

ordenaPorMezcla :: Ord a => [a] -> [a]
ordenaPorMezcla =
    divideVenceras ind id divide combina
    where
      ind xs            = length xs <= 1
      divide xs         = [take n xs, drop n xs]
                          where n = length xs `div` 2
      combina _ [l1,l2] = mezcla l1 l2

-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,
--    mezcla [1,3] [2,4,6]  ==  [1,2,3,4,6]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla [] b = b
mezcla a [] = a
mezcla a@(x:xs) b@(y:ys) | x <= y    = x : mezcla xs b
                         | otherwise = y : mezcla a ys

ordenaRapida :: Ord a => [a] -> [a]
ordenaRapida =
    divideVenceras ind id divide combina
    where
      ind xs                = length xs <= 1
      divide (x:xs)         = [[ y | y <- xs, y <= x],
                               [ y | y <- xs, y > x]]
      combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

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

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]
  it "e2" $
    ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

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

module DivideVenceras (divideVenceras) where

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

divideVenceras :: (p -> Bool)

-> (p -> s)

-> (p -> [p])

-> (p -> [s] -> s)

-> p

-> s

divideVenceras ind resuelve divide combina = dv'

where

dv' pb

| ind pb = resuelve pb

| otherwise = combina pb [dv' sp | sp <- divide pb]

ordenaPorMezcla :: Ord a => [a] -> [a]

ordenaPorMezcla =

divideVenceras ind id divide combina

where

ind xs = length xs <= 1

divide xs = [take n xs, drop n xs]

where n = length xs `div` 2

combina _ [l1,l2] = mezcla l1 l2

-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,

-- mezcla [1,3] [2,4,6] == [1,2,3,4,6]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla [] b = b

mezcla a [] = a

mezcla a@(x:xs) b@(y:ys) | x <= y = x : mezcla xs b

| otherwise = y : mezcla a ys

ordenaRapida :: Ord a => [a] -> [a]

ordenaRapida =

divideVenceras ind id divide combina

where

ind xs = length xs <= 1

divide (x:xs) = [[ y | y <- xs, y <= x],

[ y | y <- xs, y > x]]

combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

-- Verificación

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

verifica :: IO ()

verifica = hspec spec

spec :: Spec

spec = do

it "e1" $

ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

it "e2" $

ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]

-- La verificación es

-- λ> verifica

-- e1

-- e2

-- Finished in 0.0004 seconds

-- 2 examples, 0 failures

Soluciones en Python

from typing import Callable, TypeVar

P = TypeVar('P')
S = TypeVar('S')

def divideVenceras(ind: Callable[[P], bool],
                   resuelve: Callable[[P], S],
                   divide: Callable[[P], list[P]],
                   combina: Callable[[P, list[S]], S],
                   p: P) -> S:
    def dv(pb: P) -> S:
        if ind(pb):
            return resuelve(pb)
        return combina(pb, [dv(sp) for sp in divide(pb)])
    return dv(p)

def ordenaPorMezcla(xs: list[int]) -> list[int]:
    def ind(xs: list[int]) -> bool:
        return len(xs) <= 1

    def divide(xs: list[int]) -> list[list[int]]:
        n = len(xs) // 2
        return [xs[:n], xs[n:]]

    def combina(_: list[int], xs: list[list[int]]) -> list[int]:
        return mezcla(xs[0], xs[1])

    return divideVenceras(ind, lambda x: x, divide, combina, xs)

# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,
#    mezcla([1,3], [2,4,6]) == [1,2,3,4,6]
def mezcla(a: list[int], b: list[int]) -> list[int]:
    if not a:
        return b
    if not b:
        return a
    if a[0] <= b[0]:
        return [a[0]] + mezcla(a[1:], b)
    return [b[0]] + mezcla(a, b[1:])

def ordenaRapida(xs: list[int]) -> list[int]:
    def ind(xs: list[int]) -> bool:
        return len(xs) <= 1

    def divide(xs: list[int]) -> list[list[int]]:
        x, *xs = xs
        return [[y for y in xs if y <= x],
                [y for y in xs if y > x]]

    def combina(xs: list[int], ys: list[list[int]]) -> list[int]:
        x = xs[0]
        return ys[0] + [x] + ys[1]

    return divideVenceras(ind, lambda x: x, divide, combina, xs)

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

def test_divideVenceras() -> None:
    assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]
    assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]
    print("Verificado")

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

from typing import Callable, TypeVar

P = TypeVar('P')

S = TypeVar('S')

def divideVenceras(ind: Callable[[P], bool],

resuelve: Callable[[P], S],

divide: Callable[[P], list[P]],

combina: Callable[[P, list[S]], S],

p: P) -> S:

def dv(pb: P) -> S:

if ind(pb):

return resuelve(pb)

return combina(pb, [dv(sp) for sp in divide(pb)])

return dv(p)

def ordenaPorMezcla(xs: list[int]) -> list[int]:

def ind(xs: list[int]) -> bool:

return len(xs) <= 1

def divide(xs: list[int]) -> list[list[int]]:

n = len(xs) // 2

return [xs[:n], xs[n:]]

def combina(_: list[int], xs: list[list[int]]) -> list[int]:

return mezcla(xs[0], xs[1])

return divideVenceras(ind, lambda x: x, divide, combina, xs)

# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,

# mezcla([1,3], [2,4,6]) == [1,2,3,4,6]

def mezcla(a: list[int], b: list[int]) -> list[int]:

if not a:

return b

if not b:

return a

if a[0] <= b[0]:

return [a[0]] + mezcla(a[1:], b)

return [b[0]] + mezcla(a, b[1:])