DEV Community

Robert Mion
Robert Mion

Posted on

4 2

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!

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay