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 bruteforce 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 N1
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:
(edit: as time went by the code evolved a little)
:Namespace GameOf24
⍝ Generalized solver for the "game of 24".
Solve←{
⍝ Dyadic function to find ways of building ⍺ with the numbers in ⍵
(reprs values)←Combine⊂⍵
mask←⍺=∊values
(mask/reprs) (mask/values)
}
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 usedU
twice, so I created a dfn forU
, 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 ofU
; 
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 ofCombine
? Currently it’s insideCombine
because it uses variables defined insideCombine
and I think it would be too cumbersome to define those auxiliary variables each timeC
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]