Advent of Code 2020 Day 18
Task: Solve for X where...
X = the sum of each evaluated expression
Example input
1 + (2 * 3) + (4 * (5 + 6))
It represents:
- A math equation
- Where sub-equations inside parentheses are evaluated first when encountered
- Evaluation proceeds left-to-right, unlike normal order of mathematical operations
Computer science skills that seem relevant include:
- Recursion
- Regular expressions
- Mapping and Reducing (multi-dimensional?) arrays
- String traversal, maybe?
Analyzing my puzzle input
- Numbers are limited to digits 2-9 - so, single-character, non-zero, positive digits only
- No occurrences of ((( or ))), though that doesn't rule out the existence of a 3-level deep equation somewhere in the middle of a 2-level deep equation
- Equations that span between 2 and ~50 operands
Part 1
- Trying my hardest to think algorithmically
- Trying to analyze another solver's algorithm
Trying my hardest to think algorithmically
When I analyze this example diagram...
1 + (2 * 3) + (4 * (5 + 6))
1 + 6 + (4 * (5 + 6))
7 + (4 * (5 + 6))
7 + (4 * 11 )
7 + 44
51
...I think about:
- Using recursion to evaluate each of the equations inside the parentheses
- Using regular expressions to identify each parenthesis-wrapped clause
- Using a hellishly-overcomplicated series of if..else clauses to traverse each equation string, character by character, to arrive at a final number
Sadly, I struggle to map out or visualize how I would attack this puzzle using any of these three tactics.
Trying to analyze another solver's algorithm
JavaScript solver NullDev used two regular expressions as part of their solution.
Regex 1:
/\(([^()]+)\)/
Regex 2:
/(\d+) ([+*]) (\d+)/
I immediately understood Regex 2:
- Match one or more digits
- Then a single space
- Then either
+
or*
characters - Then a single space
- Then one or more digits
It matches these strings:
3 * 2
or 5 + 9
I eventually understood Regex 1:
- Match an open parenthesis (
- Match one or more non-parentheses characters
- Match a closing parenthesis )
It matches this string:
(7 * 4)
And thanks to Regexr.com I saw that it only matches the inner set in this string:
(5 + (3 * 4))
It then seems that the core algorithm does the following:
As long as the equation string has at least one more space character:
Reassign to equation the result of the following test:
Does the equation have any more parentheses?
Replace the entire match when testing for Regex 1 with the solution of the first capture group when testing for Regex 1
If the equation doesn't have any more parentheses
Replace the entire match when testing for Regex 2 with the result of the following test:
Does the second matched capture group contain only a + character?
Return the sum of the number-coerced first and third matched capture groups
Does the second matched capture group contain only a * character?
Return the product of the number-coerced first and third matched capture groups
Return the resulting number
Quitting early with my head only slightly raised
- I retreat from this puzzle satisfied only in that I understood both Regexes in NullDev's solution.
- I'm bummed that I continue to struggle solving puzzles that rely on Regex, recursion or indeterminate-length substring manipulation.
- But I recognize that this puzzle is beyond my grasp.
- At least my recent Regex practice is proving helpful!
Top comments (0)