In this part we’ll build a naïve brute-force solution, which we’ll then optimise in part 2.
What do we mean by “brute-force”?
In a sentence, to generate all possible combinations of numbers and arithmetic operations.
To get a feel for the size of the search space, let’s imagine we were working with a list of three numbers, and only addition and subtraction:
ops = ["+", "-"]
nums = [5, 3, 10]We’ll start by generating all combinations of nums:
nums_perms = [
[5, 3, 10], [5, 10, 3],
[3, 5, 10], [3, 10, 5],
[10, 5, 3], [10, 3, 5]
]But this isn’t enough.
The rule Players are not required to use all six numbers is key. Sometimes in Countdown, the solution doesn’t require all the numbers.
So we’ll need to include all permutations of nums from one up to three, to account for possible solutions which don’t require all numbers:
nums_perms = [
[5], [3], [10],
[5, 3], [3, 5], [5, 10],
[10, 5], [3, 10], [10, 3],
[5, 3, 10], [5, 10, 3], [3, 5, 10],
[3, 10, 5], [10, 5, 3], [10, 3, 5]
]Once we’ve got that, we need to generate all possible expressions.
An expression is a combination of numbers and arithmetic operations which evaluates to give an answer, for example (5+10)/3.
There are a couple of points to consider:
- The single numbers
[5],[3], and[10]innums_permsare already expressions - they just evaluate to themselves. - We’ll need to take care to remove expressions which violate the Countdown rules no negative numbers and division must result in whole numbers.
Since we aren’t using division in our example we can ignore the second constraint, but it’s something we’ll need to think about in our final solution.
exprs = [
# valid expressions with 1 number
[5], [3], [10],
# valid expressions with 2 numbers
[5, '+', 3], [5, '-', 3], [3, '+', 5],
[5, '+', 10], [10, '+', 5], [10, '-', 5],
[3, '+', 10], [10, '+', 3], [10, '-', 3],
# valid expressions with 3 numbers
[5, '+', 3, '+', 10], [5, '-', 3, '+', 10],
[5, '+', 10, '+', 3], [5, '+', 10, '-', 3],
[3, '+', 5, '+', 10], [3, '+', 10, '+', 5],
[3, '+', 10, '-', 5], [10, '+', 5, '+', 3],
[10, '+', 5, '-', 3], [10, '-', 5, '+', 3],
[10, '+', 3, '+', 5], [10, '-', 3, '-', 5],
[10, '+', 3, '-', 5], [10, '-', 3, '+', 5]
]We have 26 possible expressions in exprs we then need to evaluate to check if any of them equal our target number.
The Plan #
Let’s bring this all together into a high-level plan:
- Given a list of 6 numbers, generate all possible permutations of those numbers from length 1 to 6 (
num_perms). - Generate a list of all possible valid expressions.
- Evaluate these expressions and only keep those which evaluate to the target value.
Implementation #
Representing Operations #
Let’s start by defining some data types to help with evaluating expressions.
We’ll start by creating a data type to represent each of the arithmetic operations, and add some helper functions:
-- create data type for each of the operations
data Op = Add | Sub | Mul | Div
-- define how to print operations
instance Show Op where
show Add = "+"
show Mul = "*"
show Sub = "-"
show Div = "/"
-- Check the Op is valid, and apply it if so
apply :: Op -> Int -> Int -> Maybe Int
apply Add x y = Just (x + y)
apply Sub x y = if y > x then Nothing else Just (x - y) -- can't produce a negative value
apply Mul x y = Just (x * y)
apply Div x y = if y == 0 || x `mod` y /= 0 then Nothing else Just (x `div` y) -- can't produce a fractional valueOk, we can check if operations are valid and apply them. Now we’ll think about expressions themselves.
Representing Expressions #
Let’s define a type for expressions, and some utility functions:
{-
An expression 'Expr' is either a 'Val' containing an Int,
or an expression 'Exp' containing an 'Op' and two
sub expressions still to be evaluated.
-}
data Expr = Val Int | Exp Op Expr Expr
-- how to print an Expr
instance Show Expr where
show (Val x) = show x
show (Exp op left right) = showSubExpr left ++ " " ++ show op ++ " " ++ showSubExpr right
where
showSubExpr (Val n) = show n
showSubExpr e = "(" ++ show e ++ ")"
-- given an Expr, evaluate it
eval :: Expr -> Maybe Int
eval (Val n) = Just n -- e.g. 'Val 3' is Just 3
eval (Exp op l r) = do
left <- eval l -- evaluate the left sub-expression
right <- eval r -- evaluate the right sub-expression
apply op left right -- compute the resultBefore we get into generating permutations, let’s define some other helpful stuff:
-- a type representing an expression along with it's result
type Expression = (Expr, Int)
type Expressions = [Expression]
-- define a list of operations
ops :: [Op]
ops = [Add, Mul, Sub, Div]This will help keep our code readable later on.
Subset Permutations #
Now we get to the fun stuff - generating permutations of numbers!
Let’s start by thinking about generating sublists from length 1 up to 6, so-called subsequences.
Fortunately Haskell already has a handy subsequences function:
ghci> import Data.List (subsequences)
ghci> subsequences [1,2]
[[],[1],[2],[1,2]]We’ll drop the first list since subsequences always produces an empty list first:
ghci> import Data.List (subsequences)
ghci> (drop 1 . subsequences) [1,2]
[[1],[2],[1,2]]Much better.
Now that we have unique sublists we can use them to generate permutations. Again, Haskell has a permutations function already:
ghci> import Data.List (permutations)
ghci> permutations [1,2]
[[1,2],[2,1]]Let’s try gluing everything together:
ghci> (permutations . drop 1 . subsequences) [1,2]
[
[[1],[2],[1,2]],
[[2],[1],[1,2]],
[[1,2],[2],[1]],
[[2],[1,2],[1]],
[[1,2],[1],[2]],
[[1],[1,2],[2]]
]Hmm… That’s not quite right. It seems we have two problems:
- Wrong structure — instead of a flat list of permutations, we’re getting a List of Lists of Lists.
- Duplicates — the same permutations appear multiple times.
What we actually want is:
ghci> foo [1,2]
[[1], [2], [1,2], [2,1]]The issue is that permutations is being applied to the outer list rather than to each sublist individually. We need to map permutations over each element and then flatten the result into a single list.
Once again, Haskell to the rescue! There’s a function for this - concatMap.
concatMap takes a function as an argument, and a list, and applies the function to each element of the list, concatenating the results as it goes.
ghci> (concatMap permutations . drop 1 . subsequences) [1,2]
[[1],[2],[1,2],[2,1]]Nice! Let’s put this into a function:
-- generate every possible selection and order of numbers
subsetPermutations :: [Int] -> [[Int]]
subsetPermutations = concatMap permutations . drop 1 . subsequencesNow that we can generate all possible combinations of numbers, we need to think about building up expressions.
Splitting Lists #
Arithmetic operations are binary in that they take 2 arguments. So it’d be nice to organise our number permutations into left and right sublists: an expression like (1 + 2) + (3 + 4) comes
from splitting [1, 2, 3, 4] into [1, 2] and [3, 4].
What we want to do is take a list of numbers and split them like so:
ghci> someSplittingFunction [1,2,3]
[([1], [2,3]), ([1,2], [3])]There’s a couple of interesting functions we could use: inits and tails. Let’s see what they do:
ghci> inits [1,2,3]
[[],[1],[1,2],[1,2,3]]
ghci> tails [1,2,3]
[[1,2,3],[2,3],[3],[]]inits returns a list built from each of the initial segments of the list, starting from []. tails does the same but in reverse.
If we zip these two lists together, we get a little closer to our desired result:
ghci> zip (inits [1,2,3]) (tails [1,2,3])
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]Let’s remove the first and last element, since they’ll always contain the empty list:
ghci> init . drop 1 $ zip (inits [1,2,3]) (tails [1,2,3])
[([1],[2,3]),([1,2],[3])]Perfect! Let’s put this into its own function:
-- Split a list into all possible (Left, Right) pairs
split :: [Int] -> [([Int], [Int])]
split xs = init . drop 1 $ zip (inits xs) (tails xs)Combining Expressions #
Next we’ll think about combining potential expressions.
We’ll call our function combine, and it’s type will be Expressions -> Expressions -> Expressions, using our Expressions type from earlier.
Some example behaviour:
ghci> combine [(Val 3, 3)] [(Val 10, 10)]
[(3 + 10,13),(3 * 10,30)] # no '-' here since 3 < 10, and no '/' since 3 doesn't divide 10 evenly
ghci> combine [(Val 120, 120)] [(Exp Add (Val 10) (Val 30), 40)]
[(120 + (10 + 30), 160), (120 * (10 + 30), 4800),
(120 - (10 + 30), 80), (120 / (10 + 30), 3)]In combine, we’ll need to pull out each of the individual expressions from the left and right Expressions list, and try and apply each of the operations in ops, only keeping expressions which are valid.
Once we have our new value and expression, we can build the new Expressions list.
combine :: Expressions -> Expressions -> Expressions
combine lefts rights =
[ (Exp op leftExpr rightExpr, val)
| (leftExpr, leftVal) <- lefts, -- pull from the left expr list
(rightExpr, rightVal) <- rights, -- pull from the right expr list
op <- ops, -- pull from the ops list
Just val <- [apply op leftVal rightVal] -- only keep successful results
]Generating Expressions #
Now we’ll think about generating expressions from a list of numbers.
Our goal is a function that will take a particular permutation of our number list, and generate all possible expressions from that list.
Our allExprs function will have type [Int] -> Expressions.
Given a list of numbers (such as [1,2,3]), we want to:
- Split the list into lefts and rights:
[([1], [2,3]), ([1,2], [3])]. - Recursively produce all the valid expressions for each left and right.
combinethe results.
-- take a list of nums and build
-- every valid Expr tree possible
-- for that specific ordering
allExprs :: [Int] -> Expressions
allExprs [n] = [(Val n, n)]
allExprs ns = do
(leftSide, rightSide) <- split ns
combine (allExprs leftSide) (allExprs rightSide)Putting It All Together #
Now we’ve got the core logic down, let’s define our solve function to generate solutions to the Countdown problem (if they exist).
solve will take a list of numbers and a target, and will produce a list of strings representing each of the solutions.
The execution flow of solve will be:
- Generate all the possible
subsetPermutationsfrom our number list. - Generate
allExprsvalid for each permutation. - This will produce expressions which equal the target (if possible), as well as expressions which don’t, so we’ll need a way of only keeping expressions which equal the target.
solve :: [Int] -> Int -> [String]
solve ns target =
[ show expr
| subset <- subsetPermutations ns,
(expr, val) <- allExprs subset,
val == target
]Here’s the complete solution:
|
|
Running #
Let’s take our solver for a spin!
We’ll load the program into ghci and enable telemetry. We’ll try our solver out on the example in the video on the homepage of this project.
ghci> :l BruteCountdown.hs
ghci> :set +s
ghci> solve [25, 50, 75, 100, 3, 6] 952
...
ghci> (23.53 secs, 6,405,928,856 bytes)Whoa! That’s both memory-and-time-hungry! Let’s find out why.
The Three Sources of Complexity #
There are three causes of the inefficiency.
Subsets #
For our 6 numbers, there are \(2^{6}-1=63\) non-empty subsets we need to consider, since we aren’t required to use all of the numbers.
Permutations #
For each subset of size \(k\) from \(1\) up to \(6\), there are \(k!\) orderings.
Summing across all subset sizes:
| Subset size \(k\) | Ways to choose | Permutations (\(k!\)) | Total |
|---|---|---|---|
| 1 | 6 | 1 | 6 |
| 2 | 15 | 2 | 30 |
| 3 | 20 | 6 | 120 |
| 4 | 15 | 24 | 360 |
| 5 | 6 | 120 | 720 |
| 6 | 1 | 720 | 720 |
| Total | 1,956 |
Expression Trees - Catalan Numbers #
For a fixed ordered list of \(n\) numbers, the number of ways we can group the numbers with ( and ), in other words the number of distinct binary tree shapes, is the \((n-1)^{th}\) Catalan number:
The Catalan numbers grow rapidly: \(1, 1, 2, 5, 14, 42, 132, \cdots\)
For 6 numbers, there are 42 distinct tree shapes. Each internal node can be one of 4 operators, and with \(n\) numbers there are \(n-1\) internal nodes, giving \(4^{n-1}\) operator assignments per tree shape.
So for \(n\) numbers, the total expressions are:
$$C_{n-1} \times 4^{n-1} $$| \(n\) | Catalan(\(n-1\)) | \(4^{n-1}\) | Expressions |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 4 | 4 |
| 3 | 2 | 16 | 32 |
| 4 | 5 | 64 | 320 |
| 5 | 14 | 256 | 3,584 |
| 6 | 42 | 1,024 | 43,008 |
Grand Total #
Multiplying all three factors together and summing:
| \(k\) | Ordered subsets | Expressions per ordering | Total |
|---|---|---|---|
| 1 | 6 | 1 | 6 |
| 2 | 30 | 4 | 120 |
| 3 | 120 | 32 | 3,840 |
| 4 | 360 | 320 | 115,200 |
| 5 | 720 | 3,584 | 2,580,480 |
| 6 | 720 | 43,008 | 30,965,760 |
| Total | ~33.7 million |
Conclusion #
We’ve built a working Countdown solver in Haskell. Starting from first principles, we defined types for operations and expressions, generated all possible subset permutations of our number list, and combined them into every valid expression tree — filtering out rule violations along the way.
But as the numbers make clear, “working” and “efficient” are very different things. At roughly 33.7 million expressions to evaluate, it’s no surprise we’re looking at 23 seconds and over 6GB of allocations. The brute-force approach leaves a lot on the table.
The good news is that all three sources of complexity we identified — subsets, permutations, and expression trees — offer room for improvement. In Part 2, we’ll look at how we can prune the search space aggressively, cutting out entire branches of computation before we ever evaluate them. The goal: the same correct answers, in a fraction of the time.