142 lines
4.8 KiB
Markdown
142 lines
4.8 KiB
Markdown
# lceb - a Countdown solver in C.
|
||
|
||
`lceb` will find the best solutions(s) for the
|
||
[Numbers part of the Countdown game](https://en.wikipedia.org/wiki/Countdown_(game_show)#Numbers_round)
|
||
"[_Le compte est Bon_](https://fr.wikipedia.org/wiki/Des_chiffres_et_des_lettres#Le_Compte_est_Bon)" in French).
|
||
|
||
## Requisites
|
||
|
||
`lceb` has only been tested on `GNU/Linux` systems. It should not compile at all on `Windows`. I am not sure about `MacOS`.
|
||
|
||
## Get the source
|
||
|
||
``` text
|
||
git clone https://git.bodiccea.tk/bruno/Le-Compte-est-Bon.git
|
||
```
|
||
|
||
## Build
|
||
|
||
To display more debug information, you may first enable some DEBUG flags in the `Makefile`. I usually use the `-DDEBUG`, `-DDEBUG_MAIN`, and `-DDEBUG_MEM`, as below
|
||
|
||
```makefile
|
||
CFLAGS:=$(CFLAGS) -DDEBUG # general (signal handler, etc...)
|
||
CFLAGS:=$(CFLAGS) -DDEBUG_MAIN # general information in main
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_MAINSLEEP # sleep 1 sec within main loop (SIGINTR test)
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_MAINLOOP # main loop (do not use this!)
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_TIMER # timer
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_SIGNAL # signal
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_BEST # best control
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_TREE # tree
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_OPER # oper
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_STACK # stack
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_STACK2 # stack - more details
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_EVAL # eval
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_EVAL2 # eval 2
|
||
#CFLAGS:=$(CFLAGS) -DDEBUG_EVAL3 # eval 3
|
||
CFLAGS:=$(CFLAGS) -DDEBUG_MEM # malloc
|
||
```
|
||
|
||
To build the binaries just run:
|
||
```console
|
||
$ make lceb
|
||
```
|
||
|
||
## Usage
|
||
|
||
### basic usage and output
|
||
|
||
```console
|
||
$ ./lceb 2 7 1 7 8 8
|
||
timer started...
|
||
mem: allocating operators working area (5 bytes)
|
||
new_stack: allocating 1024 stacks
|
||
get_node: allocating 1024 new nodes - total nodes=1024
|
||
target assigned (2).
|
||
SIGINT armed.
|
||
stacks : 30
|
||
ops combinations: 256
|
||
trees : 14
|
||
max evaluations : 537,600
|
||
Le compte est bon: 5 solutions with 2 ops (1st after 0.00030 secs).
|
||
1 8 7 - +
|
||
1 8 8 / +
|
||
1 7 7 / +
|
||
1 8 + 7 -
|
||
8 7 1 - -
|
||
Total time elapsed: 0.01327 secs, nodes/leaves evaluated:401,817/397,973
|
||
```
|
||
`lceb` takes at least 3 arguments: target number (the one to find), and from 2 to 6 use-able numbers.
|
||
The solutions are displayed by default in RPN notation (here `1 8 7 - +` means `(8-7)+1`).
|
||
|
||
### options
|
||
|
||
You can see the available options with `lceb -h`:
|
||
```console
|
||
$ ./lceb -h
|
||
usage: ./lceb [options] target n1 n2 [...n6]
|
||
Countdown game solver.
|
||
-1: Show only one solution (immediate stop when exact solution found
|
||
-c: Show solutions timer
|
||
-d TYPE: Solutions display type. TYPE can be:
|
||
r: RPN (default)
|
||
p: Polish
|
||
l: Lisp (binary operators)
|
||
i: Infix (full parentheses)
|
||
d: Suitable for dc(1) input
|
||
t: Tree
|
||
-i: Show intermediate solutions
|
||
-s: Do not show summary (time, nodes evaluated)
|
||
-t: Use less trees (Wedderburn–Etherington instead of Catalan)
|
||
-T TIMER: Will stop after TIMER 1/10th seconds
|
||
-h: This help
|
||
```
|
||
|
||
### the -t option
|
||
|
||
Using `-t` gives a large performance boost. Compare the two output below :
|
||
|
||
```console
|
||
$ ./lceb -di -c 997 4 8 25 2 5 3
|
||
timer started...
|
||
mem: allocating operators working area (6 bytes)
|
||
new_stack: allocating 1024 stacks
|
||
get_node: allocating 1024 new nodes - total nodes=1024
|
||
target assigned (997).
|
||
SIGINT armed.
|
||
stacks : 720
|
||
ops combinations: 1,024
|
||
trees : 42
|
||
max evaluations : 185,794,560
|
||
get_node: allocating 1024 new nodes - total nodes=2048
|
||
get_node: allocating 1024 new nodes - total nodes=3072
|
||
get_node: allocating 1024 new nodes - total nodes=4096
|
||
get_node: allocating 1024 new nodes - total nodes=5120
|
||
Le compte est bon: 3 solutions with 3 ops (1st after 0.00841 secs).
|
||
0.00841 secs: (((5 * 8) * 25) - 3)
|
||
0.00841 secs: (((5 * 25) * 8) - 3)
|
||
0.00841 secs: (((8 * 25) * 5) - 3)
|
||
Total time elapsed: 3.40713 secs, nodes/leaves evaluated:138,979,332/132,474,697
|
||
```
|
||
|
||
```console
|
||
$ ./lceb -di -t -c 997 4 8 25 2 5 3
|
||
timer started...
|
||
mem: allocating operators working area (6 bytes)
|
||
new_stack: allocating 1024 stacks
|
||
get_node: allocating 1024 new nodes - total nodes=1024
|
||
target assigned (997).
|
||
SIGINT armed.
|
||
stacks : 720
|
||
ops combinations: 1,024
|
||
trees : 6
|
||
max evaluations : 26,542,080
|
||
get_node: allocating 1024 new nodes - total nodes=2048
|
||
Le compte est bon: 3 solutions with 3 ops (1st after 0.15392 secs).
|
||
0.15392 secs: (((5 * 8) * 25) - 3)
|
||
0.15392 secs: (((5 * 25) * 8) - 3)
|
||
0.15393 secs: (((8 * 25) * 5) - 3)
|
||
Total time elapsed: 0.47460 secs, nodes/leaves evaluated:18,793,369/18,650,735
|
||
```
|
||
|
||
It should be noted that having general performance improvement does not mean that the first solution will be found sooner.
|