Musique & Mathématique

14 septembre 2012

Countdown problem solver

Filed under: Non classé — admin @ 14 h 00 min

Français English

Countdown problem solver

New version V 1.67

The countdown problem is a number game from the popular quiz program on French television (le Compte Est Bon) and on British television. Here is a program CEB able to solve quikly this kind of problem.

Download

The last version 1.67

(1) the C source is directly compilable with the GNU GCC, Borland TurboC or Microsoft VisualC++ compilers.

User manual

CEB is a program running in the console mode, the user interface is very simple and permit to be multi-platform (Dos, Windows, Unix) because all parameters are in the command line.

To execute this program with Windows XP, you should be launched CEB from the Dos windows activated with the Start->Execute menu, then enter ‘cmd’.

On line help :

> CEB -h
CEB a1 a2 a3 a4 a5 a6 [target] [options]       V 1.67
Solves a  'Countdown' or a 'Compte Est Bon'  problem.
The target must be fitted arithmetically with the six
arguments 'a1'..'a6' and the operators +, -, *, /, ^.
a1..a6    six numerical positive arguments.
[target]  target number to fit.
          When 'target' is not present CEB returns a
          statistics for the targets from 0 to 999.
[options] Permits to define some default parameters:
-aN       set the number of arguments to N   (default is 6)
-bP       set the begin limit for statistics (default is 0)
-d        prints debug information
-eP       set the end limit for statistics (default is 999)
-f        fractionnal numbers allowed
-g        global mode
-o        optimizes the number of arguments used
-s[+*-/e] set the allowed operators list  (default is +*-/)
-uP       using P arguments or less          (default is N)
-v        displays the solution        (multi-lines format)
-v1       displays the solution           (one-line format)
-wP       with P arguments or more           (default is 1)
-xP       search up to Pth unfit target        (no default)
Author:                                gilles.bannay@free.fr

Standard commands

Is it possible with the arguments 4 5 6 7 8 9 to fit 999 ?

> CEB 4 5 6 7 8 9 999
Solved !
Time = 0.0000 sec.

If yes, with how many arguments at least ?
‘-o’ option for optimization

> CEB 4 5 6 7 8 9 999 -o
Solved (with 6 args) !
Time = 0.0300 sec.

and what is the solution ?
‘-v’ option for verbose

> CEB 4 5 6 7 8 9 999 -o -v
5 + 4 = 9
8 * 6 = 48
7 * 9 = 63
48 + 63 = 111
9 * 111 = 999
Time = 0.0300 sec.

‘-v1′ option for verbose in one-line display

> CEB 4 5 6 7 8 9 999 -o -v1
((5 + 4) * ((8 * 6) + (7 * 9))) = 999
Time = 0.0300 sec.

We can launch the program before even knowing the target, to get statistics over all targets from 0 to 999:

> CEB 4 5 6 7 8 9
Unfit = 842 898 926 939 947
Success = 99.50%, 5 unfit in 0-999.
Mean time per target = 0.0001 sec.
Time = 0.1200 sec.

The six arguments can be out of the range of the standard game, we can pose for example the following problem:

> CEB 111 222 333 444 555 666 6666
Solved !
Time = 0.0100 sec.

Will you find a solution?? (I grant to you more than 0.0100 second).

> CEB 111 222 333 444 555 666 6666 -v
222 * 111 = 24642
666 * 555 = 369630
369630 + 333 = 369963
369963 * 444 = 164263572
164263572 / 24642 = 6666
Time = 0.0100 sec.

Extended commands

We can modify the number of arguments as well as the inf and sup for the statistics.
Example a problem with 7 arguments for the targets from 1000 to 9999 :
‘-a’ option for arguments number
‘-b’ option for begin
‘-e’ option for end

> CEB -a7 6 7 8 9 10 11 12 -b1000 -e9999
Unfit = 9105 9267 9538 9686 9914 9957
Success = 99.93%, 6 unfit in 1000-9999.
Mean time per target = 0.0006 sec.
Time = 5.8000 sec.

What is the second target which we cannot reach with twelve ‘ 1 ‘?
‘-x’ option for exclude

> CEB -a12 1 1 1 1 1 1 1 1 1 1 1 1 -x2
58 59
2nd unfit = 59.
Mean time per target = 0.0017 sec.
Time = 0.1000 sec.

Same thing but while starting to 62 (we can combine the options):

> CEB -a12 1 1 1 1 1 1 1 1 1 1 1 1 -x2 -b62
62 65
2nd unfit = 65.
Mean time per target = 0.0150 sec.
Time = 0.0600 sec.

To have an additional constraint, we can specify the maximum number of arguments to use, in the list of arguments. For example, can we make 100 with 1 2 3 4 5 6 using four arguments or less ?
‘-u’ option for using

> CEB 1 2 3 4 5 6 -u4 100
Solved !
Time = 0.0000 sec.

What is the first target which we cannot express using four different digits ?

> CEB -a9 1 2 3 4 5 6 7 8 9 -u4 -x1
298
1st unfit = 298.
Mean time per target = 0.0070 sec.
Time = 2.0900 sec.

What is the first target which we cannot express using four different digits and the operators +,-,*,/,^ (exponentiation) ?
‘-s’ option to define the operators list allowed (‘e’ for exponentiation)

> CEB -a9 1 2 3 4 5 6 7 8 9 -u4 -x1 -s+-*/e
417
1st unfit = 417.
Mean time per target = 0.0070 sec.
Time = 2.0900 sec.

Also, you can compose the previous options:
Here is the shortest expressions of numbers [0..20] using six arguments ’2′ and the operators +,-,*,/,^

> CEB -a6 2 2 2 2 2 2 -b0 -e20 -o -v1 -s+-*/e
(2 - 2) = 0
(2 / 2) = 1
(2) = 2
(2 + (2 / 2)) = 3
(2 + 2) = 4
((2 / 2) + (2 + 2)) = 5
(2 + (2 + 2)) = 6
((2 / 2) + (2 + (2 + 2))) = 7
(2 * (2 + 2)) = 8
((2 + (2 / 2)) ^ 2) = 9
(2 + (2 * (2 + 2))) = 10
(2 + ((2 + (2 / 2)) ^ 2)) = 11
(2 * (2 + (2 + 2))) = 12
((2 / 2) + (2 * (2 + (2 + 2)))) = 13
((2 ^ (2 + 2)) - 2) = 14
((2 ^ (2 + 2)) - (2 / 2)) = 15
(2 ^ (2 + 2)) = 16
((2 / 2) + (2 ^ (2 + 2))) = 17
(2 + (2 ^ (2 + 2))) = 18
((2 + ((2 + (2 + 2)) ^ 2)) / 2) = 19
(2 * (2 + (2 * (2 + 2)))) = 20
Success = 100.00%, 0 unfit in 0-20.
Mean time per target = 0.0000 sec.
Time = 0.0000 sec.

The same thing but with all the arguments:
‘-w’ option for with

> CEB -a6 2 2 2 2 2 2 -b0 -e20 -o -v1 -s+-*/e -w6
((2 - 2) * (2 + (2 + (2 + 2)))) = 0
((2 + (2 + (2 + 2))) ^ (2 - 2)) = 1
(((2 + (2 + (2 + 2))) / 2) - 2) = 2
(((2 + (2 + (2 + 2))) - 2) / 2) = 3
((2 + (2 + (2 + 2))) - (2 + 2)) = 4
((2 + (2 + (2 + (2 + 2)))) / 2) = 5
(2 + ((2 + (2 + (2 + 2))) / 2)) = 6
((2 + (2 + (2 + 2))) - (2 / 2)) = 7
((2 + (2 + (2 + (2 + 2)))) - 2) = 8
((2 / 2) + (2 + (2 + (2 + 2)))) = 9
(2 + (2 * ((2 + (2 + 2)) - 2))) = 10
((2 * (2 + (2 + 2))) - (2 / 2)) = 11
(2 + (2 + (2 + (2 + (2 + 2))))) = 12
((2 / 2) + (2 * (2 + (2 + 2)))) = 13
((2 * (2 + (2 + (2 + 2)))) - 2) = 14
((2 * (2 * (2 + 2))) - (2 / 2)) = 15
(2 ^ ((2 + (2 + (2 + 2))) / 2)) = 16
((((2 + (2 + 2)) ^ 2) - 2) / 2) = 17
(2 + (2 * (2 + (2 + (2 + 2))))) = 18
((2 + ((2 + (2 + 2)) ^ 2)) / 2) = 19
(2 * (2 + (2 + (2 + (2 + 2))))) = 20
Success = 100.00%, 0 unfit in 0-20.
Mean time per target = 0.0000 sec.
Time = 0.0000 sec

You can ask to solve a problem with fraction:
‘-f’ option to specify fraction request

> CEB -a4 1 5 6 7 21 -f -v
5 / 7 = 5/7
1 - 5/7 = 2/7
6 / 2/7 = 21

Time = 0.0000 sec.

The program prints in a detailed way all the tests which it carries out (very practical for the debug or the comprehension of the program)
Here is the printing in the simple problem « How to make 9 with six ’1′ ?
‘-d’ option for debug

> CEB 1 1 1 1 1 1 9 -d
1: 9 (6) 1     1     1     1     1     1
2: 9 (5)    2+    1     1     1     1
3: 9 (4)       3+    1     1     1
4: 9 (3)          4+    1     1
5: 9 (2)             5+    1
6: 9 (1)                6+
7: 9 (1)                4-
8: 9 (2)             3-    1
9: 9 (2)             4+    2+
10: 9 (1)               8*
11: 9 (2)            4+    0-
12: 9 (3)         2-    1     1
13: 9 (2)            2-    2+
14: 9 (1)               1/
15: 9 (2)            2-    0-
16: 9 (3)         3+    2+    1
17: 9 (2)            6*    1
18: 9 (1)               7+
19: 9 (1)               5-
20: 9 (2)            1-    1
21: 9 (2)            2+    4+
22: 9 (1)               8*
23: 9 (2)            2+    2-
24: 9 (1)               1/
25: 9 (2)            3+    3+
26: 9 (1)               9*
27: 9 (1)               9*
28: 9 (2)            3+    3+
29: 9 (3)         3+    2+    1
30: 9 (4)      3+    1     1     1
31: 9 (5)   2+    1     1     1     1
Possible !
Temps = 0.0000 sec.

Deep search

I added the -g option to allow the search  of the best n-uple (n1,..nk) which fits all the targets from 1 to Nk  (see  http://mathoverflow.net/questions/61034/optimal-countdown)
The search runs over all the n-uples (n1,..nk) < (m1,..mk), where (m1,..mk) is indicated in the command line, for example to get the best 4-uple, we can launch :

> CEB -g -b1 -e10000 -a4 4 8 80 80

and we find (2,3,14,60) solves all targets from 1 to 86.

♦       ♦


Pas de commentaire

Pas encore de commentaire.

Flux RSS des commentaires de cet article.

Désolé, les commentaires sont fermés pour le moment.

Powered by WordPress, QuickLaTeX