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.