Module aoc::year2023::day22

source ·
Expand description

§Sand Slabs

Inspecting the input provides a useful insight. The x and y coordinates of bricks are restricted to between to 0 and 9 inclusive so the final shape of the pile will resemble a tall narrow tower similar to a Jenga game.

A second insight is that this is a graph problem in disguise. Sorting the bricks in ascending z order is equivalent to a topological sort where each brick is a node and a directed edge links bricks that support other bricks.

By iterating over each brick in order its final resting location and supporting bricks can be calculated immediately. For example taking the first 3 example bricks:

    Brick               Heights    Indices

    1,0,1~1,2,1 <- A    0 1 0      X 0 X    Already in final position
                        0 1 0      X 0 X
                        0 1 0      X 0 X

    0,0,2~2,0,2 <- B    2 2 2      1 1 1    Already in final position
                        0 1 0      X 0 X
                        0 1 0      X 0 X

    0,2,3~2,2,3 <- C    2 2 2      1 1 1    Moves downwards by 1
                        0 1 0      X 0 X
                        2 2 2      2 2 2

§Part One

If a brick is supported by only a single brick then the parent brick cannot be safely removed so we mark it as unsafe. Mutiple bricks could potentially be independently supported by a single parent brick so using a boolean flag means that we won’t overcount.

§Part Two

Unsafe bricks are a dominator in graph theory as every path from the root (floor) to bricks supported by them must pass through the unsafe node.

To count the total number of bricks that fall when all unsafe bricks are removed one at a time we build a linked list of bricks as we iterate through the nodes. Each brick has a depth which is the number of unsafe “dominator” nodes that connect it to the root. For example:


    Depth   0     1     2     1     0
          | A ┬-> B --> C ┬-> D ┬-> E
          |   |           |     |
    Floor |   └-> F ------┘     |
          | G ------------------┘
  • A and G rest on the floor so their depth is 0 as they can never fall.
  • B and F are both supported only by A so their depth is 1.
  • C will fall if either A or B is removed so its depth is 2.
  • D will only fall when A is removed. Removing F would leave it supported by B and C or vice-versa. The common ancestor of the path to the root is A so its depth is 1.
  • E’s common ancestor is the floor so its depth is 0.

In total 0 (A) + 0 (G) + 1 (B) + 1 (F) + 2 (C) + 1 (D) + 0 (E) = 5 bricks will fall.

Functions§

Type Aliases§