Dazbo's Advent of Code solutions, written in Python

classessetslist comprehensionmap

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.

**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.

- It takes all the rock lines as input, and expands them into a
- 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)):
lines.add(Line(points[i-1], points[i]))
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
self.sand.add(grain)
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`

.

- Drops a sand grain from the top, i.e. from
- 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)
adding_sand = True
while adding_sand:
adding_sand = grid.drop_sand()
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 .#########..
```

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`

.

- If we have a floor and sand has come to rest there, update

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
self.sand.add(grain)
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:
data = f.read().splitlines()
lines = process_lines(data)
# Part 1
grid = Grid(lines)
adding_sand = True
while adding_sand:
adding_sand = grid.drop_sand()
# print(f"\n{grid}")
print(f"Part 1: resting grains={len(grid.sand)}")
# Part 2
grid = Grid(lines, floor=True)
adding_sand = True
while adding_sand:
adding_sand = grid.drop_sand()
# 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)):
lines.add(Line(points[i-1], points[i]))
return lines
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
```

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!