4 Number Game

The 4 number game is a well known arithmetic puzzle that can be played in groups. You are presented with four numbers, e.g. 1 1 11 11, and are given the goal to make 24 by using the arithmetic operators +, *, -, / and liberal use of parenthesis.

As the below code shows, adding all the numbers will solve the puzzle.

(+ 1 1 11 11)

In this blog post we will explore code that can find solutions to these puzzles. One puzzle that is a little more interesting than the other is to try to make 24 with 1 3 8 8.

Solution Path

Every arithmetic expression, e.g. 1 + 2 * 3, can be seen as a a tree. In this case the tree would be

  +
 / \
1   *
   / \
  2   3

This tree tells us that we need to add 1 and the product of 2 and 3. I we squint with our eyes and only take into account the structure of the tree, we would see the following


 / \

   / \

The only thing that is missing from this tree are the operators, which should go into the internal positions of the tree, and the numbers, which should go in the leaf positions.

So our solution will be:

Generate all the possible tree structures
Decorate a tree structure with all possible operators and all possible values
Evaluate an expression tree
Putting it together

Generating all tree structures

In the following code snippet we generate all the tree structures with only one internal node. There is only one, which can be seen.


(require '[flippo.tree :refer [generate-structure-tree]])

(generate-structure-tree 1)

This blog post is enhanced with klipse, which means that all code snippets are interactive. Go ahead and change the number and see the corresponding tree structures.

How can one generate these structures?

Let's first think of growing a single tree. Below we have a tree with two internal node that corresponds to the arithmetic expression from the solution path section.


(def a-tree {:left nil, :right {:left nil, :right nil}})

We can visualize the nil position as buds ready to spring a new tree part. So in order to grow our tree we could try to adjoin a part to all buds.


(defn adjoin [tree part]
  "Returns a sequence of structured trees where part is adjoined to
   all the buds in tree"
  (if (nil? tree)
    (seq [part])
    (concat
     (map (fn [t] {:left t :right (:right tree)}) (adjoin (:left tree) part))
     (map (fn [t] {:left (:left tree) :right t}) (adjoin (:right tree) part)))))

(adjoin a-tree :A)

Here we adjoined a keyword :A and we see that we get three new tree structures. Try to adjoin a small tree structure {:left nil :right nil}.

This is the basis of the generate-structure-tree algorithm. There is only one tree with zero internal nodes, i.e. nil. It can serve as a basis to sprout small trees from the buds. Doing this recursively gives us our algorithm.

Decorate a Tree Structure

Now that we can generate tree structures, we would like to decorate them with tree operators and values. The basic algorithm for that is visiting all nodes in the tree and assign values to the leaves and operator to the internal nodes.

A generator helps us in this case. We could use it to request the next value we haven't use. Lets implement a generator.


(defn generator [elements]
  "Creates a generator that loops through the vector elements"
  (let [index (atom 0)]
    (fn []
      (let [current-index @index]
        (do
          (swap! index #(mod (inc %) (count elements)))
          (nth elements current-index))))))

(def keyword-generator (generator [:A :B :C]))

(keyword-generator)
(keyword-generator)

Our generator is a high-order function in the sense that it returns a function. The function closes over an atom that keeps track of an index. The index is used to retrieve an element from the elements provided as an argument to generator call.

We created a keyword generator and called it twice. This returns :B. Add a new call to keyword-generator and it will cycle through the values :A, :B and :C.

How can we use this?

Lets assume we have a tree that we want to decorate. Furthermore, we have an generator that cycles through a selection of operators, e.g. * and +, and a generator that cycles through some values, e.g. 1, 2 and 3. What we could do is walk the tree and transform it in the following fashion. For each internal node of the tree, request and operator from the operator generator, and associate it with that node. Furthermore, for each leaf node, request a value from the value generator and make a value node.

The only unknown is the question: how to traverse a tree. Lets implement it right away.


(defn map-tree [f tree]
  "Let f operate on all the nodes of the tree"
  (if (nil? tree)
    (f tree nil nil)
    (f tree (map-tree f (:left tree)) (map-tree f (:right tree)))))

map-tree takes a function f and a tree and applies each node of the tree, together with its two children to f. We can use it to decorate the tree with the operators and values.


(defn decorate [operators values tree]
  "Transforms a structured tree into a tree ready for evaluation. It walks the tree
   and transform nil nodes into value-nodes, and non-nil nodes into operator nodes.
   This is done in a cyclic fashion, both for the operators and the values."
  (let [
        operator-generator (generator operators)
        value-generator    (generator values)
        transformer        (fn [tree left right]
                             (if (nil? tree)
                               {:value (value-generator)}
                               {:operator (operator-generator) :left left :right right}))]
    (map-tree transformer tree)))

(decorate '[* +] [1 2 3] {:left nil :right {:left nil :right nil}})

It seems to have worked. Make sure to try different operators, values and tree. Then move on to the next phase. Note that we have quoted the list of operators. This is to clean up the output. See what happens when you remove the '.

Evaluating a Tree

Now that we have a abstract syntax tree of our arithmetic expression, we want to evaluate it. Evaluation is nothing more than applying the correct operation to the (evaluated) value of the left sub-tree and the (evaluated) value of the right sub-tree.


(defn evaluate [tree]
  "Evaluates a tree representation like {:operator + :left {:value 1} :right {:value 2}}
   to the corresponding value, i.e. 3."
  (if (:operator tree)
    ((:operator tree) 
      (evaluate (:left tree)) 
      (evaluate (:right tree)))
    (:value tree)))

(def tree (decorate [* +] [1 2 3] {:left nil :right {:left nil :right nil}}))

(evaluate tree)

The tree in the above snippet represents the calculation 1 + (2 * 3), so it produces the correct answer. There is only one problem that could occur. If we would allow the operator / and the value 0, possibly this could lead to a divide by zero answer. A safe-evaluate would catch this ArithmeticException and just return nil.

Putting it Together

If you have experimented with the tree decorations, you may have noticed that the order the operators are listed is important. If instead of first applying * and than +, you reverse the order, the answer is different.

So we should try to have all possible selections of operators and all permutation of values and each try them on a tree. Luckily there is a nice library that provides these functions.


(require '[clojure.math.combinatorics :refer [permutations selections]])

(permutations [:A :B :C])

Above we see all possible permutations of three elements. This is ideal for trying out all possible assignments of values, because no value is repeated. For a given puzzle we can use each value only once.

We need something else if we want to try out all assignments of operators, because the same operator can be used multiple times. Luckily the clojure.math.combinatorics library also provides selections


(require '[clojure.math.combinatorics :refer [permutations selections]])

(selections [:A :B :C] 2)

Here we see all possible two element sequence drawn from the vector [:A :B :C]. We can use that in order to solve our puzzle. The algorithm is

Generate all possible selection of operators.
Generate all possible permutation of values.
Generate all structure trees.
Decorate each combination of trees with operators and values.
Filter the ones that do not reach the target.


(require '[clojure.math.combinatorics :refer [permutations selections]]
         '[flippo.tree :refer [generate-structure-tree]])

(defn solve
  ([operators target values]
   "Returns all trees that use operators to form target"
   (filter #(= target (evaluate %))
           (let [nodes (dec (count values))]
             (for [os (selections operators nodes)
                   vs (permutations values)
                   tree (generate-structure-tree nodes)]
               (decorate os vs tree))))))

We can use that to solve our puzzle