Lindsey Kuper

A while back, Mark Dominus proposed an arithmetic puzzle: combine the numbers 6, 6, 5, and 2 with arithmetic operations (addition, subtraction, multiplication, and division) to get 17. After fiddling with the problem for a bit on my own and not being able to solve it, I decided to write a solver, and I ended up falling down an unexpected rabbit hole and dragging a few friends down with me.

(If you want to try to solve the puzzle on your own, or if you want to write a solver without having seen someone else’s, you may want to go do that before continuing to read this post.)

First draft

In the spirit of sharing process, here’s my first attempt at a solver. It’s a mess, but it works, sort of. It will find a way, if one exists, of combining four given integers using arithmetic operations to get an expression that evaluates to a given target integer (assuming that the expression is parenthesized in a particular way; more on that later). I happened to hard-code 17 as the target, but it would have been just as easy to have that be an argument. The approach I took is pretty boring: it first generates all permutations of the list of four inputs, then generates all the arithmetic expressions that can be built by sticking +, -, *, or / in between the numbers in each of those permutations. Finally, it evaluates all the resulting expressions and sees which ones, if any, evaluate to the target number.

I wrote it in Scheme because I had originally intended to use miniKanren, but at some point I changed my mind about that and just wrote vanilla Scheme. The less that’s said about my ugly first draft, the better, probably, but I do want to make one process-related observation. I was having trouble writing the permutations function in Scheme; I knew that the output was wrong, but I couldn’t tell where my code was wrong. I ported my Scheme permutations code to Haskell, tried to compile it and got a type error, and the problem became apparent: the Scheme version had been missing a concat. I mentioned this to Mark – who had already written at least one solver, but had decided to try to do another one in Scheme when I told him that that’s what I had done – and he said, “I’m at exactly that point in my Scheme implementation also! I have some function that is returning a [[[T]]] when it ought to be a [[T]] and I’m not sure yet where the fault is.” I think it’s interesting that we both ran into more or less the same bug.

Mark also remarked, “I saw your first solution and said to myself ‘She used way too much code, I could write this much shorter’ and I tried and it exploded and now the walls and floor are covered with dripping masses of Scheme code.” Well, we’ve all been there.

Second draft

Next, I wrote a Racket version that used the same strategy as the Scheme one, but was shorter and produced much easier-to-understand output. I found out that permutations was built into Racket, so I didn’t even need to write it. Here’s my code:

#lang racket

;; A solver for the following puzzle:
;; Given 5 integers a, b, c, d, and e,
;; find an expression that combines a, b, c, and d with arithmetic operations (+, -, *, and /) to get e.

(require srfi/1)

(define ops '(+ - * /))

(define (combine4 n1 n2 n3 n4)
  (concatenate
   (map (lambda (op)
          (map (lambda (e) `(,op ,n4 ,e)) (combine3 n1 n2 n3)))
        ops)))

(define (combine3 n1 n2 n3)
  (concatenate
   (map (lambda (op)
          (map (lambda (e) `(,op ,n3 ,e)) (combine2 n1 n2)))
        ops)))

(define (combine2 n1 n2)
  (map (lambda (op) `(,op ,n1 ,n2)) ops))

(define (eval-expr e)
  (with-handlers ([exn:fail:contract:divide-by-zero?
                   (lambda (exn) +inf.0)])
    (eval e)))

(define solve
  (lambda (n1 n2 n3 n4 target)
    (let* ([perms (permutations `(,n1 ,n2 ,n3 ,n4))]
           [expr-lists (map (lambda (perm)
                              (combine4 (first perm)
                                        (second perm)
                                        (third perm)
                                        (fourth perm)))
                            perms)]
           [val-lists (map (lambda (expr-list)
                             (map eval-expr expr-list)) expr-lists)]
           ;; For each perm, see if there's a val in its val-list that is equal to target.
           ;; If so, hold on to the corresponding expr from its expr-list.
           [solutions (filter-map (lambda (perm expr-list val-list)
                                    (let ([idx (list-index (lambda (elem)
                                                             (equal? elem target)) val-list)])
                                      (if idx
                                          (list-ref expr-list idx)
                                          #f)))
                                  perms expr-lists val-lists)])
      (delete-duplicates solutions))))

;; Example: combine 6, 6, 5, and 2 with arithmetic operations to get 17:
;; > (solve 6 6 5 2 17)
;; '((* 6 (+ 2 (/ 5 6))))

;; 5 / 6 = 5/6
;;   + 2 = 17/6
;;   * 6 = 17

I think the ugliest thing about my Racket solution is the combine2, combine3, and combine4 functions, especially all the repetition between combine4 and combine3. And, despite all that code, it can still only produce solutions with the (op a (op b (op c d))) expression tree shape and therefore misses a lot of solutions.

Down the rabbit hole

I thought I was done thinking about this problem, but after I tweeted about my solver, a few other people shared their attempts, many of which do clever things. For instance, Darius Bacon’s Python solution distinguishes between commutative and non-commutative operations, which I hadn’t thought to do. Then, Sebastian Fischer shared a cute solution in Haskell, specific to the “combine 6, 6, 5, and 2 to get 17” problem. However, it looks like it’s choosing the three operations to be distinct, which overconstrains the problem.

But the real rabbit hole started with a now-deleted tweet in which someone offered an incredibly concise Haskell version that didn’t have the distinctness issue. It used replicateM 3 ["+","-","*","/"] to create a list of combinations of operations, which looks like [["+","+","+"],["+","+","-"],...] and has length 64. So, there’s some list monad trickery going on there. The most surprising thing about their solution, though, was that they wrote something like do { opList <- replicateM 3 ["+","-","*","/"]; exprs <- permutations ([6, 6, 5, 2] ++ opList); ... } to generate a massive list containing all valid RPN programs written with those operators and operands, as well as many, many invalid ones. When I questioned this, the author was like, “It’s only 300K programs; it’s not a big deal to evaluate them.” (!)1

I wanted to come up with a nice way to refactor my Racket code to do what replicateM 3 ["+","-","*","/"] was doing, but then I got distracted just trying to figure out what the thing I wanted was even called. Given a set of items (in this case, \(\lbrace \texttt{+}, \texttt{-}, \texttt{*}, \texttt{/} \rbrace\)), I wanted to enumerate all of the lists of a given length (in this case, 3) whose elements are drawn from the set, with repetitions allowed. My first instinct was to call these things “ordered \(k\)-multisets”, where \(k\) is the length of the lists we’re producing, but that terminology doesn’t seem to be much in use; there are only a handful of Google results for it. These lecture notes from someone’s 2013 discrete math course at TU Vienna, at least, seem to be using it in the way I intended:

The number of ordered \(k\)-multisets over \(A\): \(n^{k}\). (Take a fixed number of positions \(k\) and for each position choose any element from \(A\)).

I wondered if there was a Racket library with a function that would enumerate the ordered \(k\)-multisets of a set. I asked some of the Racketeers I knew, and no one knew of such a library, but Justin Slepak suggested a clever way to do it: for a set with \(X\) elements, convert each of \(0,\dots,X^{k}-1\) into base \(X\), and then convert each digit (or, uh, \(X\)-it?) of the resulting base-\(X\) numbers back into an element of the original \(X\)-element set. I never got around to actually implementing that approach, but after Justin described it, I realized that it was in fact the approach taken by this Mathematica code that I’d also come across and not really understood (I had seen things like Module and Thread in the Mathematica code and had given up trying to read it). Then, a comment on that page led me to this diagram, which offers another name for “ordered \(k\)-multisets”: variations with repetition. Further investigation on Wikipedia revealed that there are several competing names for this notion:

\(n\)-tuples whose entries come from a set of \(m\) elements are also called arrangements with repetition, permutations of a multiset and, in some non-English literature, variations with repetition.

Another Wikipedia page claims that “variations with repetition” is “an archaic term in combinatorics still commonly used by non-English authors”. In any case, it’s still a lot more popular than “ordered \(k\)-multisets”!

At this point, I had satisfied my curiosity and was ready to move on from this problem, but my friend Michael “rntz” Arntzenius wasn’t quite done: he forked my Racket code and wrote a solver that can produce answers with all of the possible expression tree shapes, which mine can’t do. Then, when I mentioned the Darius Bacon version that distinguishes between commutative and non-commutative operations, he wrote a version that did that, too. Both rntz and Darius also used generators and other fancy stuff that my code doesn’t use.

Want another puzzle?

Mark mentioned that a couple of people have written to him to suggest an even harder instance of this problem: from 8, 8, 3, and 3, make 24. He said he puzzled over this one for several days before giving up and asking his solver for help. I also had to give up and ask my own solver after a while, and I was pleased that despite its limitations, it coughed up a correct answer. So, that’s a happy ending of sorts.

Update (January 2, 2017): On Twitter, Nada Amin pointed out the existence of a 2002 functional pearl paper by Graham Hutton about writing a Haskell solver for a similar problem. The version of the problem in the paper restricts not only inputs but also intermediate results to being natural numbers, which changes things quite a bit; for instance, you need non-integral intermediate results to be able to get 17 from 6, 6, 5, and 2, as shown above.

Update (April 9, 2017): Mark has written a follow-up blog post covering various people’s solution to this problem, and he says he would like to write “at least three or four” more articles on the topic eventually, which perhaps gives a sense of just how deep this rabbit hole could go.

  1. 332,560, to be precise. By contrast, my solver only needs to try 1536 possible solutions (24 permutations of the input integers, times 64 combinations of operations). Admittedly, though, there are five possible expression tree shapes, and I can only produce solutions with one of those shapes. Five times 1536 is 7680, so 7680 of the 332,560 “RPN programs” would actually be valid RPN. (These counts include duplicate solution candidates, which arise when the input numbers aren’t all distinct.) ↩

Comments