{"id":4145,"date":"2014-02-18T17:58:16","date_gmt":"2014-02-18T16:58:16","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4145"},"modified":"2016-01-09T18:20:11","modified_gmt":"2016-01-09T17:20:11","slug":"i1m2013-problema-del-concurso-cifras-y-letras-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-problema-del-concurso-cifras-y-letras-en-haskell\/","title":{"rendered":"I1M2013: Problema del concurso “Cifras y letras” en Haskell"},"content":{"rendered":"

En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos desarrollado un programa en Haskell para resolver los problemas aritm\u00e9ticos del concurso Cifras y letras<\/i> que consisten en dada una sucesi\u00f3n de n\u00fameros naturales y un n\u00famero objetivo, intentar construir una expresi\u00f3n cuyo valor es el objetivo combinando los n\u00fameros de la sucesi\u00f3n usando suma, resta, multiplicaci\u00f3n, divisi\u00f3n y par\u00e9ntesis. Adem\u00e1s, cada n\u00famero de la sucesi\u00f3n puede usarse como m\u00e1ximo una vez y todos los n\u00fameros, incluyendo los resultados intermedios tienen que ser enteros positivos (1,2,3,…).<\/p>\n

Por ejemplo, dada la sucesi\u00f3n 1, 3, 7, 10, 25, 50 y el objetivo 765, una soluci\u00f3n es (1+50)*(25\u221210). Para el problema anterior existen 780 soluciones. En cambio, con la sucesi\u00f3n anterior y el objetivo 831, no hay soluci\u00f3n.<\/p>\n

Se empieza formalizando el problema y definiendo una funci\u00f3n para reconcer las soluciones. A continuaci\u00f3n, se presentan tres soluciones: la primera por fuerza bruta, la segunda mediante generaci\u00f3n y evaluaci\u00f3n y la tercera con simplificaciones algebraicas. Se termina con una comparaci\u00f3n de las tres soluciones.<\/p>\n

El c\u00f3digo del programa es
\n<\/p>\n

\n-- ---------------------------------------------------------------------\n-- 2. Formalizaci\u00f3n del problema                                      --\n-- ---------------------------------------------------------------------\n\n-- Expresiones\n-- -----------\n\n-- Las operaciones son sumar, restar, multiplicar o dividir.\ndata Op = Sum | Res | Mul | Div\n          deriving Eq\n\ninstance Show Op where\n   show Sum = \"+\"\n   show Res = \"-\"\n   show Mul = \"*\"\n   show Div = \"\/\"\n\n-- (valida o x y) se verifica si la operaci\u00f3n o aplicada a los n\u00fameros\n-- n\u00e1turales x e y da un n\u00famero natural. Por ejemplo,\n--    valida Res 5 3  ==  True\n--    valida Res 3 5  ==  False\n--    valida Div 6 3  ==  True\n--    valida Div 6 4  ==  False\nvalida :: Op -> Int -> Int -> Bool\nvalida Sum _ _ = True\nvalida Res x y = x > y\nvalida Mul _ _ = True\nvalida Div x y = x `mod` y == 0\n\n-- (aplica o x y) es el resultado de aplicar la operaci\u00f3n o a los\n-- n\u00fameros naturales x e y. Por ejemplo,\n--    aplica Sum 2 3  ==  5\n--    aplica Div 6 3  ==  2\naplica :: Op -> Int -> Int -> Int\naplica Sum x y = x + y\naplica Res x y = x - y\naplica Mul x y = x * y\naplica Div x y = x `div` y\n\n-- Otra definici\u00f3n de aplica es\naplica' :: Op -> Int -> Int -> Int\naplica' Sum = (+)\naplica' Res = (-)\naplica' Mul = (*)\naplica' Div = div\n\n\n-- Las expresiones son n\u00fameros enteros o aplicaciones de operaciones a\n-- dos expresiones.\ndata Expr = Num Int | Apl Op Expr Expr\n            deriving Eq\n\ninstance Show Expr where\n   show (Num n)     = show n\n   show (Apl o i d) = parentesis i ++ show o ++ parentesis d\n                      where\n                         parentesis (Num n) = show n\n                         parentesis e       = \"(\" ++ show e ++ \")\"\n\n-- Expresi\u00f3n correspondiente a (1+50)*(25\u221210)\nejExpr :: Expr\nejExpr =  Apl Mul e1 e2\n    where e1 = Apl Sum (Num 1) (Num 50)\n          e2 = Apl Res (Num 25) (Num 10)\n\n-- (numeros e) es la lista de los n\u00fameros que aparecen en la expresi\u00f3n\n-- e. Por ejemplo,\n--    numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7))  ==  [2,3,7]\nnumeros :: Expr -> [Int]\nnumeros (Num n)     = [n]\nnumeros (Apl _ l r) = numeros l ++ numeros r\n\n-- (valor e) es la lista formada por el valor de la expresi\u00f3n e si todas\n-- las operaciones para calcular el valor de e son n\u00fameros positivos y\n-- la lista vac\u00eda en caso contrario. Por ejemplo,\n--    valor (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7))  ==  [35]\n--    valor (Apl Res (Apl Sum (Num 2) (Num 3)) (Num 7))  ==  []\n--    valor (Apl Sum (Apl Res (Num 2) (Num 3)) (Num 7))  ==  []\nvalor :: Expr -> [Int]\nvalor (Num n)     = [n | n > 0]\nvalor (Apl o i d) = [aplica o x y | x <- valor i\n                                  , y <- valor d\n                                  , valida o x y]\n\n-- Funciones combinatorias\n-- -----------------------\n\n-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,\n--    sublistas \"bc\"   ==  [\"\",\"c\",\"b\",\"bc\"]\n--    sublistas \"abc\"  ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\nsublistas :: [a] -> [[a]]\nsublistas []     = [[]]\nsublistas (x:xs) = yss ++ map (x:) yss\n    where yss = sublistas xs\n\n-- Puede definirse usando la  predefinida subsequences (aunque el orden de los  \n-- elementos es distinto).\nsublistas' :: [a] -> [[a]]\nsublistas' = subsequences\n\n-- (intercala x ys) es la lista de las listas obtenidas intercalando x\n-- entre los elementos de ys. Por ejemplo,\n--    intercala 'x' \"bc\"  ==  [\"xbc\",\"bxc\",\"bcx\"]\n--    intercala 'x' \"abc\"  ==  [\"xabc\",\"axbc\",\"abxc\",\"abcx\"]\nintercala :: a -> [a] -> [[a]]\nintercala x []     = [[x]]\nintercala x (y:ys) = (x:y:ys) : map (y:) (intercala x ys)\n\n-- (permutaciones xs) es la lista de las permutaciones de xs. Por\n-- ejemplo, \n--    permutaciones \"bc\"   ==  [\"bc\",\"cb\"]\n--    permutaciones \"abc\"  ==  [\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\npermutaciones :: [a] -> [[a]]\npermutaciones []     = [[]]\npermutaciones (x:xs) = concat (map (intercala x) (permutaciones xs))\n\n-- Puede definirse usando la  predefinida permutations (aunque el orden de los\n-- elementos es distinto).\npermutaciones' :: [a] -> [[a]]\npermutaciones' = permutations\n\n-- (elecciones xs) es la lista formada por todas las sublistas de xs en\n-- cualquier orden. Por ejemplo,\n--    *Main> elecciones \"abc\"\n--    [\"\",\"c\",\"b\",\"bc\",\"cb\",\"a\",\"ac\",\"ca\",\"ab\",\"ba\",\n--     \"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\nelecciones :: [a] -> [[a]]\nelecciones xs = concat (map permutaciones (sublistas xs))\n\n-- Formalizaci\u00f3n del problema\n-- --------------------------\n\n-- (solucion e ns n) se verifica si la expresi\u00f3n e es una soluci\u00f3n para\n-- la sucesi\u00f3n ns y objetivo n; es decir. si los n\u00fameros de e es una\n-- posible elecci\u00f3n de ns y el valor de e es n. Por ejemplo,\n--    solucion ejExpr [1,3,7,10,25,50] 765  ==  True\nsolucion :: Expr -> [Int] -> Int -> Bool\nsolucion e ns n = elem (numeros e) (elecciones ns) && valor e == [n]\n\n-- ---------------------------------------------------------------------\n-- 3. Soluci\u00f3n por fuerza bruta                                       --\n-- ---------------------------------------------------------------------\n\n-- (divisiones xs) es la lista de las divisiones de xs en dos listas no\n-- vac\u00edas. Por ejemplo,\n--    divisiones \"bcd\"   ==  [(\"b\",\"cd\"),(\"bc\",\"d\")]\n--    divisiones \"abcd\"  ==  [(\"a\",\"bcd\"),(\"ab\",\"cd\"),(\"abc\",\"d\")]\ndivisiones :: [a] -> [([a],[a])]\ndivisiones []     = []\ndivisiones [_]    = []\ndivisiones (x:xs) = ([x],xs) : [(x:is,ds) | (is,ds) <- divisiones xs]\n\n-- (expresiones ns) es la lista de todas las expresiones constructibles\n-- a partir de la lista de n\u00fameros ns. Por ejemplo,\n--   *Main> expresiones [2,3,5]\n--   [2+(3+5),2-(3+5),2*(3+5),2\/(3+5),2+(3-5),2-(3-5),2*(3-5),2\/(3-5),\n--    2+(3*5),2-(3*5),2*(3*5),2\/(3*5),2+(3\/5),2-(3\/5),2*(3\/5),2\/(3\/5),\n--    (2+3)+5,(2+3)-5,(2+3)*5,(2+3)\/5,(2-3)+5,(2-3)-5,(2-3)*5,(2-3)\/5,\n--    (2*3)+5,(2*3)-5,(2*3)*5,(2*3)\/5,(2\/3)+5,(2\/3)-5,(2\/3)*5,(2\/3)\/5]\nexpresiones :: [Int] -> [Expr]\nexpresiones []  = []\nexpresiones [n] = [Num n]\nexpresiones ns  = [e | (is,ds) <- divisiones ns\n                     , i       <- expresiones is\n                     , d       <- expresiones ds\n                     , e       <- combina i d]\n\n-- (combina e1 e2) es la lista de las expresiones obtenidas combinando\n-- las expresiones e1 y e2 con una operaci\u00f3n. Por ejemplo,\n--    combina (Num 2) (Num 3)  ==  [2+3,2-3,2*3,2\/3]\ncombina :: Expr -> Expr -> [Expr]\ncombina e1 e2 = [Apl o e1 e2 | o <- ops]\n\n-- ops es la lista de las operaciones. \nops :: [Op]\nops = [Sum,Res,Mul,Div]\n\n-- (soluciones ns n) es la lista de las soluciones para la sucesi\u00f3n ns y\n-- objetivo n calculadas por fuerza bruta. Por ejemplo, \n--    *Main> soluciones [1,3,7,10,25,50] 765\n--    [3*((7*(50-10))-25), ((7*(50-10))-25)*3, ...\n--    *Main> :set +s\n--    *Main> head (soluciones [1,3,7,10,25,50] 765)\n--    3*((7*(50-10))-25)\n--    (8.47 secs, 400306836 bytes)\n--    *Main> length (soluciones [1,3,7,10,25,50] 765)\n--    780\n--    (997.76 secs, 47074239120 bytes)\n--    *Main> length (soluciones [1,3,7,10,25,50] 831)\n--    0\n--    (1019.13 secs, 47074535420 bytes)\n--    *Main> :unset +s\nsoluciones :: [Int] -> Int -> [Expr]\nsoluciones ns n =  [e | ns' <- elecciones ns\n                      , e   <- expresiones ns'\n                      , valor e == [n]]\n\n-- ---------------------------------------------------------------------\n-- 4. Combinando generaci\u00f3n y evaluaci\u00f3n                              --\n-- ---------------------------------------------------------------------\n\n-- Resultado es el tipo de los pares formados por expresiones v\u00e1lidas y\n-- su valor.\ntype Resultado = (Expr,Int)\n\n-- (resultados ns) es la lista de todos los resultados constructibles\n-- a partir de la lista de n\u00fameros ns. Por ejemplo,\n--    *Main> resultados [2,3,5]\n--    [(2+(3+5),10), (2*(3+5),16), (2+(3*5),17), (2*(3*5),30), ((2+3)+5,10), \n--     ((2+3)*5,25), ((2+3)\/5,1),  ((2*3)+5,11), ((2*3)-5,1),  ((2*3)*5,30)]\nresultados :: [Int] -> [Resultado]\nresultados []  = []\nresultados [n] = [(Num n,n) | n > 0]\nresultados ns  = [res | (is,ds) <- divisiones ns\n                      , ix      <- resultados is\n                      , dy      <- resultados ds\n                      , res     <- combina' ix dy]\n\n-- (combina' r1 r2) es la lista de los resultados obtenidos combinando\n-- los resultados r1 y r2 con una operaci\u00f3n. Por ejemplo,\n--    combina' (Num 2,2) (Num 3,3)  ==  [(2+3,5),(2*3,6)]\n--    combina' (Num 3,3) (Num 2,2)  ==  [(3+2,5),(3-2,1),(3*2,6)]\n--    combina' (Num 2,2) (Num 6,6)  ==  [(2+6,8),(2*6,12)]\n--    combina' (Num 6,6) (Num 2,2)  ==  [(6+2,8),(6-2,4),(6*2,12),(6\/2,3)]\ncombina' :: Resultado -> Resultado -> [Resultado]\ncombina' (i,x) (d,y) =  [(Apl o i d, aplica o x y) | o <- ops\n                                                   , valida o x y] \n\n-- (soluciones' ns n) es la lista de las soluciones para la sucesi\u00f3n ns y\n-- objetivo n calculadas intercalando generaci\u00f3n y evaluaci\u00f3n. Por\n-- ejemplo,  \n--    *Main> head (soluciones' [1,3,7,10,25,50] 765)\n--    3*((7*(50-10))-25)\n--    (0.81 secs, 38804220 bytes)\n--    *Main> length (soluciones' [1,3,7,10,25,50] 765)\n--    780\n--    (60.73 secs, 2932314020 bytes)\n--    *Main> length (soluciones' [1,3,7,10,25,50] 831)\n--    0\n--    (61.68 secs, 2932303088 bytes)\nsoluciones' :: [Int] -> Int -> [Expr]\nsoluciones' ns n = [e | ns'   <- elecciones ns\n                      , (e,m) <- resultados ns'\n                      , m == n]\n\n-- ---------------------------------------------------------------------\n-- 5. Mejora mediante propiedades algebraicas                         --\n-- ---------------------------------------------------------------------\n\n-- (valida' o x y) se verifica si la operaci\u00f3n o aplicada a los n\u00fameros\n-- n\u00e1turales x e y da un n\u00famero natural, teniendo en cuenta las\n-- siguientes reducciones aritm\u00e9ticas \n--    x + y = y + x\n--    x * y = y * x\n--    x * 1 = x\n--    1 * y = y\n--    x \/ 1 = x\n-- Por ejemplo,\n--    valida' Sum 2 3  ==  True\n--    valida' Sum 3 2  ==  False\n--    valida' Res 3 2  ==  True\n--    valida' Res 2 3  ==  False\n--    valida' Mul 1 3  ==  False\n--    valida' Mul 3 1  ==  False\n--    valida' Mul 2 3  ==  True\n--    valida' Mul 3 2  ==  False\n--    valida' Div 3 1  ==  False\n--    valida' Div 3 2  ==  False\n--    valida' Div 4 2  ==  True\nvalida' :: Op -> Int -> Int -> Bool\nvalida' Sum x y = x <= y\nvalida' Res x y = x > y\nvalida' Mul x y = x \/= 1 && y \/= 1 && x <= y\nvalida' Div x y = y \/= 1 && x `mod` y == 0\n\n-- (resultados' ns) es la lista de todos los resultados v\u00e1lidos\n-- constructibles a partir de la lista de n\u00fameros ns. Por ejemplo,\n--    *Main> resultados [5,3,2]\n--    [(5+(3+2),10), (5*(3+2),25), (5\/(3+2),1), (5+(3-2),6), (5-(3-2),4),\n--     (5*(3-2),5),  (5\/(3-2),5),  (5+(3*2),11),(5*(3*2),30),((5+3)+2,10),\n--     ((5+3)-2,6),  ((5+3)*2,16), ((5+3)\/2,4), ((5-3)+2,4), ((5-3)*2,4),\n--     ((5-3)\/2,1),  ((5*3)+2,17), ((5*3)-2,13), ((5*3)*2,30)]\n--    *Main> resultados' [5,3,2]\n--    [(5-(3-2),4),((5-3)+2,4),((5-3)*2,4),((5-3)\/2,1)]\nresultados' :: [Int] -> [Resultado]\nresultados' []  = []\nresultados' [n] = [(Num n,n) | n > 0]\nresultados' ns  = [res | (is,ds) <- divisiones ns\n                       , ix      <- resultados' is\n                       , dy      <- resultados' ds\n                       , res     <- combina'' ix dy]\n\n-- (combina'' r1 r2) es la lista de los resultados v\u00e1lidos obtenidos\n-- combinando los resultados r1 y r2 con una operaci\u00f3n. Por ejemplo,\n--    combina'' (Num 2,2) (Num 3,3)  ==  [(2+3,5),(2*3,6)]\n--    combina'' (Num 3,3) (Num 2,2)  ==  [(3-2,1)]\n--    combina'' (Num 2,2) (Num 6,6)  ==  [(2+6,8),(2*6,12)]\n--    combina'' (Num 6,6) (Num 2,2)  ==  [(6-2,4),(6\/2,3)]\ncombina'' :: Resultado -> Resultado -> [Resultado]\ncombina'' (i,x) (d,y) = \n    [(Apl o i d, aplica o x y) | o <- ops\n                               , valida' o x y]\n\n-- (soluciones'' ns n) es la lista de las soluciones para la sucesi\u00f3n ns y\n-- objetivo n calculadas intercalando generaci\u00f3n y evaluaci\u00f3n y usando\n-- las mejoras aritm\u00e9ticas. Por ejemplo,  \n--    *Main> head (soluciones'' [1,3,7,10,25,50] 765)\n--    3*((7*(50-10))-25)\n--    (0.40 secs, 16435156 bytes)\n--    *Main> length (soluciones'' [1,3,7,10,25,50] 765)\n--    49\n--    (10.30 secs, 460253716 bytes)\n--    *Main> length (soluciones'' [1,3,7,10,25,50] 831)\n--    0\n--    (10.26 secs, 460253908 bytes)\nsoluciones'' :: [Int] -> Int -> [Expr]\nsoluciones'' ns n = [e | ns'   <- elecciones ns\n                       , (e,m) <- resultados' ns'\n                       , m == n]\n\n{-\nComparaci\u00f3n para el problema [1,3,7,10,25,50] 765 \n                  +---------------------+-------------------------+\n                  | Primera soluci\u00f3n    | Todas soluciones        |  \n                  +-------+-------------+--------+----------------+\n                  | segs. | byte  s     | segs.  | bytes          |\n   +--------------+-------+-------------+--------+----------------+ \n   | soluciones   | 8.47  | 400.306.836 | 997.76 | 47.074.239.120 |\n   | soluciones'  | 0.81  |  38.804.220 |  60.73 |  2.932.314.020 |\n   | soluciones'' | 0.40  |  16.435.156 |  10.30 |    460.253.716 |\n   +--------------+-------+-------------+--------+----------------+\n\nComparaci\u00f3n para el problema [1,3,7,10,25,50] 831\n                  +--------------------------+\n                  | No tiene soluciones      |\n                  +---------+----------------+\n                  | segs.   | bytes          |\n   +--------------+---------+----------------+ \n   | soluciones   | 1019.13 | 47.074.535.420 |\n   | soluciones'  |   61.68 |  2.932.303.088 |\n   | soluciones'' |   10.26 |    460.253.908 |\n   +--------------+---------+----------------+\n-}\n<\/pre>\n
Las transparencias usadas en la clase son desde la p\u00e1gina 1 a la 35 del tema 11<\/a>:
\n