Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Prune prefixes that can never close correctly: The Balanced Branches.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Generate parentheses matches the clues
- 2Keep this true after every move: every path prefix has closes <= opens <= n
- 3Reach the result within Catalan output time
Rules and pressure
- Target cost: Catalan output time
- State rule: every path prefix has closes <= opens <= n
Lesson 1 of 3
Live algorithm trace
Generate parentheses
Complete execution1 of 5
(
token
(
)
(
)
)
Only an opening parenthesis is legal at the root.
1
search(path, opens, closes)2
if length is 2n: record3
if opens < n: append open4
if closes < opens: append close5
undo each choice6
return resultsn = 3opens = 0closes = 0
Truth to preserve / Cost target
Truth to preserve
every path prefix has closes <= opens <= n
Cost target
Catalan output time
A prefix may open while opens remain, and may close only when more opens than closes have been used. These constraints prevent invalid strings from entering the tree.
Your call · What should guide every step of this algorithm?