# Solving the game of 24 recursively in APL

Posted on

Problem

The “game of 24” as I called it in the title is a maths game in which you are given four numbers and have to combine them in an expression using only the four basic arithmetic operations `+`, `-`, `×` and `÷` (and possibly using parenthesis) to achieve the final result of `24`. You must use each digit exactly once.

For example, if the numbers were `1 2 3 4` the answer could be `1×2×3×4` or `(1+2+3)×4`.

I set to write a solver for this game in APL (which eventually led to this blog post) which I wanted to be general enough to handle any amount of input numbers and any target number (so not necessarily only `24` as target number). The recursive algorithm I used is fairly simple and has a brute-force nature: pick two numbers from the available `N` numbers in all the different ways I can do that and then combine them with all the available operations, applying the same function recursively to the several sets of `N-1` numbers.

I am not only interested in knowing if I can get to a target number but I also want to know how to get there, so while I do all these manipulations, I also keep track of how to get to the available numbers by writing prefix expressions with the numbers used. E.g. if at some point I have the numbers `1 2 3 4`, I will have a matching string representation of `'1' '2' '3' '4'`. If then I use addition to merge `1` and `2`, the new set of numbers is `3 3 4` and the matching representation changes to `'+ 1 2' '3' '4'`.

This is the simple namespace I created:

``````:Namespace GameOf24
⍝ Generalized solver for the "game of 24".

Solve←{
⍝ Dyadic function to find ways of building ⍺ with the numbers in ⍵
(reprs values)←Combine⊂⍵
}

Combine←{
⍝ Recursive dyadic function combining the numbers ⍵ which have been obtained by the expressions ⍺
⎕DIV←1
⍺←⍕¨¨⍵ ⍝ default string representations of input numbers
1=l←≢⊃⍵: ⍺ ⍵  ⍝ if no more numbers to combine, return
U ← { ⍝ unpack pairs of nested results
⊃{(wl wr)←⍵ ⋄ (al ar)←⍺ ⋄ (al,wl)(ar,wr)}/⍵
}
C ← { ⍝ Combine two numbers of ⍵ with the dyadic function in ⍺
(r v) ← ⍵
(li ri) ← ↓⍉idx⌿⍨sub← ≠v[idx]
newv ← v[li] (⍎⍺) v[ri]
oldv ← v[sub⌿unused]
values ← ↓newv,oldv
reprs ← ↓r[sub⌿unused],⍨↓(↑sub/⊂⍺),(↑r[li]),' ',↑r[ri]
reprs values
}
idx ← (~0=(1+l)|⍳l*2) ⌿ ↑,⍳l l
unused ← idx ~⍨⍤1 1 ⍳l
(a w) ← U, '+-×÷' ∘.C ↓⍉↑⍺ ⍵
u←≠w
a ∇⍥(u∘/) w
}
:EndNamespace
``````

The `Solve` function is just a wrapper around the main algorithm I described, filtering for the target value in all the different values I can build with the input numbers. Use it like `24 GameOf24.Solve 1 2 3 4`.

Other than all the feedback you can give me, I have particular questions I would like to see addressed:

• originally I was using a fair share of each `¨` and used `U` twice, so I created a dfn for `U`, which now I only use once. Is it worth keeping it as a separate dfn? Or maybe there is a smarter way of unpacking the results of `'+-×÷' ∘.C ↓⍉↑⍺ ⍵` to `(a w)` which doesn’t require the use of `U`;

• I don’t think it is very elegant to have a string `'+-×÷'` with the arithmetic operations I am allowed to use and then later on fixing them with `⍎⍺` but I can’t think of a better way of doing this;

• is the shape of the data adequate? A vector of vectors for the numbers available and a separate vector of “strings” seems suitable;

• should `C` be adjusted and defined outside of `Combine`? Currently it’s inside `Combine` because it uses variables defined inside `Combine` and I think it would be too cumbersome to define those auxiliary variables each time `C` is called;

• the string representations keep getting extra whitespace that I don’t know where it comes from; e.g. `100 GameOf24.Solve 1 2 3 4 7` gives `×+3 7 ×+1 4 2 ` as string representation of the result.

Solution

`{(wl wr)←⍵ ⋄ (al ar)←⍺ ⋄ (al,wl)(ar,wr)}` can be `((⊣/⍤⊣,⍥⊃⊣/⍤⊢),⍥⊂⊢/⍤⊣,⍥⊃⊢/⍤⊢)`, a crazy looking train indeed.

Might be a good idea to add `⎕IO←0` at the beginning of the namespace script.

`U, '+-×÷' ∘.C ↓⍉↑⍺ ⍵` the `,` is not needed.

the string representations keep getting extra whitespace that I don’t know where it comes from

It is due to the padding of `↑` in this line:

``````reprs←↓r[sub⌿unused],⍨↓(↑sub/⊂⍺),(↑r[li]),' ',↑r[ri]
``````