Countdown numbers round

“The clock ticked as loudly as rain on glass. I like trains because they make sounds that fit their bodies” by SamahR is licensed under CC BY 2.0.

In case you’re not familiar with Countdown, it’s a gameshow where two contests compete against each other in 30-second rounds. The rounds consist of two types — letters or numbers, the latter being what we’re interested in.

At the start of the round a contestant will ask for six alternatively “large” or “small” numbers, which the co-presenter draws from a face-down stack of cards. An example of the six cards that have been drawn:

25, 10, 7, 6, 8, 3

The co-presenter will then press a button to generate a pseudo-random number that will represent the target the contestants must reach, e.g.

958

This target can be reached by performing arithmetic on the six “input” numbers, with the following caveats:

1. Every number card can only be used once
2. Multiplication, division, addition and subtraction are the only permitted operations
3. Division can only be performed if it would produce an integer, i.e. has no remainder

My dad sent me this example recently, because he was fairly chuffed that he’d beaten the brainy co-presenter, who could not think of a way to reach the target. I admit I struggle with these problems as well, but whereas my dad may be better at mental arithmetic, I’ve got more experience as a programmer!

The following solution involves generating permutations, something I used previously in this post on BST sequences and is written in C#.

var possibilities = new[] { 25, 10, 7, 6, 8, 3 };
const int target = 958;

foreach (var term in Expand(possibilities, target))
{
    Console.WriteLine(term);
}

IEnumerable<Term> Expand(IEnumerable<int> allPossibilities, int target)
{
    return Expand(allPossibilities);
    
    IEnumerable<Term> Expand(IEnumerable<int> allPossibilities, Term? current = null, int sum = 0)
    {
        if (sum == target)
        {
            if (current != null) yield return current;
            yield break;
        }
        
        foreach (var (n, index) in allPossibilities.Select((n, index) => (n, index)))
        {
            var remaining = allPossibilities.Where((_, index2) => index != index2);
            var c = new Const(n);
            if (current == null)
            {
                foreach (var term in Expand(remaining, c, n))
                    yield return term;

                continue;
            }
            foreach (var term in Expand(remaining, new Mul(c, current), sum * n))
                yield return term;
            foreach (var term in Expand(remaining, new Add(c, current), sum + n))
                yield return term;
            foreach (var term in Expand(remaining, new Sub(current, c), sum - n))
                yield return term;
            foreach (var term in Expand(remaining, new Sub(c, current), n - sum))
                yield return term;
            if (n != 0 && sum % n == 0)
                foreach (var term in Expand(remaining, new Div(current, c), sum / n))
                    yield return term;
            if (sum != 0 && n % sum == 0)
                foreach (var term in Expand(remaining, new Div(c, current), n / sum))
                    yield return term;
        }
    }
}

internal abstract record Term;

internal record Const(int Value) : Term
{
    public override string ToString() => Value.ToString();
}

internal abstract record Expr(Term Left, Term Right) : Term
{
    protected string Format(string separator)
    {
        return $"{FormatTerm(Left)} {separator} {FormatTerm(Right)}";
    }

    private static string FormatTerm(Term term) => term is Const ? term.ToString() : $"({term})";
}

internal record Div(Term Left, Term Right) : Expr(Left, Right)
{
    public override string ToString() => Format("/");
}

internal record Mul(Term Left, Term Right) : Expr(Left, Right)
{
    public override string ToString() => Format("*");
}

internal record Add(Term Left, Term Right) : Expr(Left, Right)
{
    public override string ToString() => Format("+");
}

internal record Sub(Term Left, Term Right) : Expr(Left, Right)
{
    public override string ToString() => Format("-");
}

The output seems to contain only two really different solutions — there are many effective duplicates due to multiplication or addition being reordered with no change to the result:

8 - (6 + (3 * (10 * (7 + 25))))
(8 - (3 * (10 * (7 + 25)))) - 6
8 - (6 + (10 * (3 * (7 + 25))))
(8 - (10 * (3 * (7 + 25)))) - 6
8 - (6 + (3 * (10 * (25 + 7))))
(8 - (3 * (10 * (25 + 7)))) - 6
8 - (6 + (10 * (3 * (25 + 7))))
(8 - (10 * (3 * (25 + 7)))) - 6
(25 - (7 * (10 * (8 + 6)))) - 3
25 - (3 + (7 * (10 * (8 + 6))))
(25 - (10 * (7 * (8 + 6)))) - 3
25 - (3 + (10 * (7 * (8 + 6))))
(25 - (7 * (10 * (6 + 8)))) - 3
25 - (3 + (7 * (10 * (6 + 8))))
(25 - (10 * (7 * (6 + 8)))) - 3
25 - (3 + (10 * (7 * (6 + 8))))