DEV Community

Robert Mion
Robert Mion

Posted on

Operation Order

Advent of Code 2020 Day 18

Task: Solve for X where...

X = the sum of each evaluated expression
Enter fullscreen mode Exit fullscreen mode

Example input

1 + (2 * 3) + (4 * (5 + 6))
Enter fullscreen mode Exit fullscreen mode

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

  1. Trying my hardest to think algorithmically
  2. 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
Enter fullscreen mode Exit fullscreen mode

...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+)/
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)