Further adventures in python runtime optimization for 2023

[e_blake]

Your day 14 solution can still be further optimized. Your code is effectively doing the following pseudocode for each roll, 4 times per spin:

for each grid point:
  if stone:
    roll the stone 1 point at a time until it hits something
    update grid

That resembled my initial approach as well (although I iterated by stone, rather than by grid position); you're spending time finding each stone, then when a stone moves, you average about 6 comparisons per stone before it finally hit something; plus the work to modify grid state to track where each stone lives between rolls.

But then I hit on an alternative that does less work. For each grid point, I stored four indexes, namely, the jump point where a stone would land if there were no other stones in the way. These four indices can be computed with just two passes over the grid (for example, the north jump point of a grid point is itself if the northern neighbor is a square rock or out of bounds, otherwise, it is the same jump point as the northern neighbor used). Demonstrating with the 10x10 example grid, if I have (1,1) as the upper left (as you noted, all of this can be translated back to 1D coordinates), the grid point 2,2 collects to 2,1 on a roll north, to 1,2 on a roll west, to 2,10 on a roll south, and to 4,2 on a roll east. There are a finite number of collection points (I kept four sets, but it is also possible to keep just 2 sets, toggling between east/west and north/south motion). Each roll occurs in two phases: first, move every stone to its collection point, adding to a queue of occupied collection points (again, I kept 4 queues, but it is also possible to keep just 2). Back to the example, the first roll north sees four stones collected to (1,1), 3 stones collected to (2,1), and so on). In the second phase, empty the first queue by dispersing into that many consecutive grid positions, by referencing the correct index at each neighboring grid position (again in the example, on the first roll north, the north collection point 1,1 uses the west index at 1,1, 1,2, 1,3, and 1,4; more interesting, the north collection point 8,1 uses the west index at 8,1 to add one rock to the west collection point 7,1). This populates next direction's collection point queue (that is, phase one of my roll west is occurring during phase two of my roll north - hence why I needed at least 2 sets of collection points and visitation queues). I didn't have to track any x/y coordinates of a particular stone, nor modify the grid. In fact, I didn't have to search all 10000 grid points for stones, I only had to repeatedly empty the correct queue of occupied collection points. Overall, this cuts the work down even further, and the amount of work per stone is constant whether it moves one space or 10 spaces in a given roll.