{"id":1930,"date":"2012-03-06T19:32:54","date_gmt":"2012-03-06T19:32:54","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1930"},"modified":"2012-03-08T09:33:42","modified_gmt":"2012-03-08T09:33:42","slug":"i1m2011-programa-de-cifras-y-letras-en-haskell-12","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-programa-de-cifras-y-letras-en-haskell-12\/","title":{"rendered":"I1M2011: Programa de cifras y letras en Haskell (1\/2)"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comenzado a desarrollar 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

En esta clase hemos estudiado c\u00f3mo escribir un programa para resolver el problema por fuerza bruta. En la pr\u00f3xima estudiaremos c\u00f3mo mejorar el programa. <\/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-- 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-- (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-- (elecciones xs) es la lista formada por todas las sublistas de xs en\r\n-- cualquier orden. Por ejemplo,\r\n--    ghci> 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--   ghci> 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--    ghci> soluciones [1,3,7,10,25,50] 765\r\n--    [3*((7*(50-10))-25), ((7*(50-10))-25)*3, ...\r\n--    ghci> :set +s\r\n--    ghci> 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--    ghci> length (soluciones [1,3,7,10,25,50] 765)\r\n--    780\r\n--    (997.76 secs, 47074239120 bytes)\r\n--    ghci> length (soluciones [1,3,7,10,25,50] 831)\r\n--    0\r\n--    (1019.13 secs, 47074535420 bytes)\r\n--    ghci> :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<\/pre>\n
Las transparencias usadas en la clase son desde la p\u00e1gina 1 a la 12 del tema 11<\/a>:
\n