Hello, there and welcome to my Advent of Code 2020 Day 18 cruise log. This one hurts, I still got it right in the end but it pains me that it took so long. Four hours, four freaking hours. I can’t believe this. Especially considering how I finished it in the end. At least I didn’t need a hint but maybe had I asked for one I could have been done in less than half the time. Let’s start with the storyline or as I call it for clarity, the lore.
The story starts back on a plane, as we hover over a continent with a pesky child. At that moment, my heart fills with the hope that I can reuse my clean rework of day 8. From there, you can imagine the disappointment when I saw that instead of playing with the game console code I get to do maths. Well, thank you for nothing. The kid wants us to help him with his math homework. But the rules changed, no operator precedence we process the expression from left to right. Simple in real life but we have to code this thing.
The first part took me quite some time to process, you know the 5 am brain thing, but through TDD, I got something working. At least for most examples. Then there was that one pesky example starting which just wouldn’t pass. After some crafty debugging I can spot that the difference is that this expression starts with a parenthesis.
My logic would push my current expression into a stack so that when the parenthesis closes I compound it with the last value from the stack. However, that example reveals a flow. When the first expression begins with a parenthesis I have no current expression to push into the stack. As a result, I push an empty value which I can’t combine with anything. The fix for that is filthy but works well, I push a product struct with a left value of 1. That way I turn “(2 + 3)” into “1 * (2 + 3)” which solves the issue.
Once I fix this first bug, I run all my tests and they pass. A sigh of relief, but I am not off the hook yet. I run the daily input against the algorithm and collect the first star of the day after about an hour and a half. Still long but I forgive myself and my foggy brain for this, plus these issues are far from trivial to tackle. Looking at my company leaderboard, almost a hundred and fifty people took part this year but only 35 completed day 17 so far.
Now the part I dread, not because I think it will be very hard but because this is where I started stuttering last year. I only completed the first part of day 18 last year and spent an insane amount of time on part two before giving up and trying to tackle other days. The delay got me falling too far to even clinch top five of the company. Even though I completed days 19 and 21 to try and catch up I eventually gave up. I’m not so interested in the problems as I am in performing. No prize, no glory so no point in making any further effort.
With all that in mind, I started reading the topic with undue apprehension, focusing on the shame of getting stuck again rather than the problem at hand. I shouldn’t be surprised that it took me so long in the end. Only one thing changed from the first part, we now have precedence. Additions get processed before multiplications, always. I thought I would just introduce a precedence stack and be done with it. My early tests pass so I think I will breeze through this.
Quite presumptuously, I give a go at running my code against the input. It fails, the answer is too low. Not quite sure what is wrong with my code, it feels quite sound, well almost. Actually, the precedence check didn’t handle parentheses well. Now that I’m writing this, I feel foolish for not changing course right then and there. Instead, I dug myself further into a hole, the worst part is that it almost worked. I juggled with a stack to handle addition precedence alongside my parenthesis. So much duplication, the Kaminoans would be jealous. The ugliest code I wrote in a long time, and I wrote a fair share of it over time.
Eventually, all the tests pass but the second star still refuses itself to me. Then I add all the example inputs and they all pass but one. There is still some dodgy stuff going on with my parenthesis and the additions precedence. However, it is much rarer. Let’s fast forward the next two hours of me digging around, printing my expression tree on each round straight to where I give up.
As I’m mentally preparing myself to surrender and saying goodbye to any hope of finishing this morning, my girlfriend walks in. She asks if I’m still on that coding thing, I acquiesce. Then she suggests me to take a break and go for breakfast. I hesitate for a moment, if I could not solve this in more than three hours and a half I won’t solve it in the next five minutes so I accept. But first, I’ll have one last-ditch effort to see if I can make anything sensible enough to return to in five minutes. Deep down, I know that if I can’t do that, the Advent of Code and this blog series will come to an end. It would be a shame that this advent of code 2020 day 18 log never see the light of day.
This is the part where I delete my whole part two code and decide to start afresh. Instead of doing wild stuff with parenthesis and stacks, I go for a different approach. One I actually thought about when working on the first part but I thought it would be too difficult to implement. And yet genius me ended up with something even more complex which doesn’t even work. I still have a method to parse operations but it doesn’t deal with parenthesis anymore. However, now I process the expression as a string and iterate through it until and replace the innermost parenthesis expressions with their result.
Within thirty minutes, my then broken tests pass again as I execute them one by one. Getting confident, I run all my tests at once and they all pass. I run the code against my input and it works. The pressure drops as I, relieved, drop a few F-bombs at how stupid I was for not doing that earlier. But at last, I can write that post, push that code and never look at it nor discuss it ever again. Even though I will need to delay my workout to tonight, I can find solace that day 18 is now behind me. Time to get to work.
Thank you for reading my Advent of Code 2020 Day 18 cruise log, I will see you tomorrow, maybe. In the meantime, you can check out my Go Cloud series about building and deploying a Golang app to AWS. Also, I will push my code on Github at CodingNagger/advent-of-code-2020. Feel free to check it out but not before you’ve done the challenge yourself. Bye!
Photo by Ian Panelo from Pexels
A colleague mentioned later that a way to solve this easily would be to use the the Shunting-yard algorithm. I feel like I saw that before and it kinda looks like my part one logic without looking like it. Not sure it changed that much in my case but I’ll never find out. https://en.wikipedia.org/wiki/Shunting-yard_algorithm