# Pyroclastic Flow

`2022-12-27`

Original Prompt ## Part 1

Welcome to day 17! That music sure sounds familiar…

On the surface, these falling blocks should be easy enough to simulate. We can define an `(x, y)`

grid starting in the bottom left like so:

```
C = (0, 3) D = (6, 3)
|C.....D| |.......| |.......| |A.....B| +-------+
A = (0, 0) B = (6, 0)
```

We’ll want a `Block`

class that consists of a points that we have move left/right/down as needed:

```
from dataclasses import dataclassfrom typing import Literal
GridPoint = tuple[int, int]Points = set[GridPoint]
Direction = Literal["<", ">", "down"]OFFSETS: dict[Direction, tuple[int, int]] = {"<": (-1, 0), ">": (1, 0), "down": (0, -1)}
@dataclassclass Block: points: set[GridPoint]
def moved_points(self, direction: Literal["<", ">", "down"]) -> Points: o_x, o_y = OFFSETS[direction] return {(x + o_x, y + o_y) for x, y in self.points}
```

Next, we need an easy way to build a `Block`

in the proper shape. We can do that with custom subclasses that generate their points based on the shape of the block:

```
...
class Horiz(Block): def __init__(self, y: int): super().__init__({(x, y) for x in range(2, 6)})
class Plus(Block): def __init__(self, y: int): super().__init__({(3, y + 2), (2, y + 1), (3, y + 1), (4, y + 1), (3, y)})
class Angle(Block): def __init__(self, y: int): super().__init__({(2, y), (3, y), (4, y), (4, y + 1), (4, y + 2)})
class Vert(Block): def __init__(self, y: int): super().__init__({(2, y) for y in range(y, y + 4)})
class Square(Block): def __init__(self, y: int): super().__init__({(2, y), (3, y), (2, y + 1), (3, y + 1)})
```

Each block starts 2 off the left wall and its height is based on the current max height of the tower (which will get to in a sec).

Next, we our loop where we spawn blocks, blow them around, and move them down until they settle. We’ll want to loop through the wind directions *and* keep track of the next block. We can use `itertools.cycle`

, which is a generator that will loop over an iterable indefinitely. We also want to track that points that comprise settled blocks and our current max height:

```
from itertools import cycle...
class Solution(TextSolution): def part_1(self) -> int: wind = cycle(self.input) blocks = cycle([Horiz, Plus, Angle, Vert, Square]) settled: set[GridPoint] = set() max_y = -1
```

Now, we can drop exactly `2022`

blocks. We’ll be manually calling the `next`

function to get the next item from our two infinite generators. Here’s what that looks ike:

```
...
def is_in_range(p: GridPoint) -> bool: return 0 <= p[0] < 7 and p[1] >= 0
def all_in_range(points: Points) -> bool: return all(map(is_in_range, points))
class Solution(TextSolution): def part_1(self) -> int: for _ in range(2022): block = next(blocks)(max_y + 4) # "3 above" means + 4
while True: # L/R new_points = block.moved_points(cast(Direction, next(wind))) if new_points.isdisjoint(settled) and all_in_range(new_points): block.points = new_points
# down new_points = block.moved_points("down") if new_points.isdisjoint(settled) and all_in_range(new_points): block.points = new_points else: break
```

For each move, we check both that the new points are in the walls *and* don’t intersect any of the existing settled blocks; good thing we have a big `set`

of those! Note that we only break out of the loop in the second case, when there was a downward motion.

Lastly, we add our about-to-settle blocks to the set and re-calculate the height of the tower:

```
...
@dataclassclass Block: ...
@property def highest_point(self) -> int: return max(y for _, y in self.points)
class Solution(TextSolution): def part_1(self) -> int: for _ in range(2022): ...
# |= is the equivalent of +=, but uses `set_a | set_b` instead of `+` settled |= block.points max_y = max(max_y, block.highest_point)
# an extra 1, since we're storing the 0-indexed top point of the tower, # not the actual height return max_y + 1
```

## Part 2

Well, whenever you write `range(1_000_000_000_000)`

, you know you’re in for a bad time. Instead of actually running our loop again in full, we have to find when the tower repeats. At some point, the shape of the tower *must* repeat. If we find that point, we can save ourselves *many* loops.

To find the loop, we have to track the state of the tower each time we drop a new block. As we start a block, if we’ve been in this state before, we can see how many blocks are in each loop and do some math. A starting state is unique based on:

- the block shape
- our progress through the wind instructions
- the top row of the tower

If all 3 of those are the same as we’ve seen before, then the block we’re about to drop will fall the same and so will all the others after it (until we loop again). So, we need to track all those values:

```
...
class Solution(TextSolution): # our part 1 code, moved into a method def simulate_blocks(self, num_blocks: int) -> int: ... # wrap in `enumerate`, so we can track our process through the list wind = cycle(enumerate(self.input)) wind_index = 0
# renamed from `settled` settled_points: set[GridPoint] = set()
settled_lines: dict[int, str] = {-1: "1111111"} # floor max_y = -1 # below the floor
# block_name, wind_index, top_row_value => block_num, max_y start_states: dict[tuple[str, int, str], tuple[int, int]] = {}
def line_value(line: int) -> str: return "".join(str(int((x, line) in settled_points)) for x in range(7))
...
```

This includes a function to translate a `y`

value into a 7-digit string, representing the state of that row. With those initialized, we can store states as we drop blocks:

```
...
@dataclassclass Block: ...
@property def name(self): return self.__class__.__name__ # 'Horiz', 'Plus', etc
...
class Solution(TextSolution): def simulate_blocks(self, num_blocks: int) -> int: ...
for block_number in range(num_blocks): block = next(blocks)(max_y + 4) # "3 above" means + 4
state = (block.name, wind_index, settled_lines.get(max_y, "not found"))
start_states[state] = (block_number, max_y)
while True: # drop blocks; pt 1 ...
# update settled_points, max_y ...
settled_lines[max_y] = line_value(max_y)
```

As we go, we’re generating the `state`

before we drop the block and saving the current state of the top of the tower (# blocks, height). We also update state of the top of the tower (it may have changed based on the block we just dropped).

Next, we have to check our state against the previous states. If we’ve found a match, we can calculate the size of the loop:

```
...
class Solution(TextSolution): def simulate_blocks(self, num_blocks: int) -> int: ...
for block_number in range(num_blocks): ...
state = ...
if (previous_state := start_states.get(state)) and block.name == "Horiz": blocks_per_loop = block_number - previous_state[0] height_per_loop = max_y - previous_state[1]
print( f"Loop starting at block #{block_number}. Consists of {blocks_per_loop} blocks, which add {height_per_loop} height each. Current height is {max_y.}" )
...
```

Running this on the test input gives us `Loop starting at block #55. Consists of 35 blocks, which add 53 height each. Current height is 88`

. Now that we know the pattern, we can skip as many loops as we want. Knowing this, let’s work through part 1 of the example, since “1 trillion” is harder to reason about.

We know we need the height after `2022`

blocks. Starting with block number `55`

, we can skip `35`

blocks at a time and instead add `53`

to the height of the tower. If we divide the number of blocks remaining by the size of our loop, we know how many loops we can safely skip. In our case, that’s `(2022 - 55) // 35`

, or `56`

. So, instead of starting block `55`

, we can skip straight to block `55 + 56 * 35`

, which is `2015`

. We also have to (eventually) add `56 * 53`

(`2968`

) to our height.

Now that we’ve skipped ahead, we keep dropping blocks like normal until we get to the requested number. Those 7 remaining blocks (`2022 - 2015`

) add an additional `11`

height to the `88`

we had before the skip. All together, that’s `11 + 88 + 2968`

, plus the `1`

to convert from index to actual height, and we’ve got `3068`

, the example answer form part 1!

If that all makes sense, we can code it up!

```
...
class Solution(TextSolution): def simulate_blocks(self, num_blocks: int) -> int: ...
height_to_add = 0
...
# switch from `range` to a manual tracker, so we jump block_number = 0 while block_number < num_blocks: ...
state = ...
if ( (previous_state := start_states.get(state)) and block.name == "Horiz" and height_to_add == 0 ): blocks_per_loop = block_number - previous_state[0] loops_to_skip = (num_blocks - block_number) // blocks_per_loop block_number += loops_to_skip * blocks_per_loop
height_per_loop = max_y - previous_state[1] height_to_add = loops_to_skip * height_per_loop
elif height_to_add == 0: # only track these before we've found a loop start_states[state] = (block_number, max_y)
# drop blocks ...
# settle blocks, update tracking variables ...
return max_y + height_to_add + 1
def part_1(self) -> int: return self.simulate_blocks(2022)
def part_2(self) -> int: return self.simulate_blocks(1_000_000_000_000)
```

And that’ll do it! Definitely took some time to wrap our heads around, but it ultimately wasn’t too bad.