I1M2018: Problema del concurso “Cifras y letras” en Haskell
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos desarrollado 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)x(25−10). Para el problema anterior existen 780 soluciones. En cambio, con la sucesión anterior y el objetivo 831, no hay solución.
Se empieza formalizando el problema y definiendo una función para reconcer las soluciones. A continuación, se presentan tres soluciones: la primera por fuerza bruta, la segunda mediante generación y evaluación y la tercera con simplificaciones algebraicas. Se termina con una comparación de las tres soluciones.
Los apuntes correspondientes a la clase son