0099 : Email Tutorials ‐ FP 13 ‐ The Countdown Problem

FP13 Graham Hutton Video

Table of Contents

1. What is the Countdown Numbers Game?
2. The Game Rules (and why they matter for code)
3. Representing Arithmetic Operators in Haskell (Op)
4. Giving Operators Meaning (apply)
5. Enforcing Game Rules (valid)
6. Representing Expressions (Expr)
7. Evaluating Expressions with Failure (eval) using Lists
8. Formalizing “What is a solution?” (choices, values, solution)
9. Brute Force Solver (split, exprs, combine, solutions)
10. Why brute force is slow (invalid expressions dominate)
11. Program Fusion: generate + evaluate together (Result, results, solutions')
12. Further Optimization: exploiting commutativity + identity in valid (solutions'')
13. Summary: performance improvements and takeaways
14. Glossary
15. Mini-exercises (with solutions)

1) What is the Countdown Numbers Game?

You’re given:

• Source numbers (typically 6): e.g. 1, 3, 7, 10, 25, 50
• A target number: e.g. 765
• Allowed operators: + − × ÷

Goal: build an arithmetic expression using the source numbers (each at most once) that evaluates to the target.

Example solution for target 765:

• (25 - 10) * (50 + 1) = 15 * 51 = 765

Not every target is solvable (e.g. the lecture mentioned 831 as unsolvable for that source set).

2) The Game Rules (and why they matter for code)

Two key constraints drive the design:

1. Only positive natural numbers are allowed at every step:

   • No negatives (so 1 - 2 is invalid)
   • No zero
   • No fractions (so 2 / 4 is invalid)

2. Each source number may be used at most once.

These constraints are enforced in the solver by careful evaluation rules and validity checks.

3) Representing Operators (Op)

We declare a simple algebraic data type:

data Op = Add | Sub | Mul | Div

This is just structure—these names have meaning only once we define how to interpret them.

4) Giving Operators Meaning (apply)

apply executes an operator on two integers:

apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y

Note: division is integer division.

5) Enforcing Game Rules (valid)

valid checks whether applying an operator to two positive natural numbers stays within the allowed domain.

valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0

Interpretation:

• Add and Mul always keep you in positive naturals (given positive inputs).
• Sub must ensure x > y to avoid zero/negative results.
• Div must be exact (no remainder) to avoid fractions.

6) Representing Expressions (Expr)

An expression is either:

• a value like Val 25
• or applying an operator to two subexpressions

data Expr = Val Int | App Op Expr Expr

Example: 1 + 2 becomes:

App Add (Val 1) (Val 2)

7) Evaluating Expressions with Failure (eval)

We want evaluation to fail if it produces invalid intermediate results. The lecture uses a neat trick: represent “success/failure” using a list:

• Success: singleton list [n]
• Failure: empty list []

eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) =
  [ apply o x y
  | x <- eval l
  , y <- eval r
  , valid o x y
  ]

Why this works well:

• If eval l fails, it becomes [], and the whole list comprehension produces [].
• Same for eval r.
• If valid fails, the guard blocks that branch.
• List comprehensions automatically propagate failure without explicit if plumbing.

This is like using lists as a lightweight “maybe” / nondeterminism mechanism.

8) Formalizing “What is a solution?”

8.1 choices

choices generates all ways of selecting 0 or more elements from a list, allowing different orders. Example for [1,2] yields 5 results: [], [1], [2], [1,2], [2,1]

Type:

choices :: [a] -> [[a]]

8.2 values

Extract the leaf numbers in an expression:

values :: Expr -> [Int]
values (Val n)       = [n]
values (App _ l r)   = values l ++ values r

8.3 solution

A candidate expression is a solution if:

1. its values are one of the choices from the source numbers
2. eval e succeeds and equals the target

solution :: Expr -> [Int] -> Int -> Bool
solution e ns n =
  values e `elem` choices ns && eval e == [n]

This is a specification-style checker. It’s not meant to be fast yet.

9) Brute Force Solver

To actually find solutions, we generate candidate expressions and test them.

9.1 split

Split a list into two non-empty parts in all possible ways:

Example: split [1,2,3,4] gives: ([1],[2,3,4]), ([1,2],[3,4]), ([1,2,3],[4])

Type:

split :: [a] -> [([a],[a])]

9.2 exprs: generate all expressions using numbers in order

exprs :: [Int] -> [Expr]
exprs []  = []
exprs [n] = [Val n]
exprs ns  =
  [ e
  | (ls, rs) <- split ns
  , l        <- exprs ls
  , r        <- exprs rs
  , e        <- combine l r
  ]

9.3 combine

Combine two expressions with each operator:

combine :: Expr -> Expr -> [Expr]
combine l r = [App o l r | o <- [Add,Sub,Mul,Div]]

9.4 solutions: brute force search

solutions :: [Int] -> Int -> [Expr]
solutions ns n =
  [ e
  | ns' <- choices ns
  , e   <- exprs ns'
  , eval e == [n]
  ]

Works, but can be slow because it generates many expressions that later fail.

10) Why brute force is slow

Most generated expressions are invalid under the game rules. Lecture example: about 5 million valid expressions out of 33 million generated.

So we waste huge time generating expressions we’ll discard later.

11) Program Fusion: generate and evaluate together

11.1 Result

A “result” stores both:

• a valid expression
• its computed value

type Result = (Expr, Int)

11.2 results: fused generation + evaluation

Instead of generating expressions then evaluating them, generate only expressions that stay valid, and carry their values.

results :: [Int] -> [Result]
results []  = []
results [n] = [(Val n, n) | n > 0]
results ns  =
  [ res
  | (ls, rs) <- split ns
  , lx       <- results ls
  , ry       <- results rs
  , res      <- combine' lx ry
  ]

combine' combines two results while enforcing validity immediately:

combine' :: Result -> Result -> [Result]
combine' (l,x) (r,y) =
  [ (App o l r, apply o x y)
  | o <- [Add,Sub,Mul,Div]
  , valid o x y
  ]

Now invalid partial expressions are rejected early.

11.3 solutions': use fused results

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
  [ e
  | ns' <- choices ns
  , (e,m) <- results ns'
  , m == n
  ]

This is typically ~10x faster in the lecture timings.

12) Further optimization: exploit algebraic laws via valid

Many expressions are duplicates under properties like:

• commutativity: x + y same as y + x
• commutativity: x * y same as y * x
• identities: x * 1 = x, x + 0 = x (though 0 not allowed here)
• division by 1 is pointless

Trick: enforce constraints in valid so you don’t generate duplicates.

Optimized valid:

valid Add x y = x <= y
valid Sub x y = x > y
valid Mul x y = x /= 1 && y /= 1 && x <= y
valid Div x y = y /= 1 && x `mod` y == 0

Effect:

• Only allow Add and Mul in one “canonical order” (x <= y)
• Don’t multiply by 1
• Don’t divide by 1

This reduces search space dramatically and speeds up “all solutions” a lot.

13) Summary: What you learned from this lecture

• How to model a domain with ADTs (Op, Expr)
• How to represent failure cleanly with lists (eval :: Expr -> [Int])
• How to do brute force search using list comprehensions (solutions)
• Why naïve generate-and-test is slow
• How program fusion (combining generation and evaluation) improves performance
• How domain laws (commutativity/identity) can reduce duplicates and accelerate search

14) Glossary

• Brute force: try all possibilities, filter those that work.
• Search space: the set of all candidates you generate (often huge).
• Guard (in list comprehension): a boolean filter, e.g. , valid o x y.
• Program fusion: combine two sequential passes into one (generate + evaluate).
• Result: a paired structure (Expr, Int) carrying expression plus value.
• Canonical form: a rule (like x <= y) used to avoid duplicates.

15) Mini-exercises (with solutions)

Exercise A: Why does eval return a list?

Answer: It encodes failure/success with [] vs [n] and lets list comprehensions propagate failure automatically.

Exercise B: Write combine and combine'

Solution:

combine l r = [App o l r | o <- [Add,Sub,Mul,Div]]

combine' (l,x) (r,y) =
  [ (App o l r, apply o x y)
  | o <- [Add,Sub,Mul,Div]
  , valid o x y
  ]

Exercise C: Return just the values from results

Write resultsValues :: [Int] -> [Int] that collects all values produced.

Solution:

resultsValues :: [Int] -> [Int]
resultsValues ns = [v | (_, v) <- results ns]

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Quizz & Progress Badge NFT