Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

Advent of Code - 2022

This is a solution to Day 17 of Advent of Code 2022.

Day 17: - Pyroclastic Flow

Your handheld device has located an alternative exit from the cave for you and the elephants. The ground is rumbling almost continuously now, but the strange valves bought you some time. It's definitely getting warmer in here, though.

The tunnels eventually open into a very tall, narrow chamber. Large, oddly-shaped rocks are falling into the chamber from above, presumably due to all the rumbling. If you can't work out where the rocks will fall next, you might be crushed!

The five types of rocks have the following peculiar shapes, where # is rock and . is empty space:

####

.#.
###
.#.

..#
..#
###

#
#
#
#

##
##

The rocks fall in the order shown above: first the - shape, then the + shape, and so on. Once the end of the list is reached, the same order repeats: the - shape falls first, sixth, 11th, 16th, etc.

The rocks don't spin, but they do get pushed around by jets of hot gas coming out of the walls themselves. A quick scan reveals the effect the jets of hot gas will have on the rocks as they fall (your puzzle input).

For example, suppose this was the jet pattern in your cave:

>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>

In jet patterns, < means a push to the left, while > means a push to the right. The pattern above means that the jets will push a falling rock right, then right, then right, then left, then left, then right, and so on. If the end of the list is reached, it repeats.

The tall, vertical chamber is exactly seven units wide. Each rock appears so that its left edge is two units away from the left wall and its bottom edge is three units above the highest rock in the room (or the floor, if there isn't one).

After a rock appears, it alternates between being pushed by a jet of hot gas one unit (in the direction indicated by the next symbol in the jet pattern) and then falling one unit down. If any movement would cause any part of the rock to move into the walls, floor, or a stopped rock, the movement instead does not occur. If a downward movement would have caused a falling rock to move into the floor or an already-fallen rock, the falling rock stops where it is (having landed on something) and a new rock immediately begins falling.

Drawing falling rocks with @ and stopped rocks with #, the jet pattern in the example above manifests as follows:

The first rock begins falling:
|..@@@@.|
|.......|
|.......|
|.......|
+-------+

Jet of gas pushes rock right:
|...@@@@|
|.......|
|.......|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
|.......|
|.......|
+-------+

Jet of gas pushes rock right, but nothing happens:
|...@@@@|
|.......|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
|.......|
+-------+

Jet of gas pushes rock right, but nothing happens:
|...@@@@|
|.......|
+-------+

Rock falls 1 unit:
|...@@@@|
+-------+

Jet of gas pushes rock left:
|..@@@@.|
+-------+

Rock falls 1 unit, causing it to come to rest:
|..####.|
+-------+

A new rock begins falling:
|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|.......|
|..####.|
+-------+

Jet of gas pushes rock left:
|..@....|
|.@@@...|
|..@....|
|.......|
|.......|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|..@....|
|.@@@...|
|..@....|
|.......|
|.......|
|..####.|
+-------+

Jet of gas pushes rock right:
|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|...@...|
|..@@@..|
|...@...|
|.......|
|..####.|
+-------+

Jet of gas pushes rock left:
|..@....|
|.@@@...|
|..@....|
|.......|
|..####.|
+-------+

Rock falls 1 unit:
|..@....|
|.@@@...|
|..@....|
|..####.|
+-------+

Jet of gas pushes rock right:
|...@...|
|..@@@..|
|...@...|
|..####.|
+-------+

Rock falls 1 unit, causing it to come to rest:
|...#...|
|..###..|
|...#...|
|..####.|
+-------+

A new rock begins falling:
|....@..|
|....@..|
|..@@@..|
|.......|
|.......|
|.......|
|...#...|
|..###..|
|...#...|
|..####.|
+-------+

The moment each of the next few rocks begins falling, you would see this:

|..@....|
|..@....|
|..@....|
|..@....|
|.......|
|.......|
|.......|
|..#....|
|..#....|
|####...|
|..###..|
|...#...|
|..####.|
+-------+

|..@@...|
|..@@...|
|.......|
|.......|
|.......|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@@@.|
|.......|
|.......|
|.......|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|...@...|
|..@@@..|
|...@...|
|.......|
|.......|
|.......|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|....@..|
|....@..|
|..@@@..|
|.......|
|.......|
|.......|
|..#....|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@....|
|..@....|
|..@....|
|..@....|
|.......|
|.......|
|.......|
|.....#.|
|.....#.|
|..####.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@...|
|..@@...|
|.......|
|.......|
|.......|
|....#..|
|....#..|
|....##.|
|....##.|
|..####.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

|..@@@@.|
|.......|
|.......|
|.......|
|....#..|
|....#..|
|....##.|
|##..##.|
|######.|
|.###...|
|..#....|
|.####..|
|....##.|
|....##.|
|....#..|
|..#.#..|
|..#.#..|
|#####..|
|..###..|
|...#...|
|..####.|
+-------+

To prove to the elephants your simulation is accurate, they want to know how tall the tower will get after 2022 rocks have stopped (but before the 2023rd rock begins falling). In this example, the tower of rocks will be 3068 units tall.

This seems fun! Most of the challenge in this one (at least for part 1) is in the modeling: what is the best structure and "flow" of the program. I started from a couple of different approaches, only to scrap one and move to another idea.

My first idea was to model the rock formation as its own class that knows its location but that didn't lead to a good structure as I felt there was too much duplicated information between cave and rock and too much back-and-forth of information passing.

Second idea was to model each part of a rock (a position in (x, y) coordinates) as its own class but that also run into similar issues.

So I stopped modeling from the objects outward and decided to create the main flow of code and design the objects inward. I recognized I wanted the main function to look like this:

cave = Cave()
for _ in range(2022):
    cave.tick()
return cave.height

Then I wrote on a paper what the tick should do:

  • Check if new rock should enter
  • Move the rock if able
  • Check if the rock has stopped

That translated into my Cave.tick function and from there on, I discovered what would be needed.

Modeling

from collections import defaultdict

class Cave:
    
    def __init__(self, jetstreams, rocks):
        self.map = {}
        
        self.rocks = rocks
        self.rock_index = 0

        self.jetstreams = jetstreams
        self.index = 0
        
        self.current_rock = None
        self.highest_point = 0
        self.lowest_point = 0
    
    def add_rock(self):
        assert self.current_rock is None
        
        next_rock = self.rocks[self.rock_index % len(self.rocks)]
        high_y = self.highest_point + 3
        
        self.current_rock = [(x, y + high_y) for x, y in next_rock]
        self.rock_index += 1               
        
    def is_next_down_free(self):
        for x,y in self.current_rock:
            if y - 1 < 0:
                return False
            if self.map.get((x, y-1), None) is not None:
                return False
        return True
    
    def is_next_left_free(self):
        for x,y in self.current_rock:
            if x - 1 < 0:
                return False
            if self.map.get((x-1, y), None) is not None:
                return False
        return True
    
    def is_next_right_free(self):
        for x,y in self.current_rock:
            if x + 1 > 6:
                return False
            if self.map.get((x+1, y), None) is not None:
                return False
        return True
        
    def move(self, direction):
        assert self.current_rock is not None
        
        xs = [pos[0] for pos in self.current_rock]
        low_point = min(pos[1] for pos in self.current_rock)
        left_point = min(xs)
        right_point = max(xs)
        
        match direction:
            case '<':
                if self.is_next_left_free():
                    new_pos = [
                        (x - 1, y) for x, y in self.current_rock
                    ]
                    self.current_rock = new_pos
            case '>':
                if self.is_next_right_free():
                    new_pos = [
                        (x + 1, y) for x, y in self.current_rock
                    ]
                    self.current_rock = new_pos
            case 'v':
                if self.is_next_down_free():
                    new_pos = [
                        (x, y - 1) for x, y in self.current_rock
                    ]
                    self.current_rock = new_pos
                else:
                    for x, y in self.current_rock:
                        if y + 1 > self.highest_point:
                            self.highest_point = y + 1
                        self.map[(x, y)] = '#'                                
                    self.current_rock = None
        
    def tick(self):
        if self.current_rock is None:
            self.add_rock()
        
        next_move = self.jetstreams[self.index % len(self.jetstreams)]
        self.index += 1
        self.move(next_move)

Read input

To read the data, I first turned the input line into a list, interlaced the directions with a down direction ('v'). Then I created the rock shapes with the correct x coordinates and the y coordinates in a way that bottom is 0 so I can then calculate the proper y coordinate when I add it to the cave.

from utils import read_input, flatten

data = read_input(17, list)[0]

jetstreams = []
for j in data:
    jetstreams.append(j)
    jetstreams.append('v')

rocks = [
    [(2,0), (3,0), (4,0), (5, 0)],
    [(3,0), (2,1), (3,1), (4,1), (3,2)],
    [(2,0), (3,0), (4,0), (4,1), (4,2)],
    [(2,0), (2,1), (2,2), (2,3)],
    [(2,0), (3,0), (2,1), (3,1)]
]
def solve(jetstreams, rocks, how_many_rocks):
    cave = Cave(jetstreams, rocks)
    while cave.rock_index <= how_many_rocks:
        cave.tick()
    return cave.highest_point

Part 1

How many units tall will the tower of rocks be after 2022 rocks have stopped falling?

height = solve(jetstreams, rocks, 2022)
print(f'Part 1: {height}')
assert height == 3179

Part 2

The elephants are not impressed by your simulation. They demand to know how tall the tower will be after 1000000000000 rocks have stopped! Only then will they feel confident enough to proceed through the cave.

In the example above, the tower would be 1514285714288 units tall!

How tall will the tower be after 1000000000000 rocks have stopped?

1000000000000 is such a massive number. That's one trillion rocks. Do you realize how incredible big number that is? It's even (slightly) more than the amount of projects that I've started but abandoned or the amount of domains I've bought and never built projects for because I had that brilliant idea.

With so many rocks, it means you need math. And I don't know the right math for this.

I probably won't solve this one but here are some thoughts that come to mind:

  • The only values we actually need to keep track of is the highest y value for each of the x values. So instead of my inefficient full cave map from part 1, we could just have 7 values (for x coordinates 0 through 6). That solves a lot of the memory issues.

  • Even looping empty loops for 1 trillion times takes forever so there needs to be some math that operates on way larger chunks than each rock. (The loop thing is true unless you work in language where the compiler optimizes an empty loop into a no op.)