# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

# Advent of Code 2022 - Day 14

## Problem Intro

We’re in some sort of cavern, and we’re working within a vertical slice of this cavern. Within this vertical slice, there are lines of rock which are either horizontal or vertical.

Our input data describes these lines:

``````498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9
``````

Here, each row of input data represents a set of connected lines. Grains of sand are falling from the ceiling, from point `(500,0)`. We’re told that the sand falls until it comes to rest. If a grain of sand can move directly down, diagonally down left, or diagonally down right, it will.

## Part 1

How many units of sand come to rest before sand starts flowing into the abyss below?

Here’s my strategy:

Soln:

• Use a `Point` dataclass, as I often do!
• Create a `Line` class to represent lines of rock. A line has two points: start and end.
• Create a `Grid` class:
• It takes all the rock lines as input, and expands them into a `set` of all points tha make up rock.
• Create an empty `set` to store the positions where sand comes to rest.
• Create a filled `set` to represent the union of all points occupied by either rock or sand.
• Create `drop_sand()` method simulates the falling of a grain of sand.
• For an instance of our `grid` class, drop sand until sand starts falling into the abyss.

So first of all, the `Point` and `Line` classes:

``````@dataclass(frozen=True)
class Point():
x: int
y: int

@dataclass(frozen=True)
class Line():
start: Point
end: Point
``````

They have both been defined as immutable (i.e. unmodifiable) dataclasses. We need them to be immutable,so that we can store them in our `sets` later.

Now the method that reads the input data:

``````def process_lines(data):
lines = set()
for input_line in data:
point_coords = input_line.split(" -> ")
points = [Point(*map(int, coord.split(","))) for coord in point_coords]
for i in range(1, len(points)):

return lines
``````

Here I:

• Split each input line at the arrows, to return `x,y` cordinates that make up the successive vertices of a bunch of lines.
• Then use list comprehension to turn each `x,y` pair into two values, and use map to turn each value into an `int` representation. From here, we can contruct a `Point` for each point in the input data.
• Finally, iterate through every point from a given input line, and use these points to make `Line` objects. We return all the lines.

Now it’s time to construct our `Grid` class:

``````class Grid():
SAND_ORIGIN = Point(500,0)
SAND_VECTORS = [Point(0,1), Point(-1, 1), Point(1, 1)] # down, diagonal left, diagonal right

def __init__(self, lines: set[Line]) -> None:
self.rock: set[Point] = self._get_rock(lines)
self.sand = set()
self.min_x = min(point.x for point in self.rock)
self.max_x = max(point.x for point in self.rock)
self.min_y = min(point.y for point in self.rock)
self.max_y = max(point.y for point in self.rock)

def _get_rock(self, lines: set[Line]):
""" Process lines of rock. For each point in those lines, add a rock point to the set. """
rock = set()
for line in lines:
x_start = min(line.start.x, line.end.x)
x_end = max(line.start.x, line.end.x)
y_start = min(line.start.y, line.end.y)
y_end = max(line.start.y, line.end.y)
rock.update({Point(x,y) for x in range(x_start, x_end+1)
for y in range(y_start, y_end+1)})

return rock

def _is_empty(self, point: Point) -> bool:
""" If this point is not rock or sand, return True. """
if point not in self.rock and point not in self.sand:
return True

return False

def drop_sand(self) -> Point:
""" Sand falls down until it reaches an obstacle.
If it reaches an obstacle, it will they try to fall diagonally left, then diagonally right. """
grain = Grid.SAND_ORIGIN
falling = True
while falling:
for v in Grid.SAND_VECTORS:
candidate = Point(grain.x + v.x, grain.y + v.y)
if self._is_empty(candidate):
if candidate.x < self.min_x or candidate.x > self.max_x: # we've reached fall-through
return None

grain = candidate
self.min_y = min(self.min_y, grain.y)

break  # move out of the vectors loop
else: # Get here if all our fall positions are full
falling = False

return grain

def __str__(self) -> str:
rows = []
for y in range(self.min_y, self.max_y+1):
row = f"{y:3d} "

# print 1 col to either side
for x in range(self.min_x-1, self.max_x+2):
point = Point(x,y)
if point in self.rock:
row += "#"
continue
if point in self.sand:
row += "o"
continue
row += "."

rows.append(row)

return "\n".join(rows)
``````

How this works:

• Start by iterating over all the rock lines. For each line, determine all the points that make up the line. Add these points to the `self.rock set`.
• Then we set the bounds, i.e. the minimum and maximum x and y values of any rock in the grid.

At this point, if we were to print the grid using the sample data, the output looks like this:

``````  4 .....#...##.
5 .....#...#..
6 ...###...#..
7 .........#..
8 .........#..
9 .#########..
``````
• The `drop_sand()` method:
• Drops a sand grain from the top, i.e. from `500,0`.
• Sand grain falls according to rules, specified as three vectors: down, down-left, down-right.
• Iterate through the vectors. The next candidate point (i.e. where the grain might fall) is given by the current sand grain point, plus the vector.
• If the candidate point is empty, the sand can fall to it. If not, sand has stopped falling.
• Keep iterating until sand starts falling into the abyss. We know this is happening if the x coordinate is outside of the bounds.
• If sand has come to rest, return the grain point. If not, then return `None`.
• Back in `main()`, call `drop_sand()` until no more grains are returned (i.e. at rest).
• Then count `grid.sand`.

We do that with this code:

``````    grid = Grid(lines)

print(f"\n{grid}")
print(f"Part 1: resting grains={len(grid.sand)}")
``````

At this point, if we print the grid with the sample data, the output looks like this:

``````  1 ............
2 .......o....
3 ......ooo...
4 .....#ooo##.
5 ....o#ooo#..
6 ...###ooo#..
7 .....oooo#..
8 ..o.ooooo#..
9 .#########..
``````

## Part 2

Now we have a floor, at location `y+2` relative to lowest rock. Sand will keep falling until we’ve blocked the origin at (500,0).

How many units of sand come to rest?

My code changes as follows:

• `__init__()` now accepts a parameter to set whether we have a floor or not. This allows us to perform different logic, depending on whether we’re doing Part 1 or Part 2.
• If we do have a floor, set the `floor_y` accordingly, and update the other limits.
• Update the `is_empty()` method to now return `False` if the `point.y` location is the floor.
• Update `drop_sand()` method:
• If we have a floor and sand has come to rest there, update `x` and `y` limits if required.
• After adding sand to our sand set, if the grain added was the same as the `ORIGIN`, then this is the last grain we can drop, so return `None`.

The final code looks like this:

``````from dataclasses import dataclass
from pathlib import Path
import time

SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")

@dataclass(frozen=True)
class Point():
x: int
y: int

@dataclass(frozen=True)
class Line():
start: Point
end: Point

class Grid():
SAND_ORIGIN = Point(500,0)
SAND_VECTORS = [Point(0,1), Point(-1, 1), Point(1, 1)] # down, diagonal left, diagonal right

def __init__(self, lines: set[Line], floor=False) -> None:
self.rock: set[Point] = self._get_rock(lines)
self.sand = set()
self.min_x = min(point.x for point in self.rock)
self.max_x = max(point.x for point in self.rock)
self.min_y = min(point.y for point in self.rock)
self.max_y = max(point.y for point in self.rock)
self._set_floor(floor)

def _set_floor(self, floor: bool):
self._floor = floor
self._floor_y = self.max_y + 2
self.max_y = self._floor_y

def _get_rock(self, lines: set[Line]):
""" Process lines of rock. For each point in those lines, add a rock point to the set. """
rock = set()
for line in lines:
x_start = min(line.start.x, line.end.x)
x_end = max(line.start.x, line.end.x)
y_start = min(line.start.y, line.end.y)
y_end = max(line.start.y, line.end.y)
rock.update({Point(x,y) for x in range(x_start, x_end+1)
for y in range(y_start, y_end+1)})

return rock

def _is_empty(self, point: Point) -> bool:
""" If this point is not rock or sand, return True. """
if point not in self.rock and point not in self.sand:
if self._floor:
if point.y == self._floor_y:
return False
return True

return False

def drop_sand(self) -> Point:
""" Sand falls down until it reaches an obstacle.
If it reaches an obstacle, it will they try to fall diagonally left, then diagonally right. """
grain = Grid.SAND_ORIGIN
falling = True
while falling:
for v in Grid.SAND_VECTORS:
candidate = Point(grain.x + v.x, grain.y + v.y)
if self._is_empty(candidate):
if not self._floor and candidate.y == self._floor_y: # we've reached fall-through
return None
else: # there is a floor; expand the grid
self.min_x = min(self.min_x, grain.x - 1)
self.max_x = max(self.max_x, grain.x + 1)
self.min_y = min(self.min_y, grain.y)

grain = candidate
self.min_y = min(self.min_y, grain.y)

break  # move out of the vectors loop
else: # Get here if all our fall positions are full
falling = False

if grain == Grid.SAND_ORIGIN:
return None

return grain

def __str__(self) -> str:
rows = []
for y in range(self.min_y, self.max_y+1):
row = f"{y:3d} "

# print 1 col to either side
for x in range(self.min_x-1, self.max_x+2):
point = Point(x,y)
if point in self.rock:
row += "#"
continue
if self._floor and y == self._floor_y:
row += "#"
continue
if point in self.sand:
row += "o"
continue
row += "."

rows.append(row)

return "\n".join(rows)

def main():
with open(INPUT_FILE, mode="rt") as f:

lines = process_lines(data)

# Part 1
grid = Grid(lines)

# print(f"\n{grid}")

print(f"Part 1: resting grains={len(grid.sand)}")

# Part 2
grid = Grid(lines, floor=True)
# print(f"\n{grid}")

print(f"Part 2: resting grains={len(grid.sand)}")

def process_lines(data):
lines = set()
for input_line in data:
point_coords = input_line.split(" -> ")
points = [Point(*map(int, coord.split(","))) for coord in point_coords]
for i in range(1, len(points)):

return lines

if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
``````

## Results

The final output looks like this:

``````Part 1: resting grains=888
Part 2: resting grains=26461
Execution time: 6.2650 seconds
``````

It’s a bit slow. I’m sure there are optimisations I could make. But I’m knackered, so I’m not going to!