Module aoc::year2022::day14

Regolith Reservoir

We could simulate each grain of sand falling one at a time, for example:

    #o#    # #    # #    # #
    # #    #o#    # #    # #
    # # => # # => #o# => # #
    # #    # #    # #    #o#
    ###    ###    ###    ###

In this example it would take 4 steps to simulate the first grain, 3 steps for the second and so on. More generally it would take ∑n = n * (n + 1) / 2 or O(n²) complexity for the whole pile.

We instead simulate in O(n) complexity by recursively check each grain’s underneath neighbors until we have a conclusive result then propagating that back up the call stack, for example:

    #?#    #?#    #?#    #?#    #?#    #?#    #?#    #o#
    # #    #?#    #?#    #?#    #?#    #?#    #o#    #o#
    # # => # # => #?# => #?# => #?# => #o# => #o# => #o#
    # #    # #    # #    #?#    #o#    #o#    #o#    #o#
    ###    ###    ###    ###    ###    ###    ###    ###

We model the cave as a grid in the possible states:

• Air Empty blocks, treated as unknown status when checking underneath neighbors.
• Falling Grains of sand that will continue to fall continously forever.
• Stopped Both original rock walls and any grains of sand that have come to rest.

Structs

• Cave

Enums

• Kind 🔒

Functions

• parse
  Creates a 2D grid cave exactly the maximum possible size.
• part1
  If a grain of sand reaches the floor it will fall forever.
• part2
  The floor is solid rock.
• simulate 🔒