# Learning Python with Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

# Advent of Code 2022 - Day 17

## Problem Intro

I enjoyed this one. The previous two days were really tough for me, so it was nice to have a problem that my simple brain could see a way through.

We get to code some Tetris today!!

We’re told rocks are falling from the ceiling of a tall chamber of fixed width. The rocks resemble Tetris pieces! There are five different rock shapes. With each rock that falls, the rock shape changes. The rock shapes follow a set sequence, and this sequence repeats indefinitely. Rocks always fall from a position that is 2 units from the left wall, and 3 units above highest rock that has fallen previously. (Or the floor.)

As rocks fall, they are blown left or right by jets of air from the sides. The input data describes the sequence of the air jets, e.g.

``````>>><<><>><<<>><>>><<<>>><<<><<<>><>><<>>
``````

We’re told this jet pattern repeats indefinitely. As rocks fall, they are pushed 1 unit left or right, then they descend 1 unit. A rock comes to rest in the step after it has reached a position where it cannot descend any further. Another rocks starts to fall whenever the previous rock comes to rest.

## Part 1

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

My strategy here is pretty simple:

• Each shape that is dropped will occupy a specific set of points.
• When the shape is blown left or right, we adjust the `x` values of these points, accordingly.
• When the shape falls, the `y` values of its points are increased by `1`.
• If the shape would move to a location where any of its points intersect with the walls of the cavern, the floor, or any settled shape, then this move is invalid.
• If the shape can’t fall further, then it must settle in the current position.

First, I create a `ShapeType` enum data type, that allows us to reference the various shape types by name:

``````class ShapeType(Enum):
HLINE =       {(0, 0), (1, 0), (2, 0), (3, 0)}
PLUS =        {(1, 0), (0, 1), (1, 1), (2, 1), (1, 2)}
BACKWARDS_L = {(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)}
I =           {(0, 0), (0, 1), (0, 2), (0, 3)}
SQUARE =      {(0, 0), (1, 0), (0, 1), (1, 1)}
``````

Then, a `dict` to represent the possible movements of a `Shape`, i.e. left, right, or down:

``````MOVE = {
"<": (-1, 0),
">": (1, 0),
"V": (0, -1)
}
``````

Next, I create a `Point` class, which knows how to add a vector to return a new `Point`. We’ll be using this whenever we need to determine the new location of a point, after blowing it left or right, or after letting it fall.

``````@dataclass(frozen=True)
class Point():
""" Point with x,y coordinates and knows how to add a vector to create a new Point. """
x: int
y: int

def __add__(self, other):
""" Add other point/vector to this point, returning new point """
return Point(self.x + other.x, self.y + other.y)

def __repr__(self) -> str:
return f"P({self.x},{self.y})"
``````

Now I create a class that represents the current positions occupied by an instance of any given `Shape`:

``````class Shape():
""" Stores the points that make up this shape.
Has a factory method to create Shape instances based on shape type. """

def __init__(self, points: set[Point], at_rest=False) -> None:
self.points: set[Point] = points   # the points that make up the shape
self.at_rest = at_rest

@classmethod
def create_shape_by_type(cls, shape_type: str, origin: Point):
""" Factory method to create an instance of our shape.
The shape points are offset by the supplied origin. """
return cls({(Point(*coords) + origin) for coords in ShapeType[shape_type].value})

@classmethod
def create_shape_from_points(cls, points: set[Point], at_rest=False):
""" Factory method to create an instance of our shape.
The shape points are offset by the supplied origin. """
return cls(points, at_rest)

def __eq__(self, __o: object) -> bool:
if isinstance(__o, Shape):
if self.points == __o.points:
return True
else:
return False
else:
return NotImplemented

def __hash__(self) -> int:
return hash(repr(self))

def __repr__(self) -> str:
return f"Shape(at_rest={self.at_rest}, points={self.points}"
``````

Some notes about this `Shape` class:

• It stores a `set` of all the Points it occupies.
• It has factory methods to create each shape, either by `ShapeType`, or by supplying a number of points. We use the latter to create a new shape whenever we move an existing shape.
• Shapes are created with all their points added to a specified `_origin_` point.
• The `Shape` is hashable, meaning a given instance of a `Shape` with a given set of unique attributes should return a unique but consistent hash. We need this if we want to store `Shape` objects in a `set` and then perform any `set` algebra on our sets.

All the fun stuff happens in the `Tower` class:

``````class Tower():
WIDTH = 7
LEFT_WALL_X = 0
RIGHT_WALL_X = LEFT_WALL_X + 7 + 1  # right wall at x=8
OFFSET_X = 2 + 1  # objects start with left edge at x=3
OFFSET_Y = 3 + 1  # new rocks have a gap of 3 above top of highest settled rock
FLOOR_Y = 0

# Printing characters
FALLING = "@"
AT_REST = "#"
EMPTY = "."
WALL = "|"
FLOOR = "-"

def __init__(self, jet_pattern: str) -> None:
self._jet_pattern = itertools.cycle(enumerate(jet_pattern)) # infinite cycle
self._shape_generator = itertools.cycle(enumerate(item.name for item in ShapeType))  # infinite cycle
self.top = Tower.FLOOR_Y  # keep track of top of blocks
self._all_at_rest_shapes: set[Shape] = set()
self._all_at_rest_points: set[Point] = set() # tracking this for speed

def _current_origin(self) -> Point:
""" Rocks are dropped 2 from the left edge, and 3 above the current tallest settled rock. """
return Point(Tower.LEFT_WALL_X + Tower.OFFSET_X, self.top + Tower.OFFSET_Y)

def _next_shape(self):
""" Get the next shape from the generator """
return next(self._shape_generator)

def _next_jet(self):
""" Get the next jet blast from the generator """
return next(self._jet_pattern)

def drop_shape(self):
shape_index, next_shape_type = self._next_shape()
self.current_shape = Shape.create_shape_by_type(next_shape_type, self._current_origin())

while True:
jet_index, jet = self._next_jet()
self._move_shape(jet)
# print(self)
if not self._move_shape("V"): # failed to move down
self.top = max(self.top, max(point.y for point in self.current_shape.points))
settled_shape = Shape.create_shape_from_points(self.current_shape.points, True)
self._settle_shape(settled_shape)
break

def _settle_shape(self, shape: Shape):
""" Add this shape to the settled sets """
self._all_at_rest_shapes.add(shape)
self._all_at_rest_points.update(shape.points)

def _move_shape(self, direction) -> bool:
""" Move a shape in the direction indicated. Return False if we can't move. """

# Test against boundaries
if direction == "<":
shape_left_x = min(point.x for point in self.current_shape.points)
if shape_left_x == Tower.LEFT_WALL_X + 1:
return False # can't move left

if direction == ">":
shape_right_x = max(point.x for point in self.current_shape.points)
if shape_right_x == Tower.RIGHT_WALL_X - 1:
return False # can't move right

if direction == "V":
shape_bottom = min(point.y for point in self.current_shape.points)
if shape_bottom == Tower.FLOOR_Y + 1:
return False # can't move down

# Move phase - test for collision
candidate_points = {(point + Point(*MOVE[direction])) for point in self.current_shape.points}
if self._all_at_rest_points & candidate_points: # If the candidate would intersect
return False # Then this is not a valid posiiton
else: # We can move there. Update our current shape position, by constructing a new shape a the new position
self.current_shape = Shape.create_shape_from_points(candidate_points)
return True

def __str__(self) -> str:
rows = []
top_for_vis = max(self.top, max(point.y for point in self.current_shape.points))

for y in range(Tower.FLOOR_Y, top_for_vis + 1):
line = f"{y:3d} "
if y == Tower.FLOOR_Y:
line += "+" + (Tower.FLOOR * Tower.WIDTH) + "+"
else:
for x in range(Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X + 1):
if x in (Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X):
line += Tower.WALL
elif Point(x,y) in self._all_at_rest_points:
line += Tower.AT_REST
elif Point(x,y) in self.current_shape.points:
line += Tower.FALLING
else:
line += Tower.EMPTY

rows.append(line)

return f"{repr(self)}:\n" + "\n".join(rows[::-1])

def __repr__(self) -> str:
return (f"Tower(height={self.top}, rested={len(self._all_at_rest_shapes)})")
``````

Things to say about this:

• It uses `itertools.cycle()` to infinitely iterate through the input jet pattern. We can always generate the next jet.
• It uses `itertools.cycle()` to infinitely iterate through the ShapeTypes in order. We can always generate the next shape.
• It stores all points for all at rest shapes as a `set`.
• It stores the current top (`y` coordinate) of all the settled points. This is used when we calculate the `y` value for the next shape dropped.
• It sets the origin for the next shape dropped.
• It simulates dropping a shape with a `drop_shape()` method:
• Creates the new shape at the appropriate origin `Point`, using the `Shape` constructor that takes a `ShapeType`.
• Calls `_move_shape()` with next jet.
• Calls `_move_shape("V")` to move the shape down. If we can’t move down, settles the shape by adding current shape to `_all_at_rest_shapes`.
• To move a shape:
• Check if we can move left, right or down based on the current bounds; return if we can’t.
• If the bounds are okay, generate candidate points from moving the current shape, i.e. by creating a set of points one point to the left, one point to the right, or one point below, as required.
• Check if any of these candidate points intersect with any settled points. If so, we can’t move there.
• Otherwise, make a new shape from the candidate points, and make this our `current_shape`.

I have also created a `__str__()` method to print the current `Tower`. This is really useful for debugging.

### Printing

Let’s do a quick test. We’ll uncomment the `print()` statement in our `drop_shape()` method, and then perform just three shape drops, using the sample data:

``````def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()

# Part 1
tower = Tower(jet_pattern=data)
for _ in range(3):
tower.drop_shape()

print(f"Part 1: {repr(tower)}")
``````

Here’s the output:

``````Tower(height=0, rested=0):
4 |...@@@@|
3 |.......|
2 |.......|
1 |.......|
0 +-------+
Tower(height=0, rested=0):
3 |...@@@@|
2 |.......|
1 |.......|
0 +-------+
Tower(height=0, rested=0):
2 |...@@@@|
1 |.......|
0 +-------+
Tower(height=0, rested=0):
1 |..@@@@.|
0 +-------+
Tower(height=1, rested=1):
7 |..@....|
6 |.@@@...|
5 |..@....|
4 |.......|
3 |.......|
2 |.......|
1 |..####.|
0 +-------+
Tower(height=1, rested=1):
6 |...@...|
5 |..@@@..|
4 |...@...|
3 |.......|
2 |.......|
1 |..####.|
0 +-------+
Tower(height=1, rested=1):
5 |..@....|
4 |.@@@...|
3 |..@....|
2 |.......|
1 |..####.|
0 +-------+
Tower(height=1, rested=1):
4 |...@...|
3 |..@@@..|
2 |...@...|
1 |..####.|
0 +-------+
Tower(height=4, rested=2):
10 |.....@.|
9 |.....@.|
8 |...@@@.|
7 |.......|
6 |.......|
5 |.......|
4 |...#...|
3 |..###..|
2 |...#...|
1 |..####.|
0 +-------+
Tower(height=4, rested=2):
9 |....@..|
8 |....@..|
7 |..@@@..|
6 |.......|
5 |.......|
4 |...#...|
3 |..###..|
2 |...#...|
1 |..####.|
0 +-------+
Tower(height=4, rested=2):
8 |...@...|
7 |...@...|
6 |.@@@...|
5 |.......|
4 |...#...|
3 |..###..|
2 |...#...|
1 |..####.|
0 +-------+
Tower(height=4, rested=2):
7 |..@....|
6 |..@....|
5 |@@@....|
4 |...#...|
3 |..###..|
2 |...#...|
1 |..####.|
0 +-------+
Tower(height=4, rested=2):
6 |..@....|
5 |..@....|
4 |@@@#...|
3 |..###..|
2 |...#...|
1 |..####.|
0 +-------+
Part 1: Tower(height=6, rested=3)
Execution time: 0.0146 seconds
``````

### Simple Vis

At this point, I thought it would be cool to add a simple visualisation. Rather than using any libraries like Matplotlib, this time I’ve simply used ANSI escape sequences to add some colour to my console output.

First, an enum for the ANSI colour codes:

``````class Colours(Enum):
""" ANSI escape sequences for coloured console output """
RED = "\033[31m"
GREEN = "\033[32m"
YELLOW = "\033[33m"
BLUE = "\033[34m"
MAGENTA = "\033[35m"
CYAN = "\033[36m"
BOLD = "\033[1m"
RESET = "\033[0m"
``````

Then a couple of functions for printing to the console for a set amount of time, and then clearing the console:

``````def print_and_clear(msg: str, delay=0.05):
print(msg)
time.sleep(delay)
cls()

def cls():
""" Clear console """
os.system('cls' if os.name=='nt' else 'clear')
``````

And finally, some changes to the `Tower` class so that our `__str__()` uses the ANSI codes:

``````    class PrintingChars(Enum):
FALLING = Colours.BOLD.value + Colours.BLUE.value + "@" + Colours.RESET.value
AT_REST = Colours.YELLOW.value+ "#" + Colours.RESET.value
EMPTY = Colours.GREEN.value + "." + Colours.RESET.value
CORNER = Colours.GREEN.value + "+" + Colours.RESET.value
WALL = Colours.GREEN.value + "|" + Colours.RESET.value
FLOOR = Colours.GREEN.value + "-" + Colours.RESET.value

def __str__(self) -> str:
rows = []
# top_for_vis = max(self.top, max(point.y for point in self.current_shape.points))
top_for_vis = self.top + Tower.OFFSET_Y

for y in range(Tower.FLOOR_Y, top_for_vis + 1):
line = f"{y:3d} "
if y == Tower.FLOOR_Y:
line += (Tower.PrintingChars.CORNER.value
+ (Tower.PrintingChars.FLOOR.value * Tower.WIDTH)
+ Tower.PrintingChars.CORNER.value)
else:
for x in range(Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X + 1):
if x in (Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X):
line += Tower.PrintingChars.WALL.value
elif Point(x,y) in self._all_at_rest_points:
line += Tower.PrintingChars.AT_REST.value
elif Point(x,y) in self.current_shape.points:
line += Tower.PrintingChars.FALLING.value
else:
line += Tower.PrintingChars.EMPTY.value

rows.append(line)

return f"{repr(self)}:\n" + "\n".join(rows[::-1])
``````

Now, instead of calling `print(self)` in our `drop_shape()` method, we use `print_and_clear(str(self))`.

The output looks like this:

### Solution

To solve Part 1, we just need to run our `drop()` method 2022 times:

``````def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read()

# Part 1
tower = Tower(jet_pattern=data)
for _ in range(2022):
tower.drop_shape()

print(f"Part 1: {repr(tower)}")
``````

## Part 2

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

My Part 1 solution runs at a rate of about 1 million drops per minute. At this rate, it would take us about 2 years for the program to complete for Part 2! Performing this many drops is not viable. We need a smarter way to calculate the height after 1000000000000 drops.

My strategy is to look for the first time we see a repeat of a state we’ve seen before, where a state is made up of:

• The current rock being dropped. (Given by the current index of the ShapeType being dropped.)
• The current jet index.
• The most recent rock formation. For my solution, I’ve arbitrarily chosen to take a `str` representation of the last 20 settled rows to represent the rock formation.

My theory is that if these three things are true, than we’ve discovered a pattern that will repeat every n shapes.

First, let’s add a method to cache these states, and change our `drop_shape()` method so that it checks the cache with each drop:

``````    def _check_cache(self, shape_index: int, jet_index: int, formation: str) -> tuple:
key = (shape_index, jet_index, formation)
shape_ct = len(self._all_at_rest_shapes)
if key in self._cache: # We've found a repeat!
# print(key)
last_height, last_shape_count = self._cache[key]
return (True, self.top, last_height, shape_ct, last_shape_count)
else: # cache miss, so add new entry to the cache
self._cache[key] = (self.top, shape_ct)

return (False, self.top, 0, shape_ct, 0)

def get_recent_formation(self) -> str:
""" Covert last (top) 20 rows into a str representation. """
rows = []
min_y = max(0, self.top-20) # we want the last 20 lines
for y in range(min_y, self.top+1):
line = ""
for x in range(Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X):
if Point(x,y) in self._all_at_rest_points:
line += Tower.PrintingChars.AT_REST.value
elif Point(x,y) in self.current_shape.points:
line += Tower.PrintingChars.FALLING.value
else:
line += Tower.PrintingChars.EMPTY.value

rows.append(line)

return "\n".join(rows[::-1])

def drop_shape(self):
shape_index, next_shape_type = self._next_shape()
self.current_shape = Shape.create_shape_by_type(next_shape_type, self._current_origin())

while True:
jet_index, jet = self._next_jet()
self._move_shape(jet)
if VIS_ENABLED:
print_and_clear(str(self))

if not self._move_shape("V"): # failed to move down
self.top = max(self.top, max(point.y for point in self.current_shape.points))
settled_shape = Shape.create_shape_from_points(self.current_shape.points, True)
self._settle_shape(settled_shape)
if not self.repeat_identified:
cache_response = self._check_cache(shape_index, jet_index, self.get_recent_formation())
if cache_response[0]: # Cache hit
# print(cache_response)
self.repeat_identified = True
self._repeat = (cache_response[1] - cache_response[2], # current top - last top
cache_response[3] - cache_response[4]) # current shape ct - last shape ct

break
``````

The `check_cache()` method takes the current state (shape being dropped, jet index, rock formation, and looks to see if we’ve seen this state before. If not (a cache miss), then we add this state to the cache as a key, and set the value to be the current top and the current shape count. We then return a `False` tuple.

If we have seen this state before (a cache hit), then we’ve identified a repeat of a previous state. In this scenario, we return a `True` tuple that also contains the top and shape count from when we saw this state last. Back in `drop_shape()`, we determine the delta between current top and last top, and the delta between current shape count and last shape count. We store these two deltas as `self._repeat`.

So now we know how many extra rows are added to the height of the tower, for a specific number of shapes, whenever the cycle repeats.

Now I’ve created a `calculate_height()` method in the `Tower` class, which:

• Determines how many drops are still required to reach our total drops goal.
• Determines how many repeat cycles we need, by dividing the required number of drops by the shape count delta.
• Determines if there is a shape drop remainder, so that we can manually drop the remaining shapes.
• Determines the height increase of the tower, based on this number of repeats. Add this increase to the current tower height.
• Finally, return the calculated height, as well as any shape drop remainder.

Here is the code:

``````    def calculate_height(self, shape_drops: int) -> tuple[int, int]:
""" Calculate the additional height given n shape drops.
We know that x shapes (shape repeat) create a height delta (height repeat) of y.
x - current_shape_ct -> required_drops
required_drops // shape_repeat -> whole repeats required
required_drops % shape_repeat -> remaining drops required
required_drops * height_repeat -> height delta

Returns tuple: new_height (int), remaining drops (int)
"""
remaining_drops = shape_drops - len(self._all_at_rest_shapes)
repeats_req = remaining_drops // self._repeat[1]    # full repeats
remaining_drops %= self._repeat[1]      # remaining individual drops

height_delta = self._repeat[0] * repeats_req  # height created by these repeats
new_height = self.top + height_delta

return new_height, remaining_drops
``````

Finally, back in the `main()` function:

• Drop shapes until we find our first repeat. Store the initial height at this point.
• Call `calculate_height()` to determine the calculated height after `n` drops.
• Manually drop shapes for any remainder required. Get the new height.
• The final height is given by: the calculated height + new height - initial height.

Here’s the new code I’ve added to `main()`:

``````    # Part 2
tower = Tower(jet_pattern=data)  # Recreate the initial tower
while not tower.repeat_identified:  # Drop until we identify the first repeat
tower.drop_shape()
height_at_repeat_start = tower.top  # The height achieved before first repeat
print(f"\nPart 2: Repeat found at: {repr(tower)}")

# Here we calculate the new height.  But we're NOT modifying the actual tower height.
new_height, remaining_drops = tower.calculate_height(1000000000000)
print(f"Part 2: Calculated new height from repeats: {new_height}")

# If drops was not an exact multiple of drop repeat,
# then we'll need to top up with the remaining drops.
# However, we're continuing the drops with our tower at the point where the repeat was identified.
for _ in range(remaining_drops):
tower.drop_shape()
height_after_top_up = tower.top  # But this number does NOT include the calculated height delta.
# So get the diff between the height now, and the height when we stopped dropping.
final_height = new_height + height_after_top_up - height_at_repeat_start

print(f"Part 2: Final height after top-up: {final_height}")
``````

## Results

The overall solution looks like this:

``````from dataclasses import dataclass
from enum import Enum
import itertools
import os
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")

VIS_ENABLED = False

class ShapeType(Enum):
""" Enum for our five shapes """
HLINE =       {(0, 0), (1, 0), (2, 0), (3, 0)}
PLUS =        {(1, 0), (0, 1), (1, 1), (2, 1), (1, 2)}
BACKWARDS_L = {(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)}
I =           {(0, 0), (0, 1), (0, 2), (0, 3)}
SQUARE =      {(0, 0), (1, 0), (0, 1), (1, 1)}

MOVE = {
"<": (-1, 0),
">": (1, 0),
"V": (0, -1)
}

@dataclass(frozen=True)
class Point():
""" Point with x,y coordinates and knows how to add a vector to create a new Point. """
x: int
y: int

def __add__(self, other):
""" Add other point/vector to this point, returning new point """
return Point(self.x + other.x, self.y + other.y)

def __repr__(self) -> str:
return f"P({self.x},{self.y})"

class Shape():
""" Stores the points that make up this shape.
Has a factory method to create Shape instances based on shape type. """

def __init__(self, points: set[Point], at_rest=False) -> None:
self.points: set[Point] = points   # the points that make up the shape
self.at_rest = at_rest

@classmethod
def create_shape_by_type(cls, shape_type: str, origin: Point):
""" Factory method to create an instance of our shape.
The shape points are offset by the supplied origin. """
return cls({(Point(*coords) + origin) for coords in ShapeType[shape_type].value})

@classmethod
def create_shape_from_points(cls, points: set[Point], at_rest=False):
""" Factory method to create an instance of our shape.
The shape points are offset by the supplied origin. """
return cls(points, at_rest)

def __eq__(self, __o: object) -> bool:
if isinstance(__o, Shape):
if self.points == __o.points:
return True
else:
return False
else:
return NotImplemented

def __hash__(self) -> int:
return hash(repr(self))

def __repr__(self) -> str:
return f"Shape(at_rest={self.at_rest}, points={self.points}"

class Colours(Enum):
""" ANSI escape sequences for coloured console output """
RED = "\033[31m"
GREEN = "\033[32m"
YELLOW = "\033[33m"
BLUE = "\033[34m"
MAGENTA = "\033[35m"
CYAN = "\033[36m"
BOLD = "\033[1m"
RESET = "\033[0m"

class Tower():
""" Fixed width tower that generates new shapes to drop, and blows shapes left and right as they drop. """
WIDTH = 7
LEFT_WALL_X = 0
RIGHT_WALL_X = LEFT_WALL_X + 7 + 1  # right wall at x=8
OFFSET_X = 2 + 1  # objects start with left edge at x=3
OFFSET_Y = 3 + 1  # new rocks have a gap of 3 above top of highest settled rock
FLOOR_Y = 0

class PrintingChars(Enum):
FALLING = Colours.BOLD.value + Colours.BLUE.value + "@" + Colours.RESET.value
AT_REST = Colours.YELLOW.value+ "#" + Colours.RESET.value
EMPTY = Colours.GREEN.value + "." + Colours.RESET.value
CORNER = Colours.GREEN.value + "+" + Colours.RESET.value
WALL = Colours.GREEN.value + "|" + Colours.RESET.value
FLOOR = Colours.GREEN.value + "-" + Colours.RESET.value

def __init__(self, jet_pattern: str) -> None:
self._jet_pattern = itertools.cycle(enumerate(jet_pattern)) # infinite cycle
self._shape_generator = itertools.cycle(enumerate(item.name for item in ShapeType))  # infinite cycle
self.top = Tower.FLOOR_Y  # keep track of top of blocks
self._all_at_rest_shapes: set[Shape] = set()
self._all_at_rest_points: set[Point] = set() # tracking this for speed

self.repeat_identified = False
self._cache: dict[tuple, tuple] = {}    # K=(rock_idx, jet_idx, rock_formation): V=(height, shape_ct)
self._repeat: tuple = (0, 0)  # height_diff, shape_diff

def _current_origin(self) -> Point:
""" Rocks are dropped 2 from the left edge, and 3 above the current tallest settled rock. """
return Point(Tower.LEFT_WALL_X + Tower.OFFSET_X, self.top + Tower.OFFSET_Y)

def _next_shape(self):
""" Get the next shape from the generator """
return next(self._shape_generator)

def _next_jet(self):
""" Get the next jet blast from the generator """
return next(self._jet_pattern)

def _check_cache(self, shape_index: int, jet_index: int, formation: str) -> tuple:
key = (shape_index, jet_index, formation)
shape_ct = len(self._all_at_rest_shapes)
if key in self._cache: # We've found a repeat!
# print(key)
last_height, last_shape_count = self._cache[key]
return (True, self.top, last_height, shape_ct, last_shape_count)
else: # cache miss, so add new entry to the cache
self._cache[key] = (self.top, shape_ct)

return (False, self.top, 0, shape_ct, 0)

def drop_shape(self):
shape_index, next_shape_type = self._next_shape()
self.current_shape = Shape.create_shape_by_type(next_shape_type, self._current_origin())

while True:
jet_index, jet = self._next_jet()
self._move_shape(jet)
if VIS_ENABLED:
print_and_clear(str(self))

if not self._move_shape("V"): # failed to move down
self.top = max(self.top, max(point.y for point in self.current_shape.points))
settled_shape = Shape.create_shape_from_points(self.current_shape.points, True)
self._settle_shape(settled_shape)
if not self.repeat_identified:
cache_response = self._check_cache(shape_index, jet_index, self.get_recent_formation())
if cache_response[0]: # Cache hit
# print(cache_response)
self.repeat_identified = True
self._repeat = (cache_response[1] - cache_response[2], # current top - last top
cache_response[3] - cache_response[4]) # current shape ct - last shape ct

break

def calculate_height(self, shape_drops: int) -> tuple[int, int]:
""" Calculate the additional height given n shape drops.
We know that x shapes (shape repeat) create a height delta (height repeat) of y.
x - current_shape_ct -> required_drops
required_drops // shape_repeat -> whole repeats required
required_drops % shape_repeat -> remaining drops required
required_drops * height_repeat -> height delta

Returns tuple: new_height (int), remaining drops (int)
"""
remaining_drops = shape_drops - len(self._all_at_rest_shapes)
repeats_req = remaining_drops // self._repeat[1]    # full repeats
remaining_drops %= self._repeat[1]      # remaining individual drops

height_delta = self._repeat[0] * repeats_req  # height created by these repeats
new_height = self.top + height_delta

return new_height, remaining_drops

def _settle_shape(self, shape: Shape):
""" Add this shape to the settled sets """
self._all_at_rest_shapes.add(shape)
self._all_at_rest_points.update(shape.points)

def _move_shape(self, direction) -> bool:
""" Move a shape in the direction indicated. Return False if we can't move. """

# Test against boundaries
if direction == "<":
shape_left_x = min(point.x for point in self.current_shape.points)
if shape_left_x == Tower.LEFT_WALL_X + 1:
return False # can't move left

if direction == ">":
shape_right_x = max(point.x for point in self.current_shape.points)
if shape_right_x == Tower.RIGHT_WALL_X - 1:
return False # can't move right

if direction == "V":
shape_bottom = min(point.y for point in self.current_shape.points)
if shape_bottom == Tower.FLOOR_Y + 1:
return False # can't move down

# Move phase - test for collision
candidate_points = {(point + Point(*MOVE[direction])) for point in self.current_shape.points}
if self._all_at_rest_points & candidate_points: # If the candidate would intersect
return False # Then this is not a valid posiiton
else: # We can move there. Update our current shape position, by constructing a new shape a the new position
self.current_shape = Shape.create_shape_from_points(candidate_points)
return True

def get_recent_formation(self) -> str:
""" Covert last (top) 20 rows into a str representation. """
rows = []
min_y = max(0, self.top-20) # we want the last 20 lines
for y in range(min_y, self.top+1):
line = ""
for x in range(Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X):
if Point(x,y) in self._all_at_rest_points:
line += Tower.PrintingChars.AT_REST.value
elif Point(x,y) in self.current_shape.points:
line += Tower.PrintingChars.FALLING.value
else:
line += Tower.PrintingChars.EMPTY.value

rows.append(line)

return "\n".join(rows[::-1])

def __str__(self) -> str:
rows = []
# top_for_vis = max(self.top, max(point.y for point in self.current_shape.points))
top_for_vis = self.top + Tower.OFFSET_Y

for y in range(Tower.FLOOR_Y, top_for_vis + 1):
line = f"{y:3d} "
if y == Tower.FLOOR_Y:
line += (Tower.PrintingChars.CORNER.value
+ (Tower.PrintingChars.FLOOR.value * Tower.WIDTH)
+ Tower.PrintingChars.CORNER.value)
else:
for x in range(Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X + 1):
if x in (Tower.LEFT_WALL_X, Tower.RIGHT_WALL_X):
line += Tower.PrintingChars.WALL.value
elif Point(x,y) in self._all_at_rest_points:
line += Tower.PrintingChars.AT_REST.value
elif Point(x,y) in self.current_shape.points:
line += Tower.PrintingChars.FALLING.value
else:
line += Tower.PrintingChars.EMPTY.value

rows.append(line)

return f"{repr(self)}:\n" + "\n".join(rows[::-1])

def __repr__(self) -> str:
return (f"Tower(height={self.top}, rested={len(self._all_at_rest_shapes)})")

def print_and_clear(msg: str, delay=0.05):
print(msg)
time.sleep(delay)
cls()

def cls():
""" Clear console """
os.system('cls' if os.name=='nt' else 'clear')

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

# Part 1
tower = Tower(jet_pattern=data)
for _ in range(2022):
tower.drop_shape()

print(f"Part 1: {repr(tower)}")

# Part 2
tower = Tower(jet_pattern=data)  # Recreate the initial tower
while not tower.repeat_identified:  # Drop until we identify the first repeat
tower.drop_shape()
height_at_repeat_start = tower.top  # The height achieved before first repeat
print(f"\nPart 2: Repeat found at: {repr(tower)}")

# Here we calculate the new height.  But we're NOT modifying the actual tower height.
new_height, remaining_drops = tower.calculate_height(1000000000000)
print(f"Part 2: Calculated new height from repeats: {new_height}")

# If drops was not an exact multiple of drop repeat,
# then we'll need to top up with the remaining drops.
# However, we're continuing the drops with our tower at the point where the repeat was identified.
for _ in range(remaining_drops):
tower.drop_shape()
height_after_top_up = tower.top  # But this number does NOT include the calculated height delta.
# So get the diff between the height now, and the height when we stopped dropping.
final_height = new_height + height_after_top_up - height_at_repeat_start

print(f"Part 2: Final height after top-up: {final_height}")

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

The output looks like this:

``````Part 1: Tower(height=3149, rested=2022)

Part 2: Repeat found at: Tower(height=3150, rested=2023)
Part 2: Calculated new height from repeats: 1553982300150
Part 2: Final height after top-up: 1553982300884
Execution time: 1.4179 seconds
``````