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 = 24A few examples would be:

1 x 2 x 3 x 4 = 24 4 x 3 : 3 x 6 = 24 4 + 3 x 8 - 4 = 24No 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)

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) THENThis 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 78whereafter 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 143a 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,