Advent of Code 2020 (3rd week)

There’s been some days in which I really struggled to find a working solution (that provides an answer in a reasonable amount of time) and I didn’t even try day 20, but overall I’m really happy to have arrived that far.

Day 14: Docking Data#

Docking Data could be seen as another VM problem, as it was day 7 . But this one was only about changing an input mask and writing values to memory addresses.

The hardest thing for me was to expand masked inputs to generate all the possible addresses.

👨‍💻 My solution

Day 15: Rambunctious Recitation#

That one hit home. The problem seemed easy enough (it was about expanding a sequence to find the nth term given a couple of rules). I saw in Reddit that many people had issues understanding the description. Surprisingly, that was not my problem today. So, after some back and forth I got my method providing the 2,020th value of the spoken number series.

For part 2 I was expecting some changes (complications) on the generation rules but instead the question simply to get the 30,000,000th number spoken. Damn it. My method required reversing the sequence and finding an index by value in every iteration!, so I knew I was fucked.

I improved my solution using a dictionary to store the latest index of every spoken number and I finally got my answer in about 20 seconds. Far from optimal, for sure, but good enough.

👨‍💻 My solution

Day 16: Ticket Translation#

That puzzle required more data parsing than the usual and, to be honest, I like that. I understand that programming puzzles are meant to be about algorithms and complexity, not parsing text. But at the same time, parsing is usually an easy challenge that I find sort of relaxing.

Once the data was parsed, we got some rules (being each rule a key and a couple of integer ranges), our ticket (a list of integers) and a list of nearby tickets.

The puzzle was about using the list of tickets together with the rules in order to find out the meaning of each number on the ticket. To solve it I iterated over the list of tickets finding key candidates where rules were satisfied for that particular index in all tickets. When I found an index with just one candidate, I ruled that one out and continued with the others.

Unfortunately, with my method, two iterations to the list of tickets where required in order to find the solution. I’d like to know if a single one should be enough but honestly, I’m doing AoC after work and I don’t have that much time left to think about optimisations.

👨‍💻 My solution

Day 17: Conway Cubes#

Another puzzle inspired in Conway’s Game of Life, like in day 11. This time it was in 3D, with cubes but there wasn’t a size limited grid so you didn’t have to care about edges when looking for cubes’ neighbours. So it was, in fact, easier than day 11 to me.

Part 2 was just adding another dimension to the problem. Having a good data model for part 1 it was just a matter to add an extra coordinate.

I learned about itertools .

👨‍💻 My solution

Day 18: Operation Order#

As the name suggests, Operation Order, was a problem about modifying operator precedence in arithmetic expressions with integers, additions, multiplications and parentheses.

Part 1 was about ignoring the usual precedence of product before addition (respecting parentheses though), and I solved it using two stacks (one for operators and another for operands) as well as recursivity for expressions within parentheses.

Part 2 was the first puzzle that I left unsolved this year. The challenge this time was to invert the usual precedence making addition to be evaluated before multiplication. I thought about it for a while without coming out with anything useful and at the end I ran out of time…

👨‍💻 My solution

Day 19: Monster Messages#

I had a hard time with this one. The problem input was some kind of context-free grammar like:

0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

that would generate strings with "a" and "b" characters. As well as some messages for which you should tell if they could be generated by that grammar or not.

The specific question Your goal is to determine the number of messages that completely match rule 0. […] How many messages completely match rule 0? tricked me into trying to generate all the possible strings (the problem made it clear that there weren’t any loops in the rules) to just compare with the messages afterwards. I ended up with multiple nested lists that I couldn’t manage to successfully flatten into the strings.

After a while I realised that I could convert these nested lists into regular expressions and just match them with the messages… and it worked!

Part 2, as you could expect, introduced loops by modifying a couple of rules in the input:

8: 42 | 42 8
11: 42 31 | 42 11 31

I must say I cheated this one with an ad-hoc solution that modified the output for these specific rules for something that’d fit my regular expressions solution:

loops = {
	'8': '( 42 + )',
	'11': '( 42 31 | 42 {2} 31 {2} | 42 {3} 31 {3} | 42 {4} 31 {4} | 42 {5} 31 {5} | 42 {6} 42 {6} )'
}

Obviously I’m not specially proud of this one, but it got the job done.

👨‍💻 My solution

Day 20: Jurassic Jigsaw#

Jurassic Jigsaw was the only puzzle for which I didn’t even get the first star. I started in late evening, it was Sunday, and the problem looked pretty complex… so I started creating some methods to get the borders of the tiles, I investigated how to use NumPy for flipping and rotating arrays… and then I just gave up before even trying to write the algorithm to put everything together.

🤷‍♂️ No solution