'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        -&gt; x     
| Add (x, y)      -&gt; eval x + eval y
| Subtract (x, y) -&gt; eval x - eval y
| Multiply (x, y) -&gt; eval x * eval y
| Divide (x, y)   -&gt; eval x / eval y

// string representation of an expression, with evaluated result
let write n =
    let rec write' = function
    | Number x        -&gt; x.ToString()
    | Add (x, y)      -&gt; "(" + write' x + " + " + write' y + ")"
    | Subtract (x, y) -&gt; "(" + write' x + " - " + write' y + ")"
    | Multiply (x, y) -&gt; "(" + write' x + " * " + write' y + ")"
    | Divide (x, y)   -&gt; "(" + 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&lt;Expr list&gt; 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 -&gt; i,x) exprs
        [ for (i,x) in indexed do
          for (j,y) in indexed do
          if j &gt; i then
            yield (x,y), [ for (k,z) in indexed do if k &lt;&gt; i &amp;&amp; k &lt;&gt; j then yield z ] ]

    // for two given expressions, get possible combinations
    let getExpressions x y =
        let isDivisible x y =
            let denom = eval y
            denom &lt;&gt; 0 &amp;&amp; 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 &gt;&gt; ((-) target) &gt;&gt; abs
    let fitness = Seq.map distance &gt;&gt; Seq.min

    let iterate =
        Seq.collect generate
        &gt;&gt; Seq.sortBy fitness

    let rec compute' candidates =
        let first = Seq.head candidates
        match first, fitness first with
        | x::[], _  -&gt; x // no more iterations, this is the best one
        | exprs,  0 -&gt; Seq.minBy distance exprs // woop, got it
        | _,     _  -&gt; candidates |&gt; iterate |&gt; compute'
    seq { yield numbers |&gt; List.map Number }
    |&gt; 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 &lt;&gt; 0 &amp;&amp; eval x % denom = 0

        let a,b = if x &gt; 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 -&gt; i,x) exprs

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


I would still very much appreciate any and all critique!