Advent of Code 2020: Day 18 Order of Operations (Arithmetic)

As I had written in a previous blog post, I participated in the Advent of Code, 25 programming problems to help improve my skills. I maintained really good momentum through day 20 before holiday activities forced me to pause. (Bonus: I have 5 really solid problems to play with for the next month.)

One of the best aspects of such a side activity is discussing the problems with some of my colleagues, and seeing the different approaches. It was important we treated the discussion as a open and safe space. Of course there are wrong answers, the underlying problem needs to be solved. But there are many different ways to approach and implement the solution including non-optimal ones. It was not meant to be a code golf challenge: rather by experimenting with unfamiliar aspects of our programming languages and solving abstract problems, we deepened our expertise.

I particularly enjoyed problem Day 18. Perhaps you remember your PEMDAS (order of arithmetic operations) from junior high. The Day 18 problem jumbled the notion of PEMDAS and asked to evaluate expressions if operations were evaluated “strictly left to right” or “addition comes before multiplication.” (The horror…)

My solution involved mapping the ‘depth’ of an expression wrt parentheses, then building a method to do the custom expression evaluation. Wrapping the two in iteration, I could then slice, divide, and conquer the expression to obtain the final result. Here’s an example of an expression, where the updated depth map is followed by the sliced expression selected for evaluation and finally replaced. This keeps drilling down until the entire expression has been evaluated:

### addition before multiplication ###

 (3+6+7+9)*(2+(4*7*6+9+3+5)+9+(2+3+7+4+3)+9)+8

"(3+6+7+9)*(2+(4*7*6+9+3+5)+9+(2+3+7+4+3)+9)+8"
 111111111011122222222222221112222222222211100
               4*7*6+9+3+5
               644
              ___
"(3+6+7+9)*(2+644+9+(2+3+7+4+3)+9)+8"
 11111111101111111112222222222211100
                     2+3+7+4+3
                     19
                    __
"(3+6+7+9)*(2+644+9+19+9)+8"
 11111111101111111111111100
  3+6+7+9
  25
 __ 
"25*(2+644+9+19+9)+8"
 0001111111111111100
     2+644+9+19+9
     683
    ___
"25*683+8"

line_value: 17275 

How did my colleagues approach this?

  • David – used a clever regex to find the ‘deepest’ pair of parentheses, then evaluated the contained expression, and repeat as long as there was a ‘(‘ character remaining in the expression.
  • Josh – employed a similar regex recognition, but wrapped his solution in a very tidy `map()` for an almost minified look. By using less memory, Josh is minimizing his electricity consumption and saving the environment!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s