Module aoc::year2023::day21

source ·
Expand description

§Step Counter

This solution uses a geometric approach. Looking at the input data reveals several crucial insights:

  • The sample data is a decoy and will not work with this solution.
  • The real input data has two special properties:
    • Vertical and horizontal “roads” run from the center.
    • The edge of the input is completely free of obstructions.

These properties mean that we can always cross a tile in exactly 131 steps. We start in the middle of a tile and need 65 steps to reach the edge. Part two asks how many plots can be reached in 26501365 steps.

    26501365 => 65 + 131 * n => n = 202300

The number of tiles that we can reach forms a rough diamond 202300 tiles wide. For example n = 2 looks like:

      #
     ###
    #####
     ###
      #

The next insight is that if we can reach a plot in x steps the we can also reach it in x + 2, x + 4... steps by repeatedly stepping back and forth 1 tile. This means the number of tiles reachable depends on the parity of a plot from the center, i.e. whether it is an odd or even number of steps. As the 131 width of the tile is an odd number of plots, the number of plots reachable flips from odd to even each time we cross a whole tile. There are n² even plots and (n + 1)² odd plots in the diamond.

      O
     OEO
    OEOEO
     OEO
      O

Lastly, we can only partially reach some tiles on the edges. Solid triangles represent corners that can be reached and hollow triangle represents corners that are too far away.

         ┌--┐
         |◸◹|
        ◢|  |◣
      ┌--┼--┼--┐
      |◸ |  | ◹|
     ◢|  |  |  |◣
   ┌--┼--┼--┼--┼--┐
   |◸ |  |  |  | ◹|
   |◺ |  |  |  | ◿|
   └--┼--┼--┼--┼--┘
     ◥|  |  |  |◤
      |◺ |  | ◿|
      └--┼--┼--┘
        ◥|  |◤
         |◺◿|
         └--┘

The total area is adjusted by:

  • Adding n extra even corners
        ◤◥
    ◣◢
  • Subtracting n + 1 odd corners
        ◸◹
    ◺◿

To find the values for the total number of odd, even plots and the unreachable odd corners we BFS from the center tile, counting odd and even plots separately. Any plots more than 65 steps from the center will be unreachable at the edges of the diamond.

One nuance is that to always correctly find the extra reachable even corner plots requires a second BFS starting from the corners and working inwards. All tiles within 64 steps are reachable at the edges of the diamond. For some inputs this happens to be the same as the number of tiles greater than 65 steps from the center by coincidence, however this is not guaranteed so a second BFS is more reliable solution.

Constants§

Functions§

  • bfs 🔒
    Breadth first search from any number of starting locations with a limit on maximum steps.
  • parse
  • part1
  • part2

Type Aliases§