3 min read

Advent of Code 2020 Day 18

The real issue is that I didn't have any easy test string to look for those issues, but when I first did the string replace option, I THOUGHT I might encounter it, but didn't end up thinking I really would encounter a problem, I guess I was wrong.
Advent of Code 2020 Day 18

I spent roughly 3 hours painstakingly debugging my day 18 part 2 code, because I used String.replace() rather than doing sub-string insertion, and because of that, I frustrated myself beyond no other. What did I learn today? things that work won't always necessarily work in all cases.  And when I made the decision to do what I did, I knew it could always be problematic, but I figured that I would be unlikely to hit that condition, well, I hit it.  I want to go through the example that caused me problems, but to explain the puzzle for day 18 first. The general idea of this puzzle was that you're given an equation and you have to find the result of that equation. The difference is that in the two different parts, parentheses still operate first, but in part one, multiplication and addition happen in order, for example 1 + 2 * 3 would be 9, whereas with normal mathematics it would be 7.  Another example is below

  Part 1 math                   PEMDAS Math
1 + 2 * (3 + 4)               1 + 2 * (3 + 4)
   1 + 2 * 7                     1 + 2 * 7
     3 * 7                         1 + 14
       21                            15

In part two, the modification is that rather than multiplication before division (as it is in standard math) it throws in addition before multiplication. Continuing from another example, 1 + 2 * 3 + 4 with PEMDAS math would be 11 with part one math, it would be 13 and with the part two math, it would be 21.  With this, you can see how these operations can become pretty complicated. Now, onto the example that caused me to have issues

Looking at step-by-step output for part two on the following string:

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

is as follows:

7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (8 * (2 + 7 * 5) * 6 * 5 * 5) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (8 * (  9 * 5  ) * 6 * 5 * 5) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (    8 * 45 * 6 * 5 * 5     ) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (     360 * 6 * 5 * 5       ) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (       2160 * 5 * 5        ) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (         10800 * 5         ) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * (           54000           ) + 5
7 * 4 * (6 + 3 + 2 * 9 + (7 * 5 + 4 * 5 * 9)) * 54005
7 * 4 * (6 + 3 + 2 * 9 + (  7 * 9 * 5 * 9  )) * 54005
7 * 4 * (6 + 3 + 2 * 9 + (    63 * 5 * 9   )) * 54005
7 * 4 * (6 + 3 + 2 * 9 + (     315 * 9     )) * 54005
7 * 4 * (6 + 3 + 2 * 9 + (      2835       )) * 54005
7 * 4 * (        6 + 3 + 2 * 9 + 2835       ) * 54005
7 * 4 * (           9 + 2 * 9 + 2835        ) * 54005
7 * 4 * (              11 * 11835           ) * 54005
7 * 4 *                 130185                * 54005
7 * 4 * 130185 * 54005
28 * 130185 * 54005
3645180 * 54005
196857945900

The issue happens from step 14 to 15, shortened here is the two lines:

7 * 4 * (9 + 2 * 9 + 2835) * 54005
7 * 4 * (11 * 11835) * 54005

As you can see, when 9 + 2 processes, it does a string replacement for all instances of 9 + 2 to be 11 but the second half inside the parentheses is 9 + 2835 so this is for sure not valid.  The actual result is much lower than 196,857,945,900 it ends up being 47,305,787,760.  Fortunately, this string was pretty high up in my list (ended up being the about 48th equation in the list of about 380 total) so I was able to catch it quickly and go from a find/replace in the string to an addition of 3 substrings based on where the match was found.  The real issue is that I didn't have any easy test string to look for those issues, but when I first did the string replace option, I THOUGHT I might encounter it, but didn't end up thinking I really would encounter a problem, I guess I was wrong.  If you want to join my Advent of Code leaderboard, feel free to join with the code: 699615-aae0e8af.

Enjoying these posts? Subscribe for more