Module day18

RAM Run

We use a trick to speed things up. Instead of storing # and . in the grid, we store the time when a block arrives. For example:

           ...#...    ∞ ∞ ∞ 3 ∞ ∞ ∞
    5,4    ..#....    ∞ ∞ 4 ∞ ∞ ∞ ∞
    4,2    ....#..    ∞ ∞ ∞ ∞ 1 ∞ ∞
    4,5 => ....... => ∞ ∞ ∞ ∞ ∞ ∞ ∞
    3,0    .....#.    ∞ ∞ ∞ ∞ ∞ 0 ∞
    2,1    ....#..    ∞ ∞ ∞ ∞ 2 ∞ ∞
           .......    ∞ ∞ ∞ ∞ ∞ ∞ ∞

Now we can BFS from any arbitrary start time. Squares are safe if the grid time is greater than the start time.

Part two uses an incremental flood fill, getting a little further each time and removing blocking bytes in descending order of time until we reach the exit.

• Start with t = i32::MAX
• Start flood fill from top-left origin.
• If we encounter a blocking byte with a time less than t then push (time, position) onto a max heap keyed by time.
• If we exhaust the flood fill VecDeque then pop the heap’s top item. This is the oldest byte that we encountered blocking the way. Set t to the byte’s time and push position to the dequeue.
• Restart flood fill from new position until we reach the exit.

Functions

• parse
• part1
  BFS from start to exit using a fixed time of 1024.
• part2
  Incremental flood fill that removes one blocking byte at a time in descending order.