Module aoc::year2023::day14

Parabolic Reflector Dish

To solve part two we look for a cycle where the dish returns to a previously seen state. By storing each dish and a index in a HashMap we can calculate the offset and length of the cycle then use that to find to state at the billionth step.

Calculating the state needs to be done sequentially so we use some tricks to make it as fast as possible.

First the location of each each ball is stored in a vec. My input had ~2,000 balls compared to 10,000 grid squares total, so this approach reduces the amount of data to scan by 5x. The 2D coordinates are converted so a 1D number, for example the index of a ball on the second row second column would be 1 * 100 + 1 = 101.

Next for each possible tilt orientation (north, south, east and west) an approach similar to a prefix sum is used. Each edge or fixed rock is assigned an index. We expand the grid by 2 in each direction (one for each edge) to handles the edges. For example, using west (left):

    ..#.#..

is represented in fixed_west as (noticing the extra 0 for the left edge)

    0 0 0 1 1 2 2 2

The the number of balls the come to rest against each fixed point is counted, for example:

    OO#.#OO

is stored in roll_west similar to:

   2 0 2

This approach has two huge advantages:

First, the number of balls resting against each fixed point completely represents the state of the grid in a very compact format. For example my input has ~1600 fixed points. Using 2 bytes per point needs 3.2K total to represent the grid, compared to 100 * 100 = 10K for the simple approach. 3x less data is 3x faster to hash when storing states in a HashMap looking for duplicates.

Second, calculating the new position of a ball is very fast. For each ball:

• Use fixed_* to lookup the index in the corresponding roll_* vec.
• This stores the current index of the last ball resting against that fixed point.
• Increment this value by ±1 for horizontal movement or ±width for vertical movement and then update the new location of this ball.

For example, tilting a single row west, processing each ball from left to right where each line represent the new state would look like:

   grid              rounded         fixed_west                       roll_west
   .O#..O.OO.#..O    [1 5 7 8 13]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [-1 2 10]
   O.#..O.OO.#..O    [0 5 7 8 13]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [0 2 10]
   O.#O...OO.#..O    [0 3 7 8 13]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [0 3 10]
   O.#OO...O.#..O    [0 3 4 8 13]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [0 4 10]
   O.#OOO....#..O    [0 3 4 5 13]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [0 5 10]
   O.#OOO....#O..    [0 3 4 5 11]    [0 0 1 1 1 1 1 1 1 1 2 2 2 2]    [0 5 11]

Structs

• Input

Functions

• parse
• part1
• part2
• tilt 🔒
  Very fast calculation of new state after tilting in the specified direction.