Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Carry just enough state to reject an illegal one: The Binary Branches.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Recursive binary decision tree matches the clues
- 2Keep this true after every move: the current path has the requested prefix length and contains no adjacent ones
- 3Reach the result within O(Fibonacci(n)) output-sensitive time
Rules and pressure
- Target cost: O(Fibonacci(n)) output-sensitive time
- State rule: the current path has the requested prefix length and contains no adjacent ones
Lesson 1 of 3
Live algorithm trace
Recursive binary decision tree
Complete execution1 of 5
node
0
00
01
10
101
Begin at the root with no chosen bits.
1
search(path, previousOne)2
if path length is n: record it3
always append 0 and recurse4
if previous bit was not 15
append 1 and recurse6
undo after each branchn = 3path = emptypreviousOne = false
Truth to preserve / Cost target
Truth to preserve
the current path has the requested prefix length and contains no adjacent ones
Cost target
O(Fibonacci(n)) output-sensitive time
At every position choose 0 or 1. The previous bit is sufficient state to prune a 1 after another 1, while the path itself records the candidate.
Your call · What should guide every step of this algorithm?