Skip to content

Instantly share code, notes, and snippets.

@JamesTheBard
Created November 29, 2023 15:33
Show Gist options
  • Save JamesTheBard/f2e573571c1dc89b4f0628d4ebbb665f to your computer and use it in GitHub Desktop.
Save JamesTheBard/f2e573571c1dc89b4f0628d4ebbb665f to your computer and use it in GitHub Desktop.
Day 17 of the Advent of Code 2022
from pathlib import Path
from typing import Union
from itertools import cycle
from dataclasses import dataclass
rocks = [
[0b00000, 0b00000, 0b00000, 0b11110],
[0b00000, 0b01000, 0b11100, 0b01000],
[0b00000, 0b00100, 0b00100, 0b11100],
[0b10000, 0b10000, 0b10000, 0b10000],
[0b00000, 0b00000, 0b11000, 0b11000],
]
rocks = [[j << 2 for j in i][::-1] for i in rocks]
def ffs(x):
return (x & -x).bit_length() - 1
@dataclass(frozen=True)
class PlayfieldState:
playfield_state: tuple[int]
block_type: int
move_number: int
def __eq__(self, __value: object) -> bool:
if self.playfield_state == __value.playfield_state and self.block_type == __value.block_type and self.move_number == __value.move_number:
return True
return False
class Playfield:
field: list
def __init__(self, filename: Union[str, Path]):
self.field = list()
self.vertical_start = 3
self.moves = Path(filename).open('r').readline().strip()
@property
def height(self):
for idx in range(len(self.field) - 1, -1, -1):
if self.field[idx]:
return idx + 1
return 0
def check(self, x_pos: int, y_pos: int, shape: int) -> bool:
if y_pos < 0 or x_pos > 6:
return False
if len(self.field) < y_pos + 4:
self.field = self.field + ([0] * 10)
x_offset = 6 - x_pos
for idx, row in enumerate(rocks[shape]):
if ffs(row) < x_offset and row:
return False
if row >> x_offset & self.field[y_pos + idx]:
return False
return True
def place(self, x_pos: int, y_pos: int, shape: int) -> bool:
if not self.check(x_pos, y_pos, shape):
return False
x_offset = 6 - x_pos
for idx, row in enumerate(rocks[shape]):
r = row >> x_offset
self.field[y_pos + idx] ^= r
return True
def move(self, x_pos: int, move: str) -> int:
if move == '>':
return x_pos - 1
else:
return x_pos + 1
def solve(self, blocks: int) -> int:
self.field = list()
self.state: dict[PlayfieldState: tuple[int, int]] = dict()
moves = cycle(enumerate(self.moves))
block_count = 0
height_offset = 0
found_loop = False
while block_count < blocks:
y, x = self.height + 3, 4
block = block_count % len(rocks)
while True:
move_count, move = next(moves)
# print(block_count, move_count, move, self.height)
x_new = self.move(x, move)
if self.check(x_new, y, block):
x = x_new
if self.check(x, y - 1, block):
y -= 1
else:
self.place(x, y, block)
state = PlayfieldState(
playfield_state=tuple(
self.field[self.height - 15:self.height]),
move_number=move_count,
block_type=block,
)
if state in self.state and not found_loop:
found_loop = True
loop_length = block_count - self.state[state][1]
loop_height = self.height - self.state[state][0]
loop_quantity = (blocks - block_count) // loop_length
if loop_quantity <= 0:
break
block_count += loop_length * loop_quantity
height_offset += loop_height * loop_quantity
elif not found_loop:
self.state[state] = (self.height, block_count)
break
block_count += 1
return self.height + height_offset
if __name__ == "__main__":
p = Playfield(filename="input.txt")
print(p.solve(2022))
print(p.solve(1000000000000))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment