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:

(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 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.

{(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]