2 min read

Advent of Code 2020 Day 19

Advent of Code 2020 Day 19

The days are getting more difficult, and today's puzzle was no exception to the rule. I saw the puzzle come live at 11:00 pm on December 18, did some work to read in the file, and then needed to rest my head as I was exhausted from a long day of work and other things so I went to bed, thinking of how to solve the puzzle. When I woke up, I had AN idea of generating all of the possible strings based on the rules.  The example was short enough that I could think of it in my head without issues, and I knew that generating the possible strings would take a lot of time (because it's super recursive) but also would expand pretty quickly with more and more rules being added (like the example input).

By generating the strings for part one, I was able to accomplish completing part one, but it took quite a while to generate all possible strings based on starting from rule 0. Part two introduced some "looping" into the fold where rules may be self-referencing (0: 1 | 1 0) for instance would allow for having effectively a variable number of the values of rule 1 in a row. This is potentially a bad example, but in part two, we had to replace some rules with new confirmations.  For me, rule 8 was 8: 42 and I had to replace it with 8: 42 | 42 8 and rule 11 was 11: 42 31 and I had to replace it with 11: 42 31 | 42 11 31. Because everyone's inputs are different, other people may have different changes in their rules. By the way, Eric (who owns Advent Of Code) does a great job dishing those out to people, and I just wish I could see the work that goes into generating the input for potentially hundreds of thousands of people.

For part two, I went from generating candidate strings to starting to match the string based on the input strings to check against, this means it's potentially a quick exit in certain scenarios, but typically means you have to follow through with the given rules completely before you fail things quickly. At that point, I switched over to the Rule interface that you see in my GitHub now which treats each portion of a rule "node" as one of 4 (or 5) different types, either an AndRule which is any space-delimited list of rules, OrRule which is any rule separated by the pipe |, EndRule which is any rule that ends up being one of the specified characters "a" or "b", ReferentialRule which is a rule that uses a rule number reference. Since it's possible that the ReferentialRule may refer to a rule id that doesn't technically exist, and because of that, we have a NilRule that simply returns an emptySet no matter what. All of that works with both part one and part two, the only difference is the overwriting of the two rule values for part two.

I think it's problems like these that I typically struggle with, because there's kind of an easy human approach, but for me, it's hard to get that human approach coded up. I really enjoy these puzzles, because it does help me to better get from human approach to computer approach going forward. 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