I1M2011: Programa de cifras y letras en Haskell (1/2)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comenzado a desarrollar un programa en Haskell para resolver los problemas aritméticos del concurso Cifras y letras que consisten en dada una sucesión de números naturales y un número objetivo, intentar construir una expresión cuyo valor es el objetivo combinando los números de la sucesión usando suma, resta, multiplicación, división y paréntesis. Además, cada número de la sucesión puede usarse como máximo una vez y todos los números, incluyendo los resultados intermedios tienen que ser enteros positivos (1,2,3,…).
Por ejemplo, dada la sucesión 1, 3, 7, 10, 25, 50 y el objetivo 765, una solución es (1+50)*(25−10). Para el problema anterior existen 780 soluciones. En cambio, con la sucesión anterior y el objetivo 831, no hay solución.
En esta clase hemos estudiado cómo escribir un programa para resolver el problema por fuerza bruta. En la próxima estudiaremos cómo mejorar el programa.
El código del programa es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 |
-- --------------------------------------------------------------------- -- 2. Formalización del problema -- -- --------------------------------------------------------------------- -- Expresiones -- ----------- -- Las operaciones son sumar, restar, multiplicar o dividir. data Op = Sum | Res | Mul | Div deriving Eq instance Show Op where show Sum = "+" show Res = "-" show Mul = "*" show Div = "/" -- (valida o x y) se verifica si la operación o aplicada a los números -- náturales x e y da un número natural. Por ejemplo, -- valida Res 5 3 => True -- valida Res 3 5 => False -- valida Div 6 3 => True -- valida Div 6 4 => False valida :: Op -> Int -> Int -> Bool valida Sum _ _ = True valida Res x y = x > y valida Mul _ _ = True valida Div x y = x `mod` y == 0 -- (aplica o x y) es el resultado de aplicar la operación o a los -- números naturales x e y. Por ejemplo, -- aplica Sum 2 3 => 5 -- aplica Div 6 3 => 2 aplica :: Op -> Int -> Int -> Int aplica Sum x y = x + y aplica Res x y = x - y aplica Mul x y = x * y aplica Div x y = x `div` y -- Las expresiones son números enteros o aplicaciones de operaciones a -- dos expresiones. data Expr = Num Int | Apl Op Expr Expr deriving Eq instance Show Expr where show (Num n) = show n show (Apl o i d) = parentesis i ++ show o ++ parentesis d where parentesis (Num n) = show n parentesis e = "(" ++ show e ++ ")" -- Expresión correspondiente a (1+50)*(25−10) ejExpr :: Expr ejExpr = Apl Mul e1 e2 where e1 = Apl Sum (Num 1) (Num 50) e2 = Apl Res (Num 25) (Num 10) -- (numeros e) es la lista de los números que aparecen en la expresión -- e. Por ejemplo, -- numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) => [2,3,7] numeros :: Expr -> [Int] numeros (Num n) = [n] numeros (Apl _ l r) = numeros l ++ numeros r -- (valor e) es la lista formada por el valor de la expresión e si todas -- las operaciones para calcular el valor de e son números positivos y -- la lista vacía en caso contrario. Por ejemplo, -- valor (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) => [35] -- valor (Apl Res (Apl Sum (Num 2) (Num 3)) (Num 7)) => [] -- valor (Apl Sum (Apl Res (Num 2) (Num 3)) (Num 7)) => [] valor :: Expr -> [Int] valor (Num n) = [n | n > 0] valor (Apl o i d) = [aplica o x y | x <- valor i , y <- valor d , valida o x y] -- Funciones combinatorias -- ----------------------- -- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo, -- sublistas "bc" => ["","c","b","bc"] -- sublistas "abc" => ["","c","b","bc","a","ac","ab","abc"] sublistas :: [a] -> [[a]] sublistas [] = [[]] sublistas (x:xs) = yss ++ map (x:) yss where yss = sublistas xs -- (intercala x ys) es la lista de las listas obtenidas intercalando x -- entre los elementos de ys. Por ejemplo, -- intercala 'x' "bc" => ["xbc","bxc","bcx"] -- intercala 'x' "abc" => ["xabc","axbc","abxc","abcx"] intercala :: a -> [a] -> [[a]] intercala x [] = [[x]] intercala x (y:ys) = (x:y:ys) : map (y:) (intercala x ys) -- (permutaciones xs) es la lista de las permutaciones de xs. Por -- ejemplo, -- permutaciones "bc" => ["bc","cb"] -- permutaciones "abc" => ["abc","bac","bca","acb","cab","cba"] permutaciones :: [a] -> [[a]] permutaciones [] = [[]] permutaciones (x:xs) = concat (map (intercala x) (permutaciones xs)) -- (elecciones xs) es la lista formada por todas las sublistas de xs en -- cualquier orden. Por ejemplo, -- ghci> elecciones "abc" -- ["","c","b","bc","cb","a","ac","ca","ab","ba", -- "abc","bac","bca","acb","cab","cba"] elecciones :: [a] -> [[a]] elecciones xs = concat (map permutaciones (sublistas xs)) -- Formalización del problema -- -------------------------- -- (solucion e ns n) se verifica si la expresión e es una solución para -- la sucesión ns y objetivo n; es decir. si los números de e es una -- posible elección de ns y el valor de e es n. Por ejemplo, -- solucion ejExpr [1,3,7,10,25,50] 765 => True solucion :: Expr -> [Int] -> Int -> Bool solucion e ns n = elem (numeros e) (elecciones ns) && valor e == [n] -- --------------------------------------------------------------------- -- 3. Solución por fuerza bruta -- -- --------------------------------------------------------------------- -- (divisiones xs) es la lista de las divisiones de xs en dos listas no -- vacías. Por ejemplo, -- divisiones "bcd" => [("b","cd"),("bc","d")] -- divisiones "abcd" => [("a","bcd"),("ab","cd"),("abc","d")] divisiones :: [a] -> [([a],[a])] divisiones [] = [] divisiones [_] = [] divisiones (x:xs) = ([x],xs) : [(x:is,ds) | (is,ds) <- divisiones xs] -- (expresiones ns) es la lista de todas las expresiones constructibles -- a partir de la lista de números ns. Por ejemplo, -- ghci> expresiones [2,3,5] -- [2+(3+5),2-(3+5),2*(3+5),2/(3+5),2+(3-5),2-(3-5),2*(3-5),2/(3-5), -- 2+(3*5),2-(3*5),2*(3*5),2/(3*5),2+(3/5),2-(3/5),2*(3/5),2/(3/5), -- (2+3)+5,(2+3)-5,(2+3)*5,(2+3)/5,(2-3)+5,(2-3)-5,(2-3)*5,(2-3)/5, -- (2*3)+5,(2*3)-5,(2*3)*5,(2*3)/5,(2/3)+5,(2/3)-5,(2/3)*5,(2/3)/5] expresiones :: [Int] -> [Expr] expresiones [] = [] expresiones [n] = [Num n] expresiones ns = [e | (is,ds) <- divisiones ns , i <- expresiones is , d <- expresiones ds , e <- combina i d] -- (combina e1 e2) es la lista de las expresiones obtenidas combinando -- las expresiones e1 y e2 con una operación. Por ejemplo, -- combina (Num 2) (Num 3) => [2+3,2-3,2*3,2/3] combina :: Expr -> Expr -> [Expr] combina e1 e2 = [Apl o e1 e2 | o <- ops] -- ops es la lista de las operaciones. ops :: [Op] ops = [Sum,Res,Mul,Div] -- (soluciones ns n) es la lista de las soluciones para la sucesión ns y -- objetivo n calculadas por fuerza bruta. Por ejemplo, -- ghci> soluciones [1,3,7,10,25,50] 765 -- [3*((7*(50-10))-25), ((7*(50-10))-25)*3, ... -- ghci> :set +s -- ghci> head (soluciones [1,3,7,10,25,50] 765) -- 3*((7*(50-10))-25) -- (8.47 secs, 400306836 bytes) -- ghci> length (soluciones [1,3,7,10,25,50] 765) -- 780 -- (997.76 secs, 47074239120 bytes) -- ghci> length (soluciones [1,3,7,10,25,50] 831) -- 0 -- (1019.13 secs, 47074535420 bytes) -- ghci> :unset +s soluciones :: [Int] -> Int -> [Expr] soluciones ns n = [e | ns' <- elecciones ns , e <- expresiones ns' , valor e == [n]] |
Las transparencias usadas en la clase son desde la página 1 a la 12 del tema 11: