👨💻 about me home CV/Resume 🖊️ Contact Github LinkedIn I’m a Haskeller 📝 Blog Freedom, privacy, tutorials… 🏆 Best of LuaX Calculadoira panda upp Haskell todo pwd TPG Nextcloud Git BitTorrent

Boycott the Football World Cup in Qatar in 2022.

No to pollution and the non-respect for the environment
(football in the desert is as fucking stupid as winter olympic games
where the snow does not fall).

No to the dictatorship of money and
the non-respect of basic human rights.

- Athletes, journalists, politicians, do not go there!
- Supporters, do not watch this masquerade on TV!
- Media, do not broadcast this ignominy!

- you contribute to the eradication of you and your descendants
- all mankind will hate you

It’s time to stop consuming and polluting for nothing. Earth is burning and there is no planet B (even Elon Musk won’t save you).

- stop flying for futile reasons
- stop driving large and polluting cars (ride bicycle instead)
- stop air conditioning
- stop watching stupid videos everywhere
- stop everything that is not necessary to our own survival
- stop stupid wars
- eat local vegetables instead of meat that travels all around the world
- try to be a bit more clever for once…

I’m so sad to see how stupid you human beings can
be.

What about fighting together against the apocalypse that
is coming very soon instead of shooting ourselves in the foot like
fools?

Hey fucking dude, wake up! Look up!

If you’re ready to make some efforts, you’re welcome to my website. Otherwise there is no hope…

💣
*Kick GAFAMs out*
(✔️ ~~ǝlƃooפ~~, ✔️ ~~ʞooqǝɔɐℲ~~, ✔️ ~~uozɐɯ∀~~): Stop giving
our soul and money to evils, be free and respectful!

🆕
**since December 2020**: Playing with the actor model in an
embedded multicore context. C imperative components become C stream pure
functions with no side effect ➡️ C low level programming with high
level pure functional programming properties 🏆

📰 **Saturday 30. January
2021**: Playing with Pandoc Lua filters in
Lua. panda is a lightweight
alternative to abp providing a
consistent set of Pandoc filters (text substitution, file inclusion,
diagrams, scripts, …).

🆕
**Sunday 24. May 2020**: Working at EasyMile for more than 5 years. Critical
real-time software in C, simulation and monitoring in Haskell ➡️ perfect combo! It’s
efficient and funny ;-)

🚌 And**we are
recruiting!** Contact
if you are interested in **Haskell** or **embedded
softwares** (or both).

🚌 And

24 May 2018

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/.

“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.

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.

```
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
```

The result of an operation is retrieved by `val`

:

```
Number x) = x
val (Add _ _ x) = x
val (Sub _ _ x) = x
val (Mul _ _ x) = x
val (Div _ _ x) = x val (
```

`printOpts`

prints operations in a human readable way:

```
Number n) = print n
printOps (= (putStrLn . sh) e
printOps e where sh (Number x) = ""
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' (= sh e ++ "; " sh' e
```

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.

```
steps :: [Expr] -> [[Expr]]
= [ e:es'' | (x, es' ) <- extract es
steps es <- extract es'
, (y, es'') <- ops x y
, e
]where
= []
extract [] :es) = (e, es) : [ (e', e:es') | (e', es') <- extract es ] extract (e
```

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.

```
steps' :: [[Expr]] -> [[Expr]]
= []
steps' [] = ess ++ steps' (concatMap steps ess) steps' ess
```

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.

```
ops :: Expr -> Expr -> [Expr]
= [ Add x y (x' + y') | 0<y', y'<=x' ] ++
ops x y Sub x y (x' - y') | 0<y', y'< x' ] ++
[ Mul x y (x' * y') | 1<y', y'<=x' ] ++
[ Div x y (x' `div` y') | 1<y', x' `mod` y' == 0 ]
[ where
= val x
x' = val y y'
```

The solver is finally a function that takes all the possible expressions that can be built from the initial numbers and filters to best ones. It records the best solutions encountered since the beginning of the list and emit the current one if it is closer to the expected number. When the expected number is found, the remaining expressions are ignored.

`solve`

take the number `n`

to find, the value
of the best solution encountered upto now (`best`

) and the
list of expressions (`e:es`

):

- if \(e=n\) then we found an exact solution. It is returned and the search stops here.
- if \(\lvert n-e \rvert \lt \lvert n-best \rvert\) then we found a better approximate solution. It is returned but the search continues.
- Other cases are worse solutions and are ignored.

The last item of the list returned by `solve`

is then the
best (or exact) solution.

As the solution candidates are generated in increasing size order, the first one that is found is also the one that requires the minimal number of operations.

```
:es) | val e == n = [e]
solve n best (e| abs (n - val e) < abs (n - best) = e : solve n (val e) es
| otherwise = solve n best es
= [] solve n best []
```

The `main`

function takes the initial values and the
target one. It uses `solve`

and prints all the expressions it
returns. The last one is the best solution.

```
= do
main <- getArgs
args let n = read $ last args
let ns = map read $ init args
let es = concat $ steps' [map Number ns]
putStrLn $ show n ++ " with " ++ show ns ++ " ?"
-n) es) printOps forM_ (solve n (
```

- How to find 102 with 25, 50, 75, 100, 3, 6 ? easy!

```
$ runhaskell compte.lhs 25 50 75 100 3 6 102
102 with [25,50,75,100,3,6] ?
25
50
75
100
100 + 3 = 103
50 / 25 = 2; 100 + 2 = 102
```

- How to find 952 with 25, 50, 75, 100, 3, 6 ???

```
$ runhaskell compte.lhs 25 50 75 100 3 6 952
952 with [25,50,75,100,3,6] ?
25
50
75
100
25 * 6 = 150
50 * 25 = 1250
25 - 3 = 22; 50 * 22 = 1100
25 - 6 = 19; 50 * 19 = 950
25 - 6 = 19; 50 * 19 = 950; 950 + 3 = 953
75 * 3 = 225; 100 + 6 = 106; 225 * 106 = 23850; 23850 - 50 = 23800; 23800 / 25 = 952
```

The Haskell source code is here: compte.lhs