Tentative to solve "Le Compte est Bon" game in C.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
Bruno Raoult 26dc599d88 Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
.gitignore changed gen_reduced_trees() to match gen_tree() args 2 years ago
Makefile merged signal.c in timer.c 2 years ago
README.md Note about not use-able on Windows 2 years ago
REDUCE-TREES.txt clearer trees presentation 2 years ago
best.c Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
eval.c added timer for maxed calculation time. 2 years ago
lceb.c Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
lceb.h Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
oper.c Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
stack.c Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago
timer.c Ooops. 2 years ago
tree.c Suppression of "6 numbers" limit. New option to choose tree type. 2 years ago

README.md

lceb - a Countdown solver in C.

lceb will find the best solutions(s) for the Numbers part of the Countdown game "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

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

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:

$ make lceb

Usage

basic usage and output

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

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

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