Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Choose every operator as the final combination: The Expression Splits.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Divide and conquer expression evaluation matches the clues
- 2Keep this true after every move: solve(segment) returns every value from every parenthesization of that exact segment
- 3Reach the result within Catalan-sized output with memoized substrings
Rules and pressure
- Target cost: Catalan-sized output with memoized substrings
- State rule: solve(segment) returns every value from every parenthesization of that exact segment
Lesson 1 of 3
Live algorithm trace
Divide and conquer expression evaluation
Complete execution1 of 5
2
*
operator
3
-
4
*
5
Every operator is considered as the final operation.
1
solve(expression segment)2
for each operator position3
solve left and right substrings4
combine every left and right result5
if no operator: parse the number6
memoize and return all resultsexpression = 2*3-4*5rootChoices = *, -, *
Truth to preserve / Cost target
Truth to preserve
solve(segment) returns every value from every parenthesization of that exact segment
Cost target
Catalan-sized output with memoized substrings
Each operator may be the root of the expression tree. Recursively compute every result from its left and right substrings, then combine their Cartesian product.
Your call · What should guide every step of this algorithm?