{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Tema 11: Aplicaciones de programación funcional\n", " \n", "\n", "----------\n", "\n", "[José A. Alonso](https://www.cs.us.es/~jalonso) \n", "[Departamento de Ciencias de la Computación e I.A.](https://www.cs.us.es) \n", "[Universidad de Sevilla](http://www.us.es) \n", "Sevilla, 7 de agosto de 2019" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Notas:__ \n", "+ La versión interactiva de este tema se encuentra en [Binder](https://mybinder.org/v2/gh/jaalonso/Temas_interactivos_de_PF_con_Haskell/master?urlpath=lab/tree/temas/Tema-11.ipynb).\n", "+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ ":opt no-lint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Librerías auxiliares**\n", "\n", "+ En este tema se usan las siguientes librerías:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import Data.List\n", "import Test.QuickCheck" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# El juego de cifras y letras" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introducción\n", "\n", "**Presentación del juego**\n", "\n", "+ *Cifras y letras* es un programa de Canal Sur que incluye un\n", " juego numérico.\n", "\n", "+ La esencia del juego es la siguiente: Dada una sucesión de números naturales\n", " y un número objetivo, intentar construir una expresión cuyo valor es el\n", " objetivo combinando los números de la sucesión usando suma, resta,\n", " multiplicación, división y paréntesis. Cada número de la sucesión puede\n", " usarse como máximo una vez. Además, todos los números, incluyendo los\n", " resultados intermedios tienen que ser enteros positivos (1,2,3,...).\n", "\n", "+ Ejemplos\n", " + Dada la sucesión 1, 3, 7, 10, 25, 50 y el objetivo 765, una solución\n", " es (1+50)*(25−10).\n", " + Para el problema anterior, existen 780 soluciones.\n", " + Con la sucesión anterior y el objetivo 831, no hay solución.\n", "\n", "**Formalización del problema: Operaciones**\n", "\n", "+ Las operaciones son sumar, restar, multiplicar o dividir." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "data Op = Sum | Res | Mul | Div \n", "\n", "instance Show Op where\n", " show Sum = \"+\"\n", " show Res = \"-\"\n", " show Mul = \"*\"\n", " show Div = \"/\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `ops` es la lista de las operaciones." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "ops :: [Op]\n", "ops = [Sum,Res,Mul,Div]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Operaciones válidas**\n", "\n", "+ `(valida o x y)` se verifica si la operación `o` aplicada a los números\n", " naturales `x` e `y` da un número natural. Por ejemplo,\n", "\n", "```sesion\n", "valida Res 5 3 == True\n", "valida Res 3 5 == False\n", "valida Div 6 3 == True\n", "valida Div 6 4 == False\n", "```" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "valida :: Op -> Int -> Int -> Bool\n", "valida Sum _ _ = True\n", "valida Res x y = x > y\n", "valida Mul _ _ = True\n", "valida Div x y = y /= 0 && x `mod` y == 0" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valida Res 5 3 " ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valida Res 3 5 " ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valida Div 6 3 " ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valida Div 6 4 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aplicación de operaciones**\n", "\n", "+ `(aplica o x y)` es el resultado de aplicar la operación `o` a los números\n", " naturales `x` e `y`. Por ejemplo,\n", "\n", "```sesion\n", "aplica Sum 2 3 == 5\n", "aplica Div 6 3 == 2\n", "```" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "aplica :: Op -> Int -> Int -> Int\n", "aplica Sum x y = x + y\n", "aplica Res x y = x - y\n", "aplica Mul x y = x * y\n", "aplica Div x y = x `div` y" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "aplica Sum 2 3 " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "aplica Div 6 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Expresiones**\n", "\n", "+ Las expresiones son números enteros o aplicaciones de operaciones a dos\n", " expresiones." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "data Expr = Num Int | Apl Op Expr Expr \n", "\n", "instance 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 ++ \")\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Ejemplo: Expresión correspondiente a (1+50)*(25−10)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "ejExpr :: Expr\n", "ejExpr = Apl Mul e1 e2\n", " where e1 = Apl Sum (Num 1) (Num 50)\n", " e2 = Apl Res (Num 25) (Num 10)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Números de una expresión**\n", "\n", "+ `(numeros e)` es la lista de los números que aparecen en la expresión\n", " `e`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) \n", "[2,3,7] \n", "```" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "numeros :: Expr -> [Int]\n", "numeros (Num n) = [n]\n", "numeros (Apl _ l r) = numeros l ++ numeros r" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2,3,7]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "numeros (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Valor de una expresión**\n", "\n", "+ `(valor e)` es la lista formada por el valor de la expresión `e` si todas las\n", " operaciones para calcular el valor de `e` son números positivos y la lista\n", " vacía en caso contrario. Por ejemplo,\n", "\n", "```sesion\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)) == []\n", "```" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "valor :: Expr -> [Int]\n", "valor (Num n) = [n | n > 0]\n", "valor (Apl o i d) = [aplica o x y | x <- valor i\n", " , y <- valor d\n", " , valida o x y]" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[35]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valor (Apl Mul (Apl Sum (Num 2) (Num 3)) (Num 7)) " ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valor (Apl Res (Apl Sum (Num 2) (Num 3)) (Num 7)) " ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "valor (Apl Sum (Apl Res (Num 2) (Num 3)) (Num 7)) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Funciones combinatorias: Sublistas**\n", "\n", "+ `(sublistas xs)` es la lista de las sublistas de `xs`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> sublistas \"bc\" \n", "[\"\",\"c\",\"b\",\"bc\"]\n", "ghci> sublistas \"abc\" \n", "[\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\n", "```" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "sublistas :: [a] -> [[a]]\n", "sublistas [] = [[]]\n", "sublistas (x:xs) = yss ++ map (x:) yss\n", " where yss = sublistas xs" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"\",\"c\",\"b\",\"bc\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sublistas \"bc\" " ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sublistas \"abc\" " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Funciones combinatoria: Intercalado**\n", "\n", "+ `(intercala x ys)` es la lista de las listas obtenidas intercalando `x` entre\n", " los elementos de `ys`. Por ejemplo,\n", "\n", "```sesion\n", "intercala 'x' \"bc\" == [\"xbc\",\"bxc\",\"bcx\"]\n", "intercala 'x' \"abc\" == [\"xabc\",\"axbc\",\"abxc\",\"abcx\"]\n", "```" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "intercala :: a -> [a] -> [[a]]\n", "intercala x [] = [[x]]\n", "intercala x (y:ys) = \n", " (x:y:ys) : map (y:) (intercala x ys)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"xbc\",\"bxc\",\"bcx\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "intercala 'x' \"bc\" " ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"xabc\",\"axbc\",\"abxc\",\"abcx\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "intercala 'x' \"abc\" " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Funciones combinatoria: Permutaciones**\n", "\n", "+ `(permutaciones xs)` es la lista de las permutaciones de `xs`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> permutaciones \"bc\" \n", "[\"bc\",\"cb\"]\n", "ghci> permutaciones \"abc\" \n", "[\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\n", "```" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "permutaciones :: [a] -> [[a]]\n", "permutaciones [] = [[]]\n", "permutaciones (x:xs) = \n", " concat (map (intercala x) (permutaciones xs))" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"bc\",\"cb\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "permutaciones \"bc\" " ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "permutaciones \"abc\" " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Funciones combinatoria: Elecciones**\n", "\n", "+ `(elecciones xs)` es la lista formada por todas las sublistas de `xs` en\n", " cualquier orden. Por ejemplo,\n", "\n", "```sesion\n", "ghci> elecciones \"abc\"\n", "[\"\",\"c\",\"b\",\"bc\",\"cb\",\"a\",\"ac\",\"ca\",\"ab\",\"ba\",\n", " \"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\n", "```" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "elecciones :: [a] -> [[a]]\n", "elecciones xs = \n", " concat (map permutaciones (sublistas xs))" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\"\",\"c\",\"b\",\"bc\",\"cb\",\"a\",\"ac\",\"ca\",\"ab\",\"ba\",\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "elecciones \"abc\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Reconocimiento de las soluciones**\n", "\n", "+ `(solucion e ns n)` se verifica si la expresión `e` es una solución para la\n", " sucesión `ns` y objetivo `n`; es decir. si los números de `e` es una posible\n", " elección de `ns` y el valor de `e` es `n`. Por ejemplo,\n", "\n", "```sesion\n", "solucion ejExpr [1,3,7,10,25,50] 765 == True\n", "```" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "solucion :: Expr -> [Int] -> Int -> Bool\n", "solucion e ns n = \n", " elem (numeros e) (elecciones ns) && valor e == [n]" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "solucion ejExpr [1,3,7,10,25,50] 765" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Búsqueda de la solución por fuerza bruta\n", "\n", "**Divisiones de una lista**\n", "\n", "+ `(divisiones xs)` es la lista de las divisiones de `xs` en dos listas no\n", " vacías. Por ejemplo,\n", "\n", "```sesion\n", "ghci> divisiones \"bcd\" \n", "[(\"b\",\"cd\"),(\"bc\",\"d\")]\n", "ghci> divisiones \"abcd\" \n", "[(\"a\",\"bcd\"),(\"ab\",\"cd\"),(\"abc\",\"d\")]\n", "```" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [], "source": [ "divisiones :: [a] -> [([a],[a])]\n", "divisiones [] = []\n", "divisiones [_] = []\n", "divisiones (x:xs) = \n", " ([x],xs) : [(x:is,ds) | (is,ds) <- divisiones xs]" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(\"b\",\"cd\"),(\"bc\",\"d\")]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "divisiones \"bcd\" " ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(\"a\",\"bcd\"),(\"ab\",\"cd\"),(\"abc\",\"d\")]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "divisiones \"abcd\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Combinación de expresiones**\n", "\n", "+ `(combina e1 e2)` es la lista de las expresiones obtenidas combinando las\n", " expresiones `e1` y `e2` con una operación. Por ejemplo,\n", "\n", "```sesion\n", "ghci> combina (Num 2) (Num 3) \n", "[2+3,2-3,2*3,2/3] \n", "```" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "combina :: Expr -> Expr -> [Expr]\n", "combina e1 e2 = [Apl o e1 e2 | o <- ops]" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2+3,2-3,2*3,2/3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "combina (Num 2) (Num 3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Expresiones construibles**\n", "\n", "+ `(expresiones ns)` es la lista de todas las expresiones construibles a partir\n", " de la lista de números `ns`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> expresiones [2,3,5]\n", "[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),\n", " 2+(3/5),2-(3/5),2*(3/5),2/(3/5),(2+3)+5,(2+3)-5,\n", " ...\n", "```" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "expresiones :: [Int] -> [Expr]\n", "expresiones [] = []\n", "expresiones [n] = [Num n]\n", "expresiones ns = [e | (is,ds) <- divisiones ns\n", " , i <- expresiones is\n", " , d <- expresiones ds\n", " , e <- combina i d]" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[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]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "expresiones [2,3,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Búsqueda de las soluciones**\n", "\n", "+ `(soluciones ns n)` es la lista de las soluciones para la sucesión `ns` y\n", " objetivo `n` calculadas por fuerza bruta. Por ejemplo,\n", "\n", "```sesion\n", "ghci> soluciones [1,3,7,10,25,50] 765\n", "[3*((7*(50-10))-25), ((7*(50-10))-25)*3, ...\n", "ghci> length (soluciones [1,3,7,10,25,50] 765)\n", "780\n", "ghci>\n", "length (soluciones [1,3,7,10,25,50] 831)\n", "0\n", "```" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [], "source": [ "soluciones :: [Int] -> Int -> [Expr]\n", "soluciones ns n = [e | ns' <- elecciones ns\n", " , e <- expresiones ns'\n", " , valor e == [n]]" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*((7*(50-10))-25)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "head (soluciones [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones [1,3,7,10,25,50] 831)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Estadísticas de la búsqueda por fuerza bruta**\n", "\n", "+ Estadísticas:\n", "\n", "```sesion\n", "ghci> :set +s\n", "ghci> head (soluciones [1,3,7,10,25,50] 765)\n", "3*((7*(50-10))-25)\n", "(8.47 secs, 400306836 bytes)\n", "ghci> length (soluciones [1,3,7,10,25,50] 765)\n", "780\n", "(997.76 secs, 47074239120 bytes)\n", "ghci> length (soluciones [1,3,7,10,25,50] 831)\n", "0\n", "(1019.13 secs, 47074535420 bytes)\n", "ghci> :unset +s\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Búsqueda combinando generación y evaluación\n", "\n", "**Resultados**\n", "\n", "+ `Resultado` es el tipo de los pares formados por expresiones válidas y su\n", " valor." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type Resultado = (Expr,Int) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Combinación de resultados**\n", "\n", "+ `(combina' r1 r2)` es la lista de los resultados obtenidos combinando los\n", " resultados `r1` y `r2` con una operación. Por ejemplo,\n", "\n", "```sesion\n", "ghci> combina' (Num 2,2) (Num 3,3) \n", "[(2+3,5),(2*3,6)]\n", "ghci> combina' (Num 3,3) (Num 2,2) \n", "[(3+2,5),(3-2,1),(3*2,6)]\n", "ghci> combina' (Num 2,2) (Num 6,6) \n", "[(2+6,8),(2*6,12)]\n", "ghci> combina' (Num 6,6) (Num 2,2) \n", "[(6+2,8),(6-2,4),(6*2,12),(6/2,3)]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina' :: Resultado -> Resultado -> [Resultado]\n", "combina' (i,x) (d,y) = \n", " [(Apl o i d, aplica o x y) | o <- ops\n", " , valida o x y] " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina' (Num 2,2) (Num 3,3) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina' (Num 3,3) (Num 2,2) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina' (Num 2,2) (Num 6,6) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina' (Num 6,6) (Num 2,2) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `(resultados ns)` es la lista de todos los resultados construibles a partir\n", " de la lista de números `ns`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> 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)]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "resultados :: [Int] -> [Resultado]\n", "resultados [] = []\n", "resultados [n] = [(Num n,n) | n > 0]\n", "resultados ns = [res | (is,ds) <- divisiones ns\n", " , ix <- resultados is\n", " , dy <- resultados ds\n", " , res <- combina' ix dy]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "resultados [2,3,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Búsqueda combinando generación y evaluación**\n", "\n", "+ `(soluciones' ns n)` es la lista de las soluciones para la sucesión `ns` y\n", " objetivo `n` calculadas intercalando generación y evaluación. Por ejemplo,\n", "\n", "```sesion\n", "ghci> head (soluciones' [1,3,7,10,25,50] 765)\n", "3*((7*(50-10))-25)\n", "ghci> length (soluciones' [1,3,7,10,25,50] 765)\n", "780\n", "ghci> length (soluciones' [1,3,7,10,25,50] 831)\n", "0\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "soluciones' :: [Int] -> Int -> [Expr]\n", "soluciones' ns n = [e | ns' <- elecciones ns\n", " , (e,m) <- resultados ns'\n", " , m == n]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "head (soluciones' [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones' [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones' [1,3,7,10,25,50] 831)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Estadísticas de la búsqueda combinada**\n", "\n", "+ Estadísticas:\n", "\n", "```sesion\n", "ghci> head (soluciones' [1,3,7,10,25,50] 765)\n", "3*((7*(50-10))-25)\n", "(0.81 secs, 38804220 bytes)\n", "ghci> length (soluciones' [1,3,7,10,25,50] 765)\n", "780\n", "(60.73 secs, 2932314020 bytes)\n", "ghci> length (soluciones' [1,3,7,10,25,50] 831)\n", "0\n", "(61.68 secs, 2932303088 bytes)\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Búsqueda mejorada mediante propiedades algebraicas\n", "\n", "**Aplicaciones válidas**\n", "\n", "+ `(valida' o x y)` se verifica si la operación `o` aplicada a los números\n", " naturales `x` e `y` da un número natural, teniendo en cuenta las siguientes\n", " reducciones algebraicas\n", "\n", "```sesion\n", "x + y = y + x\n", "x * y = y * x\n", "x * 1 = x\n", "1 * y = y\n", "x / 1 = x\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "valida' :: Op -> Int -> Int -> Bool\n", "valida' Sum x y = x <= y\n", "valida' Res x y = x > y\n", "valida' Mul x y = x /= 1 && y /= 1 && x <= y\n", "valida' Div x y = y /= 0 && y /= 1 && x `mod` y == 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Combinación de resultados válidos**\n", "\n", "+ `(combina'' r1 r2)` es la lista de los resultados válidos obtenidos\n", " combinando los resultados `r1` y `r2` con una operación. Por ejemplo,\n", "\n", "```sesion\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)]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina'' :: Resultado -> Resultado -> [Resultado]\n", "combina'' (i,x) (d,y) = \n", " [(Apl o i d, aplica o x y) | o <- ops\n", " , valida' o x y]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina'' (Num 2,2) (Num 3,3) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina'' (Num 3,3) (Num 2,2) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina'' (Num 2,2) (Num 6,6) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "combina'' (Num 6,6) (Num 2,2) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Resultados válidos construibles**\n", "\n", "+ `(resultados' ns)` es la lista de todos los resultados válidos construibles a\n", " partir de la lista de números `ns`. Por ejemplo,\n", "\n", "```sesion\n", "ghci> resultados' [5,3,2]\n", "[(5-(3-2),4),((5-3)+2,4),((5-3)*2,4),((5-3)/2,1)]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "resultados' :: [Int] -> [Resultado]\n", "resultados' [] = []\n", "resultados' [n] = [(Num n,n) | n > 0]\n", "resultados' ns = [res | (is,ds) <- divisiones ns\n", " , ix <- resultados' is\n", " , dy <- resultados' ds\n", " , res <- combina'' ix dy]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "resultados' [5,3,2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Búsqueda mejorada mediante propiedades algebraicas**\n", "\n", "+ `(soluciones'' ns n)` es la lista de las soluciones para la sucesión `ns` y\n", " objetivo `n` calculadas intercalando generación y evaluación y usando las\n", " mejoras aritméticas. Por ejemplo,\n", "\n", "```sesion\n", "ghci> head (soluciones'' [1,3,7,10,25,50] 765)\n", "3*((7*(50-10))-25)\n", "ghci> length (soluciones'' [1,3,7,10,25,50] 765)\n", "49\n", "ghci> length (soluciones'' [1,3,7,10,25,50] 831)\n", "0\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "soluciones'' :: [Int] -> Int -> [Expr]\n", "soluciones'' ns n = [e | ns' <- elecciones ns\n", " , (e,m) <- resultados' ns'\n", " , m == n]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "head (soluciones'' [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones'' [1,3,7,10,25,50] 765)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "length (soluciones'' [1,3,7,10,25,50] 831)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Estadísticas de la búsqueda mejorada**\n", "\n", "+ Estadísticas:\n", "\n", "```sesion\n", "ghci> head (soluciones'' [1,3,7,10,25,50] 765)\n", "3*((7*(50-10))-25)\n", "(0.40 secs, 16435156 bytes)\n", "ghci> length (soluciones'' [1,3,7,10,25,50] 765)\n", "49\n", "(10.30 secs, 460253716 bytes)\n", "ghci> length (soluciones'' [1,3,7,10,25,50] 831)\n", "0\n", "(10.26 secs, 460253908 bytes)§\n", "```\n", "\n", "**Comparación de las búsquedas**\n", "\n", "+ **Caso 1**: Comparación de las búsquedad problema de dados [1,3,7,10,25,50]\n", " obtener 765.\n", "\n", "+ Búsqueda de la primera solución:\n", "\n", "```sesion\n", " +---------------------+\n", " | segs. | bytes |\n", "+--------------+-------+-------------+ \n", "| soluciones | 8.47 | 400.306.836 |\n", "| soluciones' | 0.81 | 38.804.220 |\n", "| soluciones'' | 0.40 | 16.435.156 |\n", "+--------------+-------+-------------+\n", "```\n", "\n", "+ Búsqueda de todas las soluciones:\n", "\n", "```sesion\n", " +--------+----------------+\n", " | segs. | bytes |\n", "+--------------+--------+----------------+ \n", "| soluciones | 997.76 | 47.074.239.120 |\n", "| soluciones' | 60.73 | 2.932.314.020 |\n", "| soluciones'' | 10.30 | 460.253.716 |\n", "+--------------+--------+----------------+\n", "```\n", "\n", "\n", "+ **Caso 2**: Comprobación de que dados [1,3,7,10,25,50] no puede obtenerse 831 \n", "\n", "```sesion\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", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# El problema de las reinas\n", "\n", "+ Enunciado: Colocar N reinas en un tablero rectangular de dimensiones N\n", " por N de forma que no se encuentren más de una en la misma línea:\n", " horizontal, vertical o diagonal.\n", "\n", "+ El tablero se representa por una lista de números que indican las filas\n", " donde se han colocado las reinas. Por ejemplo, `[3,5]` indica que se\n", " han colocado las reinas `(1,3)` y `(2,5)`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "type Tablero = [Int]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `noAtaca r rs d` se verifica si la reina `r` no ataca a ninguna de las de la\n", " lista `rs` donde la primera de la lista está a una distancia horizontal `d`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "noAtaca :: Int -> Tablero -> Int -> Bool\n", "noAtaca _ [] _ = True\n", "noAtaca r (a:rs) distH = abs(r-a) /= distH &&\n", " noAtaca r rs (distH+1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `reinas n` es la lista de soluciones del problema de las N reinas.\n", " Por ejemplo, `reinas 4` == `[[3,1,4,2],[2,4,1,3]]`. \n", " La primera solución `[3,1,4,2]` se interpreta como \n", "\n", "```sesion\n", "|---|---|---|---|\n", "| | R | | |\n", "|---|---|---|---|\n", "| | | | R |\n", "|---|---|---|---|\n", "| R | | | |\n", "|---|---|---|---|\n", "| | | R | |\n", "|---|---|---|---|\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "reinas :: Int -> [Tablero]\n", "reinas n = aux n\n", " where aux 0 = [[]]\n", " aux m = [r:rs | rs <- aux (m-1),\n", " r <- ([1..n] \\\\ rs),\n", " noAtaca r rs 1]" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "reinas 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Números de Hamming\n", "\n", "+ Enunciado: Los números de Hamming forman una sucesión estrictamente\n", " creciente de números que cumplen las siguientes condiciones:\n", "\n", "+ El número 1 está en la sucesión.\n", "\n", "+ Si x está en la sucesión, entonces 2x, 3x y 5x también están.\n", "\n", "+ Ningún otro número está en la sucesión. \n", "\n", "+ `mezcla2 xs ys zs` es la lista obtenida mezclando las listas ordenadas `xs` e\n", " `ys` y eliminando los elementos duplicados. Por ejemplo,\n", "\n", "```sesion\n", "ghci> mezcla2 [2,4,6,8,10,12] [3,6,9,12]\n", "[2,3,4,6,8,9,10,12]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "mezcla2 :: [Int] -> [Int] -> [Int]\n", "mezcla2 p@(x:xs) q@(y:ys) | x < y = x:mezcla2 xs q\n", " | x > y = y:mezcla2 p ys \n", " | otherwise = x:mezcla2 xs ys\n", "mezcla2 [] ys = ys\n", "mezcla2 xs [] = xs" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "mezcla2 [2,4,6,8,10,12] [3,6,9,12]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `mezcla3 xs ys zs` es la lista obtenida mezclando las listas ordenadas `xs`,\n", " `ys` y `zs` y eliminando los elementos duplicados. Por ejemplo,\n", "\n", "```sesion\n", "ghci> mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]\n", "[2,3,4,5,6,8,9,10,12]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "mezcla3 :: [Int] -> [Int] -> [Int] -> [Int]\n", "mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs) " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ `hamming` es la sucesión de Hamming. Por ejemplo,\n", "\n", "```sesion\n", "take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "hamming :: [Int]\n", "hamming = 1 : mezcla3 [2*i | i <- hamming] \n", " [3*i | i <- hamming] \n", " [5*i | i <- hamming] " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "take 12 hamming" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bibliografía\n", "\n", "+ G. Hutton. *Programming in Haskell*. Cambridge University Press, 2007.\n", " + Cap. 11: The countdown problem.\n", "\n", "+ B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. *Razonando con\n", " Haskell*. Thompson, 2004.\n", " + Cap. 13: Puzzles y solitarios." ] } ], "metadata": { "kernelspec": { "display_name": "Haskell", "language": "haskell", "name": "haskell" }, "language_info": { "codemirror_mode": "ihaskell", "file_extension": ".hs", "name": "haskell", "pygments_lexer": "Haskell", "version": "8.6.5" } }, "nbformat": 4, "nbformat_minor": 4 }