{"id":2540,"date":"2013-02-26T17:43:10","date_gmt":"2013-02-26T17:43:10","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2540"},"modified":"2013-03-08T05:47:33","modified_gmt":"2013-03-08T05:47:33","slug":"i1m2012-problema-del-concurso-cifras-y-letras-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-problema-del-concurso-cifras-y-letras-en-haskell\/","title":{"rendered":"I1M2012: Problema del concurso “Cifras y letras” en Haskell"},"content":{"rendered":"

En la clase ayer y en la primera parte de la 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

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