Fatvat

Countdown is a Channel4 game show with standard number and word puzzles. In this post we'll look at the Numbers game. The rules are simple, given 6 numbers (between 1 and 999 inclusive), calculate the target number (between 100 and 999 inclusive). You can use +, -, / and * to get the numbers and you have a 30 second time limit to do so.

To solve this in Clojure we'll start with a brute force search of all the possibilities and see if that's good enough to solve it.

One approach I tried initially was just to build up the Clojure expression tree for all possible examples, using code like this:

(def *operators* ['+ '- '/ '*])

(defn expr
  "A list of expressions for a and b"
  [a b]
  (map (fn [x] (list x a b)) *operators*))

The idea would be that I could then just (map eval (expr 4 5)) and get all the possible results. This turned out to be very slow. Generally you want to avoid calling eval at run-time if you can help it.

To solve this I defined a simple structure to keep track of running expressions and their value. As the expressions are built up, the values are calculated in sync.

(def *operators* {'+ + '- - '/ / '* *})

(defn is-valid [op a b]
  (cond 
   (= + op) true
   (= - op) (> a b)
   (= * op) true
   (= / op) (= (mod a b) 0)))

(defstruct node :expression :value)

(defn value 
  [x]
  (if (map? x)
    (x :value)
    x))

(defn expression
  [x]
  (if (map? x)
    (x :expression)
    x))

(defn expr 
  "A list of expressions for a and b"
  [a b]
  (let [nodea (map? a) nodeb (map? b)]
    (filter (fn [x] (not (nil? x))) 
            (map (fn [x] (when (is-valid (second x) (value a) (value b))
                           (struct node 
                                   (list (first x) (expression a) (expression b)) 
                                   ((second x) (value a) (value b)))))
                 *operators*))))

Why is *operators* a map? That's simply because "+" doesn't print very nicely e.g.

  countdown> +
  #<core$_PLUS___3180 clojure.core$_PLUS___3180@61dd1c39>

I also added a check to prune entries out that results in floating point or negative numbers, that just helps keep the number of combinations down a little.

Armed with a function that calculates all the possible expressions for a pair of expressions, how do we now use that to generate all the possible expressions?

(defn make-expressions-helper 
  "Given a lst, build up all valid Countdown expressions"
  [x]
  (cond
   (< (count x) 2) (list (struct node (first x) (first x)))
   (= 2 (count x)) (apply expr x)
   :else
     (let [exps (apply expr (take 2 x))
           remd (drop 2 x)]
       (mapcat make-expressions-helper (map (fn [x] (cons x remd)) exps)))))

This is a recursive definition with the following logic:

• A singleton list (1) can only evaluate to itself so the only possibility is [expr=1 value=1]
  
• A list of size two just uses the expr function to generate all the expressions
  
• Any other list builds all the possible expressions for the first two elements, and then for all of these (mapcat) calls make-expressions-helper on the rest.
  

Note that this just builds up the possible expressions with the numbers in this particular order. For example.

  countdown>(make-expressions-helper '(1 2 3))
  ({:expression (+ (+ 1 2) 3), :value 6} {:expression (/ (+ 1 2) 3), :value 1}
   {:expression (* (+ 1 2) 3), :value 9} {:expression (+ (* 1 2) 3), :value 5}
   {:expression (* (* 1 2) 3), :value 6})

  countdown> (count (make-expressions-helper '(1 2 3 4 5 6)))
  118

So now we need to apply the helper function to all possible combinations. Thankfully, Clojure Contrib already has a few combinatorics algorithms. permutations returns a lazy list of all possible permutations of the supplied list.

(defn make-expressions [lst]
  (if (nil? lst)
    nil
    (lazy-cat
     (mapcat make-expressions-helper (permutations lst))
     (mapcat make-expressions (drop-one lst)))))

So this algorithm applies the helper function to all permutations of the input, and then applies itself to all combinations of the remainder of the list. drop-one is a helper function which gives a list of all combinations of a list without one element.

So how many valid Countdown expressions are there?

  countdown> (count (make-expressions '(1 2 3 4 5 6)))
  300290

  countdown> (time (count (make-expressions '(1 7 8 25 50 75))))
  "Elapsed time: 2653.618442 msecs"
  268175

Note that the number is different because we rule out cases which result in floating point or negative numbers. The elapsed time is just under three seconds which is pretty fast! Remember that this time includes all the calculation of the results too, not just generating the expressions. So finally, all we need is a solver function.

(defn solve 
  "Solve the countdown problem"
  [numbers target]
  (filter (fn [x] (= (x :value) target)) (make-expressions numbers)))
  

This will return all the combinations that lead to the right results. Let's try it out with a toy examples:

  countdown> (time (solve '(4 5 6) 15))
  "Elapsed time: 0.281907 msecs"
  ({:expression (+ (+ 4 5) 6), :value 15} {:expression (+ (+ 4 6) 5), :value 15}
   {:expression (+ (+ 5 4) 6), :value 15} {:expression (+ (+ 5 6) 4), :value 15}
   {:expression (+ (+ 6 4) 5), :value 15} {:expression (+ (+ 6 5) 4), :value 15})

Notice that we've returned all possible + expressions that make 15. We've not taken any notice of the commutative properties of addition. Taking advantage of these properties is explored in "The Countdown Problem" [PDF] by Graham Hutton.

How does it fair on bigger solutions?

  countdown> (time (solve '(7 5 9 25 40 10) 753))
  "Elapsed time: 222.632493 msecs"
  {:expression (- (* (- (- (* 5 25) 9) 40) 10) 7), :value 753}

With the code as it stands we could add additional operators (exponent for example) without any code changes, but more operators would probably require something more sophisticated than brute force.

As usual, any suggestions for making the code clearer (or finding any bugs!) are greatly appreciated. Full code is on my Git repository.

Labels: clojure