The 24 game

In the 90's the 24 game came to The Netherlands. In each bag of Smiths crisps was a round card containing 4 digits and you had to add the binary operators +, -, : or x (plus, minus, divide or times) such that the four digits plus three operators would validate the sum

`digit1 op1 digit2 op2 digit3 op3 digit4 = 24`
A few examples would be:
```1 x 2 x 3 x 4 = 24
4 x 3 : 3 x 6 = 24
4 + 3 x 8 - 4 = 24
```
No parenthesis allowed and the usual operator precedences "x and :" > "+ and -". No powers, no roots. Simple math.

Finding digit/operator combinations

So the first thing to do was to create a 24game-checker or -finder. And since I lack the brains to make a bombproof algorithm for this I decided to apply the brute force method:

• Four variables i, j, k, l for the digits
• Three operands op1, op2, op3
• Create all possible permutations for 4 x 9 digits and 3 x 4 operators
• Check each permutation if it yields the right answer (24)
Yes that is a lot of work. Yes it would make you stark crazy if you would attempt to do it yourself. But the computer won't mind if instructed appropriately.

The checking algorithm

The heart of the checker is the checking algorithm which must parse the formula in the mathematically correct order. The routine is relatively simple.

```CONST	min	  = 0;
plus 	  = 1;
times	  = 2;
divide	  = 3;

PROCEDURE  Test (a, b, c, d, op1, op2, op3  : INTEGER) : BOOLEAN;

VAR	u, v	: INTEGER;

BEGIN
Quit := FALSE;		(*  Quit is a global variable	*)
u := 0;
v := 0;
IF  (op2 DIV 2) > (op1 DIV 2)  THEN
u := Op (b, c, op2);
u := Op (u, d, op3);
u := Op (a, u, op1)
ELSE
u := Op (a, b, op1);
IF  (op3 DIV 2) > (op2 DIV 2)  THEN
v := Op (c, d, op3);
u := Op (u, v, op2)
ELSE
u := Op (u, c, op2);
u := Op (u, d, op3)
END
END;
IF  (u = targetVal) & (Quit = FALSE)  THEN  RETURN TRUE  ELSE  RETURN FALSE  END
END Test;
```
Why the Quit? It's never used! Yes it is but not in this section. Quit is used in the 'operation-center' Op (a, b, op) to signal an illegal condition and remember it for later processing. Illegal conditions are, for example, dividing 9 by 7 which in integer division equals '1' but in games like this 'are illegal'. For children, you cannot divide 9 by 7. 'Quit' signals these conditions. Quit also signals negative intermediate results.

First we check operation2 (the middle operation). Does it have a higher precedence than op1? If so we must delay op1 until the result of op2 is known. Something similar goes for op3 being greater than op2.

In the condition I use

`IF  (op2 DIV 2) > (op1 DIV 2)  THEN`
This way I make 'mutiply' and 'divide' equal to '2 DIV 2' and '3 DIV 2' which are both equal to '1' and the 'subtract/add' operators that end up at precedence '0' which makes precedence checking quite easy. In Modula-2 I would have reverted to a SET for this method but it would mean complicated operations on the set-elements. Now with the predefined and well chosen CONSTants the precedence checking gets quite simple.

Carrying out an operation

The following function carries out the operations. One function for all the possible operations. This makes easy work for exception checking (the Quit variable):

```PROCEDURE Op (x, y, op : INTEGER) : INTEGER;

VAR	t 	: INTEGER;

BEGIN
CASE  op  OF
min	 : t := x - y;
IF  t < 0  THEN  Quit := TRUE  END   |
plus  : t := x + y	|
times : t := x * y
ELSE
t := x DIV y;
IF  (x MOD y) # 0  THEN  Quit := TRUE  END
END;
RETURN t
END Op;
```
It's rather straightforward. No need for elaborate explanations I guess. Using the 'Op' function, the checking function becomes a lot more compact and easier to follow. No Spaghetti code in obc Oberon.

The source

Below is the full source of the 24game program. I had to call the source and module 'game24' since variables and symbols cannot start with anything else than an ASCII letter (A..Z).

```MODULE game24;

IMPORT	Args, Conv, Files, Strings;

CONST	min	  = 0;
plus 	  = 1;
times	  = 2;
divide	  = 3;

VAR	i, j, k, l	: INTEGER;
out		: Files.File;
Quit 		: BOOLEAN;
targetVal	: INTEGER;

PROCEDURE Op (x, y, op : INTEGER) : INTEGER;

VAR	t 	: INTEGER;

BEGIN
CASE  op  OF
min	 : t := x - y;
IF  t < 0  THEN  Quit := TRUE  END   |
plus  : t := x + y	|
times : t := x * y
ELSE
t := x DIV y;
IF  (x MOD y) # 0  THEN  Quit := TRUE  END
END;
RETURN t
END Op;

PROCEDURE  Test (a, b, c, d, op1, op2, op3  : INTEGER) : BOOLEAN;

VAR	u, v	: INTEGER;

BEGIN
Quit := FALSE;
u := 0;
v := 0;
IF  (op2 DIV 2) > (op1 DIV 2)  THEN
u := Op (b, c, op2);
u := Op (u, d, op3);
u := Op (a, u, op1)
ELSE
u := Op (a, b, op1);
IF  (op3 DIV 2) > (op2 DIV 2)  THEN
v := Op (c, d, op3);
u := Op (u, v, op2)
ELSE
u := Op (u, c, op2);
u := Op (u, d, op3)
END
END;
IF  (u = targetVal) & (Quit = FALSE)  THEN  RETURN TRUE  ELSE  RETURN FALSE  END
END Test;

PROCEDURE WriteOp (dest :  Files.File;  op  : INTEGER);

VAR	ch	: CHAR;

BEGIN
CASE  op  OF
0 : ch := '-'	|
1 : ch := '+'	|
2 : ch := 'x'	|
3 : ch := ':'
ELSE
ch := 'o'
END;
Files.WriteString (dest, "    ");
Files.WriteChar (dest, ch)
END WriteOp;

PROCEDURE Check24 (a, b, c, d	: INTEGER);

VAR	op1, op2, op3	: INTEGER;

BEGIN
FOR  op1 := min TO divide  DO
FOR  op2 := min TO divide  DO
FOR  op3 := min TO divide  DO
IF  Test (a, b, c, d, op1, op2, op3) = TRUE  THEN
Files.WriteInt (out, a, 4);
Files.WriteInt (out, b, 4);
Files.WriteInt (out, c, 4);
Files.WriteInt (out, d, 4);
WriteOp (out, op1);
WriteOp (out, op2);
WriteOp (out, op3);
Files.WriteLn (out)
END
END
END
END
END Check24;

PROCEDURE Init;

VAR	s, t	: ARRAY 16 OF CHAR;

BEGIN
IF  Args.argc = 2  THEN
Args.GetArg (1, s);
targetVal := Conv.IntVal (s)
ELSE
targetVal := 24
END;
s := "results.";
Conv.ConvInt (targetVal, t);
Strings.Append (t,s);
out := Files.Open (s, "w");
Files.WriteString (out, "   i   j   k   l  op1  op2  op3");	Files.WriteLn (out);
Files.WriteString (out, "  --- --- --- ---  -    -    -");	Files.WriteLn (out)
END Init;

BEGIN
Init;
FOR  i := 1  TO  9  DO
FOR  j := 1  TO  9  DO
FOR  k := 1  TO  9  DO
FOR  l := 1  TO  9  DO
Check24 (i, j, k, l)
END
END
END
END;
Files.Close (out)
END game24.
```
Now, that ain't no difficult source, or is it? The main loop is just four FOR loops, where each numerical combination is processed in Check24, where for this set of i, j, k and l, the three operations are added and each of them is checked for validity. If the combination is valid, it is written to file. This file is then used by other programs. The file has the name 'results' and the extension '.xx' where xx is the 'sumvalue'.

In 'Init' I check for possible commandline arguments. If there is one it must be the targetvalue. Initially the program would check for 24game values but, hey, this is a computer, it can do more things, so I created a variable (targetVal) that can be set on the commandline as in:

`Game24 78`
whereafter the program weeds out all illegal combinations and produces a file with all the valid i, j, k, l, op1, op2 and op3. If, for example, I would issue the command
`Game24 143`
a file called 'results.143' would be created, containing just 50 combinations. As you see below. Please feel free to check several values and report to me if one is off.

```   i   j   k   l   op1  op2  op3
--- --- --- ---   -    -    -
2   8   9   1    x    x    -
2   9   8   1    x    x    -
3   4   5   7    +    x    x
3   4   7   5    +    x    x
3   5   4   7    +    x    x
3   5   7   4    +    x    x
3   5   9   8    x    x    +
3   6   8   1    x    x    -
3   7   4   5    +    x    x
3   7   5   4    +    x    x
3   7   7   4    x    x    -
3   8   6   1    x    x    -
3   9   5   8    x    x    +
4   4   9   1    x    x    -
4   5   7   3    x    x    +
4   6   6   1    x    x    -
4   7   5   3    x    x    +
4   9   4   1    x    x    -
5   3   9   8    x    x    +
5   4   7   3    x    x    +
5   5   6   7    x    x    -
5   6   5   7    x    x    -
5   7   4   3    x    x    +
5   9   3   8    x    x    +
6   3   8   1    x    x    -
6   4   6   1    x    x    -
6   5   5   7    x    x    -
6   6   4   1    x    x    -
6   8   3   1    x    x    -
7   3   7   4    x    x    -
7   4   5   3    x    x    +
7   5   4   3    x    x    +
7   7   3   4    x    x    -
8   2   9   1    x    x    -
8   3   5   9    +    x    x
8   3   6   1    x    x    -
8   3   9   5    +    x    x
8   5   3   9    +    x    x
8   5   9   3    +    x    x
8   6   3   1    x    x    -
8   9   2   1    x    x    -
8   9   3   5    +    x    x
8   9   5   3    +    x    x
9   2   8   1    x    x    -
9   3   5   8    x    x    +
9   4   4   1    x    x    -
9   5   3   8    x    x    +
9   8   2   1    x    x    -
```

More to come soon

Page created 29 Feb 2020,