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:
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,