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:

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,