Learning Python with Advent of Code Walkthroughs
Dazbo's Advent of Code solutions, written in Python
Advent of Code 2022 - Day 17
Useful Links
Concepts and Packages Demonstrated
Page Navigation
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
xvalues of these points, accordingly. - When the shape falls, the
yvalues of its points are increased by1. - 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
setof 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
Shapeis hashable, meaning a given instance of aShapewith a given set of unique attributes should return a unique but consistent hash. We need this if we want to storeShapeobjects in asetand then perform anysetalgebra 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 (
ycoordinate) of all the settled points. This is used when we calculate theyvalue 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 theShapeconstructor that takes aShapeType. - 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.
- Creates the new shape at the appropriate origin
- 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
strrepresentation 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 afterndrops. - 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