% "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