% "Le compte est bon" in Haskell % Christophe Delord % 24 May 2018 License ======= This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/. Introduction ============ "Le compte est bon" (sorry, I don't know the english name of this game) is a game where the players have to take numbers and operations ($+$, $-$, $*$, $/$) and find a way to arrive to a given result. For instance, with 25, 50, 75, 100, 3 and 6 can you compute 952? Well this one is a bit difficult to find. Let's see if Haskell can find a solution. Operations ========== Let's define a type to represent operations. The type Expr is either a number (an integer) or an operation ($+$, $-$, $*$, $/$) with two operands. We can add a third data which is the result of the operation to avoid recalculating it several times. \begin{code} module Main where import Data.List import System.Environment import Control.Monad data Expr = Number Integer | Add Expr Expr Integer | Sub Expr Expr Integer | Mul Expr Expr Integer | Div Expr Expr Integer \end{code} The result of an operation is retrieved by val: \begin{code} val (Number x) = x val (Add _ _ x) = x val (Sub _ _ x) = x val (Mul _ _ x) = x val (Div _ _ x) = x \end{code} printOpts prints operations in a human readable way: \begin{code} printOps (Number n) = print n printOps e = (putStrLn . sh) e where sh (Number x) = "" sh (Add x y v) = sh' x ++ sh' y ++ show (val x) ++ " + " ++ show (val y) ++ " = " ++ show v sh (Sub x y v) = sh' x ++ sh' y ++ show (val x) ++ " - " ++ show (val y) ++ " = " ++ show v sh (Mul x y v) = sh' x ++ sh' y ++ show (val x) ++ " * " ++ show (val y) ++ " = " ++ show v sh (Div x y v) = sh' x ++ sh' y ++ show (val x) ++ " / " ++ show (val y) ++ " = " ++ show v sh' (Number _) = "" sh' e = sh e ++ "; " \end{code} Solver ====== The solver is quiet simple. It generates all the possible computations. They will later be filtered to keep the best one. A game is a list of expressions. Initially the game contains only numbers. Each step consists in taking two expressions and an operation and returning a new list with the new expression and the remaining ones. So a list with $N$ expressions will produce a list of lists with $N-1$ expressions, the first one being built from two expressions of the original list. Each produced list is a possible step from the initial list. \begin{code} steps :: [Expr] -> [[Expr]] steps es = [ e:es'' | (x, es' ) <- extract es , (y, es'') <- extract es' , e <- ops x y ] where extract [] = [] extract (e:es) = (e, es) : [ (e', e:es') | (e', es') <- extract es ] \end{code} We can now play "one step". We have now to play all the possible steps. The function steps' takes a list of games (a list of expression lists) and append all the possible steps from all the games. This way we recursively build a list with all the possible expressions reachable from the initial numbers. Thanks to lazyness, the generation will stop when a solution is found. \begin{code} steps' :: [[Expr]] -> [[Expr]] steps' [] = [] steps' ess = ess ++ steps' (concatMap steps ess) \end{code} There are some constraints on operations. ops takes two expressions and generates the possible expressions. Starting from $x$ and $y$ we generate: - $x+y$ if $x \ne 0 \land y \ne 0$ otherwise $x+y$ would not be a new number and the operation is useless. we also generate $x+y$ only if $x \ge y$ to avoid generating $x+y$ and $y+x$ which would double the number of expressions to test. - $x-y$ if $x \ne 0 \land y \ne 0$ otherwise $x-y$ would not be a new number and the operation is useless. we also generate $x-y$ only if $y \lt x$ to avoid generating $0$ or negative numbers. - $x*y$ if $x \gt 1 \land y \gt 1 \land x \ge y$ for the same reasons - $x/y$ if $x \gt 1 \land y \gt 1 \land y|x$ for obvious reasons too (the result of the division must be an integral number). When an expression is built, its value is also computed. \begin{code} ops :: Expr -> Expr -> [Expr] ops x y = [ Add x y (x' + y') | 0