I’ve only finished Part 1 so far, but here are some thoughts on Part 2. While it’s not implemented yet, it should be the right track: when testing it by hand on a much smaller example, I come too close to the brute-force answer to make me think the mistakes are anything other than due to hand computation / numbers-slightly-off / etc.
Sorry if this seems far too long, too detailed, or too annoying with blurred spoilers-which-perhaps-aren’t, but if anyone sees an invalid assumption, I would be grateful!
- Once the elf visits a plot, he cannot visit it again except on multiples of 2, on account of the limited number of directions available. That is, if he first visits the plot in row 5, column 12 on step 7, then he will only visit that plot on odd-numbered steps.
- In my input, and I suspect in all inputs, the number of steps is 65 + x * 131, where x is a Very Large Number , 131 is the dimension of the square, and 65 is the number of steps it takes to get from the starting point, which is in the middle, to the end of the square.
- Unlike the example – and this is a big deal! – the row and column in the middle are completely clear, so that the shortest route to the 4 adjacent squares require no turns at all.
- As the elf explores, you get a nearly diamond-shaped pattern for the number of steps required to first reach a square. In the diagram below, all B’s at the same time, all C’s at the same time, all D’s at the same time, etc.
- You can thus consider separately squares along the cardinal directions (north, south, east, west), and the other squares.
- Remember x from above? That’s the number of squares visited in the cardinal directions, but they’re not all full: the elf hasn’t taken enough steps to fill the four at the end. We’ll return to this speed bump in a moment.
- In each column not in a cardinal direction (e.g., the column with squares
C; or, the column with just
E), the number of full squares decreases by 2 each index you move further away from a cardinal direction.
- So it’s relatively easy to count the number of full squares, so you can count the number of plots in those squares the elf can visit on the desired step based on whether it’s even or odd (as noted above). That product gives the number of plots the elf can visit in all the full squares. Don’t forget to add the number in the center box!
- Likewise, it should be relatively easy to brute-force count the number of plots the elf visits in squares that aren’t full, because you know the shortest number of steps it takes to arrive there, and you can explore from that entrace position. Again, the fact that movement is limited to the cardinal directions helps you here: in a box to the northwest of A, for instance, the earliest entrance is in a southeast corner, so explore from there for the number of steps remaining.
- Add the values in these last two steps and you should have the answer.
I suspect the reason my hand computation is wrong is that I’m slightly off on the next-to-last step. I’ll look at it more later…