# Solving the game of 24 recursively in APL

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.

• I can still not understand how the expression ÷-÷3 ×5 6 2 4 evals, it looks like Polish notation, but not exactly the same. Oct 12, 2021 at 12:12
• Am I not using regular prefix notation? ÷-÷3×5 6 2 4 = ÷-÷3(×5 6) 2 4 = ÷-÷3 30 2 4 = ÷-(÷3 30) 2 4 = ÷-0.1 2 4 etc
– RGS
Oct 12, 2021 at 12:15
• Ah, I see now. The extra white space makes me a little confusing. Oct 12, 2021 at 12:48
• APL seems to be even more write only than Perl :) Oct 12, 2021 at 15:33
• @Kubahasn'tforgottenMonica APL is unlike other traditional languages, yes. In general, it's hard to look at APL and guess what it's doing if you know nothing about APL, yes. APL is write-only? Not really :) when you learn it, you'll learn how to read it. Just like with English, Russian, or Chinese.
– RGS
Oct 12, 2021 at 16:30

{(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.
It is due to the padding of ↑ in this line:
reprs←↓r[sub⌿unused],⍨↓(↑sub/⊂⍺),(↑r[li]),' ',↑r[ri]