Advent of Code 2022 - Day 14

Useful Links

Concepts and Packages Demonstrated

Problem Intro
Part 1
Part 2
Results

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)):
            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:

.....#...##.
.....#...#..
...###...#..
.........#..
.........#..
.#########..

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)
    
    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:

............
.......o....
......ooo...
.....#ooo##.
....o#ooo#..
...###ooo#..
.....oooo#..
..o.ooooo#..
.#########..

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

        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")

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!

‹›

Learning Python with Advent of Code Walkthroughs