Hello, there and welcome to my Advent of Code 2020 Day 7 cruise log. Oh my! This one was fun, Anakin would appreciate that this is where the fun begins. I knew that the ease of yesterday’s challenge only trumped us into a false sense of security for day 7.
Today’s was surprisingly easy. However I feel like @ericwastl gave us a false sense of security before a bomb drops tomorrow.
— Jean-Dominique Nguele (@CodingNagger) December 6, 2020
Of course, this wasn’t an Avengers level threat yet but it definitely tickled my brain. I found the first part mixed in terms of difficulty, the parsing was fairly easy to tackle. After all, people used to call me ParseMan back at the engineering school for the preposterous amount of parsers I’d create for any problem. I changed my ways since but I still very much enjoy it when I get to write some parsing logic.
As you’d expect, I started by writing tests for the parsing logic first to create rules. I feel like rules engines will be this year’s thread. Day 2 already featured something with a parse/handle rule shape. Back to the tests, the tests were fairly easy to write. First, a test to make sure a single rule gets parsed, then add another for a ruleset, etc. Unsurprisingly, the parsing tests passed at the first attempt so I guess I still have my ParseMan mojo. After that, I added another test using the subject’s example and cracked on with coding Part 1.
For that part, recursion seemed to be the easy path through but generally, with these sort of tests, recursion is the last thing you want to do. Recursion-based solutions will definitely work with the small data samples provided in examples, that’s for sure. However, it fails miserably at returning results in a timely manner on larger datasets akin to Advent of Code inputs. As you know, time is of the essence to score points and try to rank up in here.
From there I had to go with an iterative solution, using a visiting algorithm. This is pretty effective. First, you initialise your stack with your starting point. Then you iterate over your stack until it becomes empty. Until then, you pop your next visiting key from your stack, continue to the next iteration if already visited or mark it as visited. Finally, you do your business there.
No big hurdle there, it just took me time to really wrap my head around the description to have the right logic in. But once that was done I went full speed implementing. Still took me an hour though but all the tests passed on the first try. As for part 2, I thought it looked much easier than the first but I felt like there was a trap somewhere so I slowed down the pace. I wrote some more tests, they passed, then I ran through my input. Fingers crossed. I got the marine screen of death. My result was too low.
Doubt installs itself, were all my tests wrong or was something missing? Then I realised “even if the nesting becomes topologically impractical” was the last sentence of this part’s description. For this one, I need to ignore that I already visited the bag colours and go through these again and again. That makes sense, you can have a bag colour available in several other bags. I missed a test. After adding a test, my algorithm failed as expected.
That theory being confirmed I removed the visitation checks and the test passed. Now I reran my input and it passed.
Thank you for reading my Advent of Code 2020 Day 7 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 so feel free to check it out but not before you’ve done the challenge yourself. Bye!