Day 17: Set and Forget
by Simon Berger
Links:
Before you read any further, please just take a second to look at the immense amount of code I’ve written for today’s puzzle.
All good? Then let me state the obvious: Yes, it’s a lot.
Seeing how much I wrote today got me curious about the other days so I hastily threw together this chart:
This begs the question, “why?”. Disappointingly, it’s just because I wrote a lot of abstractions from scratch. For example, there are 90 lines for dealing with euclidean vectors. I also implemented the Display trait for most types which takes up a lot of lines. In terms of actual puzzle logic most of the lines are spent on the second part, but we’ll get there in a minute.
What’s interesting about today’s puzzle is that both parts are easier solved by hand. The first part still seems like something you can code in a reasonable amount of time compared to how long it would take to solve by hand, but identifying three different repeating parts in the path for the second part is much harder to put into code than it is to by hand. I’m not interested in “Advent of solving problems by hand” though, so of course I solved them using code.
After writing all the helper code like the vector construct I started working on the first part. I wrote a function which generates all points on the path in the appropriate order. To get the crossings the code follows the path and keeps track of each visited point. If a point is visited a second time, it must be a crossing. All that was left to do for the first part was to calculate the checksum.
The second part starts very similarly, but this time we need to generate the instructions for the robot to follow the path. To get the instructions I had to adjust the path generating function so that it no longer generates the points on the path but instead the move(s) required to get to the next corner. The problem is that we can’t just send this to the robot, we have to “compress” the instructions by finding three distinct subroutines which can be combined to build the entire path. I opted to use a recursive algorithm which keeps trying subroutines of increasing lengths until it finds three that describe the entire path with no leftovers. After determining these routines they are sent to the robot and we wait until it finishes. All that’s left to do is to read the robot’s output.
That probably makes it sound rather easy and I guess it is, once you find out a reliable method to determine the subroutines.
This post is probably all over the place. I spent way too much time on the code today, so I’m rushing through this to compensate. Before I stop I just want to mention that I really enjoyed the second part. I don’t really know why it resonated with me that much, it’s just something about the challenge of compressing the instructions that really got me.
tags: advent-of-code - rustOverview
Previous day Next day