# 'Countdown' Numbers round - combine numbers arithmetically to reach a target

Countdown is a British gameshow where contestants compete in word and number challenges. During the numbers round, six numbers are chosen semi-randomly and the task is to combine them using addition, subtraction, multiplication and division in order to reach a target number.

For example, the numbers might be [75; 25; 7; 2; 5; 8] and the target 491.

One winning solution is ((75 + 25) * 5) - 7 - 2 = 491

Below is some F# code that I wrote to try and improve my functional skills. The compute function accepts an int list and an int and returns an Expr which is the closest it could find to the target.

First, declaring the recursive type and functions to evaluate and print them

module Numbers

type Expr =
| Number of int
| Add of Expr * Expr
| Subtract of Expr * Expr
| Multiply of Expr * Expr
| Divide of Expr * Expr

let rec eval = function
| Number x        -> x
| Add (x, y)      -> eval x + eval y
| Subtract (x, y) -> eval x - eval y
| Multiply (x, y) -> eval x * eval y
| Divide (x, y)   -> eval x / eval y

// string representation of an expression, with evaluated result
let write n =
let rec write' = function
| Number x        -> x.ToString()
| Add (x, y)      -> "(" + write' x + " + " + write' y + ")"
| Subtract (x, y) -> "(" + write' x + " - " + write' y + ")"
| Multiply (x, y) -> "(" + write' x + " * " + write' y + ")"
| Divide (x, y)   -> "(" + write' x + " / " + write' y + ")"
write' n + " = " + (eval n).ToString()


This function that takes an Expr list (in the first case, a list of Numbers) and produces a seq<Expr list> which is calculated by all the possible applications of a single arithmetic operator (+*/-) to any/all pairs of expressions.

let generate exprs =
// a specialised choose2 function that returns the pair plus the remainders
// uses indices for comparison in case of duplicate values
let pairTwo exprs =
let indexed = List.mapi (fun i x -> i,x) exprs
[ for (i,x) in indexed do
for (j,y) in indexed do
if j > i then
yield (x,y), [ for (k,z) in indexed do if k <> i && k <> j then yield z ] ]

// for two given expressions, get possible combinations
let getExpressions x y =
let isDivisible x y =
let denom = eval y
denom <> 0 && eval x % denom = 0

let a = max x y
let b = min x y
seq {
yield Multiply (x, y)
yield Subtract(a, b) // don't bother with negatives
if isDivisible a b
then yield Divide(a, b)
yield x // yielding each partial result prevents near-misses getting lost
yield y // although expands the search tree
}

seq {
for (x,y),zs in pairTwo exprs do
for expr in getExpressions x y do
yield expr :: zs }


Finally the compute function which drives the calculation, iterating over all candidate expressions until a match is found or there are no more possibilities

let compute numbers target =
let distance = eval >> ((-) target) >> abs
let fitness = Seq.map distance >> Seq.min

let iterate =
Seq.collect generate
>> Seq.sortBy fitness

let rec compute' candidates =
match first, fitness first with
| x::[], _  -> x // no more iterations, this is the best one
| exprs,  0 -> Seq.minBy distance exprs // woop, got it
| _,     _  -> candidates |> iterate |> compute'
seq { yield numbers |> List.map Number }
|> compute'


I'd really like feedback on my use of closures, pattern matching, choices of list vs seq, and if anyone can think of a nicer way to implement the pairTwo function I would like to see it

I have slightly simplified the generate function by merging the pairTwo function into the resulting seq computation expression. I refrained from merging the getExpressions function, as its functionality is distinct enough to warrant a separate function IMO.

let generate exprs =
// for two given expressions, get possible combinations
let getExpressions x y =
let isDivisible x y =
let denom = eval y
denom <> 0 && eval x % denom = 0

let a,b = if x > y then x,y else y,x
seq {
yield Multiply (x, y)
yield Subtract(a, b) // don't bother with negatives
if isDivisible a b
then yield Divide(a, b)
yield x // yielding each partial result prevents near-misses getting lost
yield y // although expands the search tree
}

let indexed = List.mapi (fun i x -> i,x) exprs

seq {
for (i,x) in indexed do
for (j,y) in indexed do
if j > i then
for expr in getExpressions x y do
yield expr :: [ for (k,z) in indexed do if k <> i && k <> j then yield z ] }


I would still very much appreciate any and all critique!

I find the logic a bit hard to follow, especially in compute', so I'll just comment on some minor issues and post some recommended reading.

| x::[], _  -> x


Is more commonly written

| [x], _ -> x


Using point-free style here is distracting:

let distance = eval >> ((-) target) >> abs


I find this much clearer:

let distance expr = abs (target - eval expr)


This does not do what you want:

let a = max x y
let b = min x y


For example,

> max (Number 100) (Add (Number 1, Number 2)) ;;

val it : Expr = Add (Number 1,Number 2)


You want something like this instead

let a, b = if eval x >= eval y then x, y else y, x


Graham Hutton wrote a paper on solving this problem in Haskell, which is a great read. You can find it here. It would be a good exercise to port the solution to F#.

We systematically develop a functional program that solves the countdown problem, a numbers game in which the aim is to construct arithmetic expressions satisfying certain constraints. Starting from a formal specification of the problem, we present a simple but inefficient program that solves the problem, and prove that this program is correct. We then use program fusion to calculate an equivalent but more efficient program, which is then further improved by exploiting arithmetic properties.

• Thank you. I had realised the min/max issue since posting and implemented the same fix that you gave which is reassuring. Now that you mention it, the point-free style is a bit OTT for the distance function so I have reimplemented per your suggestion. About the complexity of the compute function, I agree it is a little hard to follow. I'll check out the Haskell paper (been a while since I did any of that) and see if I can relate the logic back to my program. Cheers for the link – AlexFoxGill Sep 4 '14 at 8:37