View all possible solutions for a Countdown numbers round in tree form.
If you haven't seen Countdown, it's a game show. Watch a quick numbers round. The numbers round goes like this:
- Contestants have 30 seconds to reach the target number using a sequence of calculations from 6 input numbers. e.g
75, 25, 100, 9, 2, 3how can you make
170? One way is
100 - 2 - 3 + 75.
- The target number is a three digit number. The input numbers will be positive integers less than or equal to 100.
- At no stage during calculations can negative numbers or fractions be used.
- For the more detailed constraints please read.
How it works
- Solver. The algorithm iterates through all permutations of the input numbers by brute force. This is run in a web worker so as not to block the main thread.
- Tree layout algorithm. The main thread keeps a tree in memory. As each solution is yielded from the web worker, the main thread adds it to the tree. The tree is then run through a homegrown layout algorithm to absolutely position the nodes and edges. The algorithm works by keeping track of nodes at any given depth and what the right most node of the partial tree is at any time. Each node is then positioned as far left as possible provided it's greater than previous siblings at that depth and the right most node. (Explanation assumes vertical layout).
- Tree drawing in svg. Using
lines are absolutely positioned.
- For fun I also worked out how many possible expressions there are.
- For fun I also threw together a solver for the word round.