5
\$\begingroup\$

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 Add (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 =
        let first = Seq.head 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

\$\endgroup\$
1
\$\begingroup\$

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 Add (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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – AlexFoxGill Sep 4 '14 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.