The distress signal leads you to a giant waterfall! Actually, hang on - the signal seems like it's coming from the waterfall itself, and that doesn't make any sense. However, you do notice a little path that leads behind the waterfall.
Correction: the distress signal leads you behind a giant waterfall! There seems to be a large cave system here, and the signal definitely leads further inside.
As you begin to make your way deeper underground, you feel the ground rumble for a moment. Sand begins pouring into the cave! If you don't quickly figure out where the sand is going, you could quickly become trapped!
Fortunately, your familiarity with analyzing the path of falling material will come in handy here. You scan a two-dimensional vertical slice of the cave above you (your puzzle input) and discover that it is mostly air with structures made of rock.
Your scan traces the path of each solid rock structure and reports the x,y coordinates that form the shape of the path, where x represents distance to the right and y represents distance down. Each path appears as a single line of text in your scan. After the first point of each path, each point indicates the end of a straight horizontal or vertical line to be drawn from the previous point. For example:
498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
This scan means that there are two paths of rock; the first path consists of two straight lines, and the second path consists of three straight lines. (Specifically, the first path consists of a line of rock from 498,4 through 498,6 and another line of rock from 498,6 through 496,6.)
The sand is pouring into the cave from point 500,0.
Drawing rock as #, air as ., and the source of the sand as +, this becomes:
4 5 5
9 0 0
4 0 3
0 ......+...
1 ..........
2 ..........
3 ..........
4 ....#...##
5 ....#...#.
6 ..###...#.
7 ........#.
8 ........#.
9 #########.
Sand is produced one unit at a time, and the next unit of sand is not produced until the previous unit of sand comes to rest. A unit of sand is large enough to fill one tile of air in your scan.
A unit of sand always falls down one step if possible. If the tile immediately below is blocked (by rock or sand), the unit of sand attempts to instead move diagonally one step down and to the left. If that tile is blocked, the unit of sand attempts to instead move diagonally one step down and to the right. Sand keeps moving as long as it is able to do so, at each step trying to move down, then down-left, then down-right. If all three possible destinations are blocked, the unit of sand comes to rest and no longer moves, at which point the next unit of sand is created back at the source.
So, drawing sand that has come to rest as o, the first unit of sand simply falls straight down and then stops:
......+...
..........
..........
..........
....#...##
....#...#.
..###...#.
........#.
......o.#.
#########.
The second unit of sand then falls straight down, lands on the first one, and then comes to rest to its left:
......+...
..........
..........
..........
....#...##
....#...#.
..###...#.
........#.
.....oo.#.
#########.
After a total of five units of sand have come to rest, they form this pattern:
......+...
..........
..........
..........
....#...##
....#...#.
..###...#.
......o.#.
....oooo#.
#########.
After a total of 22 units of sand:
......+...
..........
......o...
.....ooo..
....#ooo##
....#ooo#.
..###ooo#.
....oooo#.
...ooooo#.
#########.
Finally, only two more units of sand can possibly come to rest:
......+...
..........
......o...
.....ooo..
....#ooo##
...o#ooo#.
..###ooo#.
....oooo#.
.o.ooooo#.
#########.
Once all 24 units of sand shown above have come to rest, all further sand flows out the bottom, falling into the endless void. Just for fun, the path any new sand takes before falling forever is shown here with ~:
.......+...
.......~...
......~o...
.....~ooo..
....~#ooo##
...~o#ooo#.
..~###ooo#.
..~..oooo#.
.~o.ooooo#.
~#########.
~..........
~..........
~..........
Using your scan, simulate the falling sand. How many units of sand come to rest before sand starts flowing into the abyss below?
# Python imports
from pathlib import Path
test = Path("data/day14_test.txt") # test data
data = Path("data/day14_data.txt") # puzzle data
def coord_to_tuple(input: str) -> tuple[int, int]:
"""Return co-ordinate as integer tuple
:param input: coordinate in xpos,ypos format
"""
return tuple([int(_) for _ in input.split(",")])
def parse_input(fpath: Path) -> set[tuple[int, int]]:
"""Parse puzzle input: locations of walls/blocked tiles
:param fpath: path to puzzle input
"""
blocked = set() # holds co-ordinates blocked by a wall
# Read in wall locations
with fpath.open() as ifh:
for line in [_.strip() for _ in ifh.readlines()]: # one "wall" per line
coords = line.split(" -> ") # separator indicates wall continues between coords
last_coord = coord_to_tuple(coords.pop(0)) # get "last" coordinate for wall
blocked.add(last_coord) # block last_coord location
while len(coords): # iterate over remaining wall turns, blocking connecting tiles
next_coord = coord_to_tuple(coords.pop(0)) # end of next section
blocked.add((next_coord)) # block end of next section
if last_coord[0] == next_coord[0]: # vertical wall: block tiles vertically
for ypos in range(min(last_coord[1], next_coord[1]), max(last_coord[1], next_coord[1]) + 1):
blocked.add((last_coord[0], ypos))
elif last_coord[1] == next_coord[1]: # horizontal wall: block tiles horizontally
for xpos in range(min(last_coord[0], next_coord[0]), max(last_coord[0], next_coord[0]) + 1):
blocked.add((xpos, last_coord[1]))
last_coord = next_coord # start next section from end of current section
return blocked
def release_sand(walls: set[tuple[int, int]], floor: bool=False) -> int:
"""Return the number of sand grains needed
:param walls: locations of blocked tiles
:param floor: true for part 2, where there is a floor to the chamber
For part 1, the number of sand grains that settle before new sand grains
end up falling forever is returned.
For part 2, the number of sand grains that fall before the sand inlet
gets blocked is returned
The trick here is to realise that, for larger problems, the number of
sand grains and positions they take in their paths as as they fall
rapidly becomes unmanageable. So that we don't need to consider an
exponentially-increasing number of movements as the number of grains
increases, we recognise that each grain either comes to rest or (in
part 1) falls forever. If it falls forever (in part 1), we halt the
process, but if it comes to rest we try a new grain. The new grain
will follow the last grain up until the point it meets the last grain,
so we can skip all the intermediate points in the grain's fall, up to
that last point.
To implement this, we keep a list/stack that holds the last grain's
falling path, and start new grains from the end of it.
This helps with part 2 because, when the sand inlet is blocked (the
end state for part 2), the list is empty, and we can test for this to
halt the solution.
"""
blocked_count = len(walls) # initial number of blocked tiles
max_ywall = max([_[1] for _ in walls]) # lowest point in any wall
settled_count = 0 # number of settled sand grains (puzzle solution)
fallpath = [(500, 0)] # holds fall path for sand, we start from the sand inlet.
# In part 2 we need to account for the floor of the chamber
if floor: # we're in part 2
floorlevel = max([_[1] for _ in walls]) + 2 # floor is two units below lowest wall
# iterate dropping sand until no more can settle - in part 1 because
# all new grains will be in freefall; in part 2 because the inlet is
# blocked; return settled_count to halt the solution
while True:
if floor and len(fallpath) == 0: # we've blocked the entrance
return settled_count
sandpos = fallpath.pop() # we start our sand grain from the last known good position
settled = False # our grain is falling
while settled is False: # We follow the grain as it falls
fallpath.append(sandpos) # extend the grain falling path
# Try falling
for nextpos in [(sandpos[0], sandpos[1] + 1), # vertically
(sandpos[0] - 1, sandpos[1] + 1), # tumble left
(sandpos[0] + 1, sandpos[1] + 1)]: # tumble right
settled = True # assume settled unless the grain...
if nextpos not in walls: # ...can fall into the next space
sandpos = nextpos # can fall, so update position
settled = False # we're still falling
break # don't test any more spaces
if floor and sandpos[1] == floorlevel - 1: # we've hit the floor
settled = True # this grain has settled
if settled: # Sand grain has settled
settled_count += 1 # update count of settled grains (the solution)
walls.add(sandpos) # update set of blocked tiles
fallpath.pop() # move one step back in the path to model the next grain
if not floor and nextpos[1] > max_ywall: # No floor, but sand in freefall
return settled_count
def part1(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
walls = parse_input(fpath)
settled = release_sand(walls)
return settled
part1(test)
24
part1(data)
793
You realize you misread the scan. There isn't an endless void at the bottom of the scan - there's floor, and you're standing on it!
You don't have time to scan the floor, so assume the floor is an infinite horizontal line with a y coordinate equal to two plus the highest y coordinate of any point in your scan.
In the example above, the highest y coordinate of any point is 9, and so the floor is at y=11. (This is as if your scan contained one extra rock path like -infinity,11 -> infinity,11.) With the added floor, the example above now looks like this:
...........+........
....................
....................
....................
.........#...##.....
.........#...#......
.......###...#......
.............#......
.............#......
.....#########......
....................
<-- etc #################### etc -->
To find somewhere safe to stand, you'll need to simulate falling sand until a unit of sand comes to rest at 500,0, blocking the source entirely and stopping the flow of sand into the cave. In the example above, the situation finally looks like this after 93 units of sand come to rest:
............o............
...........ooo...........
..........ooooo..........
.........ooooooo.........
........oo#ooo##o........
.......ooo#ooo#ooo.......
......oo###ooo#oooo......
.....oooo.oooo#ooooo.....
....oooooooooo#oooooo....
...ooo#########ooooooo...
..ooooo.......ooooooooo..
#########################
Using your scan, simulate the falling sand until the source of the sand becomes blocked. How many units of sand come to rest?
def part2(fpath: Path) -> int:
"""Solve the puzzle
:param fpath: path to puzzle input
"""
walls = parse_input(fpath)
settled = release_sand(walls, floor=True)
return settled
part2(test)
93
part2(data)
24166