Advent of Code - 2022
This is a solution to Day 14 of Advent of Code 2022.
Day 14 - Regolith Reservoir
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,9This 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?
Today's puzzle had four distinct phases for me:
- Understanding the puzzle
- Parsing the input and creating the data structure
- Coding the problem
- Waiting for my slow loop to execute (we'll get back to that)
Surprisingly, part 3 was the easiest for me. I expected this kind of puzzle to be a big challenge but it turned out that my only real mistake was calculating the position of the floor on every loop, from an evergrowing set. Once I refactored that out, everything worked out perfectly.
Read input
The provided input comes in a form of series of points that form the corners of the walls.
I decided to use set for my datastructure: we're only interested in which coordinates are filled and really nothing else so set is great for that.
For the coordinate system, I used the complex number coordinates system that I learned last year: the real part of the complex number denotes the X coordinate and the imaginary part is the Y coordinate. It's not the most readable and requires more knowledge than a (x, y) system that I'd guess most people are familiar with. But it makes math so nice as we'll see later.
To create our initial cave, I split each line to points and then calculate all coordinates between those two points. In the end, I put all of them into a one big set.
from utils import read_input, flatten
from collections import namedtuple
from itertools import pairwise
def get_line(start, end):
"""
Gets all the points on a straight line
>>> get_line((498,4), (498,6))
[(498+4j), (498+5j), (498+6j)]
>>> get_line((498,6),(496,6))
[(498+6j), (497+6j), (496+6j)]
"""
line = []
x0, y0 = start
x1, y1 = end
assert x0 == x1 or y0 == y1
if x0 == x1:
step = 1 if y0 < y1 else -1
return [x0+y*1j for y in range(y0, y1+step, step)]
else:
step = 1 if x0 < x1 else -1
return [x+y0*1j for x in range(x0, x1+step, step)]
def transformer(line):
points = line.split(' -> ')
positions = set()
for start, end in pairwise(points):
x0, y0 = [int(p) for p in start.split(',')]
x1, y1 = [int(p) for p in end.split(',')]
midpoints = get_line((x0, y0), (x1, y1))
positions = positions | set(midpoints)
return positions
cave = set(flatten(read_input(14, transformer)))I then built a few helper functions to make the main code cleaner.
get_floor(cave) finds the lowest point, so we can know when we've hit the void.
left, right and down calculate the next possible positions (left here means left-and-down and same for right). Here we can see how nice using the complex numbers is: instead of a return (current[0] - 1, current[1] + 1), we just add two numbers together.
def get_floor(cave):
return int(max(pos.imag for pos in cave))
def left(current):
"""
>>> left(500+0j)
(499+1j)
"""
return current + (-1+1j)
def right(current):
"""
>>> right(500+0j)
(501+1j)
"""
return current + (1+1j)
def down(current):
"""
>>> down(500+0j)
(500+1j)
"""
return current + 1jshould_stop is the powerhouse of this solution as it checks whether a pebble of sand should stop or not. If all the three possible positions are filled already or we've gone past the bottom, it should stop.
next_position calculates the next position for the sand to go.
def should_stop(cave, current):
"""
>>> should_stop({(494+9j), (495+9j), (496+6j),(496+9j),(497+6j),(497+9j)}, 500+0j)
False
>>> should_stop({499+1j, 500+1j, 501+1j}, 500+0j)
True
"""
return (
down(current) in cave and
left(current) in cave and
right(current) in cave
)
def next_position(cave, current):
if (
down(current) in cave and
left(current) in cave and
right(current) in cave
):
return None
if (d := down(current)) not in cave:
return d
if (l := left(current)) not in cave:
return l
if (r := right(current)) not in cave:
return r
return None
def in_void(current, floor):
return current.imag > floorTo simulate our sand falling into cave, we define the start point as (500, 0) (or 500+0j in our system), get the bottom of the cave and execute our loop until we enter the void (a sand goes below the lowest floor).
For each sand, we loop until it stops and if on any step we fall into the void, we return out.
After a sand pebble has stopped, we add its final place to the cave as filled position and start over.
def simulate(cave):
current = 500+0j
rounds = 0
floor = get_floor(cave)
while True:
while not should_stop(cave, current):
current = next_position(cave, current)
if in_void(current, floor):
return rounds
rounds += 1
cave.add(current)
current = 500+0jsands = simulate(cave.copy())
print(f'Part 1: {sands}')
assert sands == 768Part 2
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?
For this second part, two changes were required:
-
The stopping criteria for our execution moved from "entered the void" to "we stopped right away"
-
We had infinite floor at the bottom
To check for the first, I check if the next position for the sand to stop on would be the starting position.
To make testing easier, instead of modeling an infinite floor, I just added a floor that span 1000 units both ways at the correct y coordinate.
def simulate_2(cave):
current = 500+0j
rounds = 0
while True:
while not should_stop(cave, current):
current = next_position(cave, current)
rounds += 1
if current == 500+0j:
return rounds
cave.add(current)
current = 500+0j
def add_floor(cave):
floor_level = get_floor(cave) + 2
xs = [int(pos.real) for pos in cave]
left_limit = min(xs) - 1000
right_limit = max(xs) + 1000
floor = get_line((left_limit, floor_level), (right_limit, floor_level))
cave = cave | set(floor)
return cavepart2 = set(flatten(read_input(14, transformer)))
part2 = add_floor(part2.copy())
final_count = simulate_2(part2)
print(f'Part 2: {final_count}')
assert final_count == 26686