Hello, there and welcome to my Advent of Code 2020 Day 21 cruise log. Today feels much better than yesterday, I actually managed to wrap up both Day 20 and Day 21 before 7 am. But it didn’t start merrily. You may wonder where is my Day 20 log, I didn’t write it. Truth is that until 4.55 am this morning I didn’t know I would. That is the time at which I finally took my 40th star of the Advent of Code. Only five minutes before today’s challenge. Don’t worry, I will write a log for it soon, but first I want to write this before it evaporates. Also, I do need to do a post-mortem of Day 20. Potentially redo it from scratch before pushing my code later today.
Now, back on the lore, after helping elves detect monsters on Day 20, we now reach our final stop before the holiday destination. No way to get there without getting wet and there are no boats going that way. However, our resourceful our hero has a raft and only needs some food to sail a few days. The problem is that the food has ingredients listed in a foreign language nobody can read and only allergens are legible. Our input is a list of food with encoded ingredients and legible allergens. The trap is that allergens aren’t necessarily listed for the ingredients that contain them. We will need to proceed by elimination.
As you may guess, the first part consists of detecting which encoded ingredients can’t have any allergen for sure. This part felt easier than usual. This may be because, for the first time since the start of this Advent of Code, I didn’t rush into coding something. Instead, I took out a pen and paper from the get-go and went through the examples to figure an algorithm.
After a few minutes, of parsing the subject, maybe thirty or so, I realised I could get rid of the examples obfuscations. I did so by replacing the random encoded strings with letters from A to G based on when they first appear. Also, I replaced allergens with numbers from 1 to 3. It got so much easier to read and iterate through. From there, I through what my algorithm’s state should be for one iteration, then another. This would serve as a basis for my tests. About forty minutes in, I had my algorithm on lock and started coding. First the tests, then the implementation, always. About half an hour later, I captured my first star of the day, and it felt excellent, especially after day 20.
Now, it’s time to tackle the second part. I felt some apprehension but had the feeling that this time, for the first time in forever, my first part code would fully be useful. And it was! As a result of the first part, I had a map that paired my allergens with some allergen candidates. The allergen candidates were the ingredients that appeared at least once with that allergen.
My second part algorithm would go through that map and delete all the candidates that didn’t have the maximal number of appearances for that allergen. At the end of that process, I would have at least one allergen with a single ingredient. From there I can just delete that ingredient from other allergens’ candidate list and store it in a map where the key is the paired allergen.
At that point, I iterate over my allergen candidates map until my resulting map matches it in length. This would mean that all the allergen are paired to a unique ingredient. It took longer to think through than to code but it was fairly quick. Only half an hour after capturing my 41st star, I captured the 42nd and went back to bed. I will need the rest before doing the post-mortem of day 20 and work out. Good thing that I am on leave from today so that I can recover more.
Thank you for reading my Advent of Code 2020 Day 21 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!
Cover by Leonie Fahjen from Pexels
