2023 Day 21: Step Counter

Advent of Code
1

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 :tm:, 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.
             +-+
             |H|
           +-+-+-+
           |G|F|G|
         +-+-+-+-+-+
         |G|E|D|E|G|
       +-+-+-+-+-+-+-+
       |G|E|C|B|C|E|G|
     +-+-+-+-+-+-+-+-+-+
     |H|F|D|B|A|B|D|F|H|
     +-+-+-+-+-+-+-+-+-+
       |G|E|C|B|C|E|G|
       +-+-+-+-+-+-+-+
         |G|E|D|E|G|
         +-+-+-+-+-+
           |G|F|G|
           +-+-+-+
             |H|
             +-+
  • 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 G, E, and C; or, the column with just G and 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…

2

:grin: :dark_sunglasses: :grinning:
:fireworks: :sunglasses: :sparkler:
:tada: :birthday: :cake:

The approach described above works.

Well… essentially it works. A couple of corrections:

  • The values for A, B, D, F, H, … alternate.
  • Aside from the cardinal directions, add another cell on each side. You’ll need those values, too.
  • You’ll need formulas for the sums of the first x-1 even number and the first x odd numbers, where x is as described above.
  • For me, the pattern was as follows
|    |    |    | 911|5357| 932|    |    |    |
|    |    | 911|6224|7193|6215| 932|    |    |
|    | 911|6224|7193|7082|7193|6215| 932|    |
| 911|6224|7193|7082|7193|7082|7193|7082| 932|
|5348|7193|7028|7193|7082|7193|7028|7193|5340|
| 917|6206|7193|7028|7193|7028|7193|6207| 929|
|    | 917|6206|7193|7028|7193|6207| 929|    |
|    |    | 917|6206|7193|6207| 929|    |    |
|    |    |    | 917|5331| 929|    |    |    |

Your numbers will likely differ, but the general pattern should be the same.

3

Something I have noticed is that the borders of the example and of my data (and perhaps all data) are completely free. So once you reach the border of the startup square, the conquest of the next squares is perhaps easier to compute.
Something that people on Reddit noticed is that the S point is at the centre the startup square and that the odd number of columns & rows might play a role.

1 Like
4

True in my data, and probably for the reason you give. I forgot to mention it; it’s one of the assumptions underlying my claim that you reach other squares with a certain regularity.

I hadn’t looked at Reddit yet and was wondering if any other approach was possible! :grin: Yes, my start was also in the center, and I assumed it along with the borders and the middle lines being clear, as that implies the symmetry shown in my diagram above.

I had not thought about the odd number of columns and rows. I suspect that affects only the alternating pattern of values of “filled” boxes that you see in my diagram.

5

The more I think about this, the more I think I’m wrong.

That aside, I’ve now uploaded to GitHub a solution that should work for any input, with the caveat that some constants may have to be changed to match the user’s input. (I had a 131x131 initial square, and had to find the number of plots visited on the 26,501,365th step.)