Divide y vencerás

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

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

Rompecabeza del triominó mediante divide y vencerás

Algoritmo divide y vencerás

Entradas recientes

Buscar

Correo electrónico