1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
from utils import open_day, Point2D as P
from itertools import repeat, cycle
pieces = [
{ P(0, 0), P(1, 0), P(2, 0), P(3, 0) },
{ P(1, 0), P(0, 1), P(1, 1), P(2, 1), P(1, 2) },
{ P(0, 0), P(1, 0), P(2, 0), P(2, 1), P(2, 2) },
{ P(0, 0), P(0, 1), P(0, 2), P(0, 3) },
{ P(0, 0), P(1, 0), P(0, 1), P(1, 1) },
]
class Tower:
def __init__(self, width=7):
self.width = width
self.tower = []
@property
def height(self):
return len(self.tower) // self.width
def __str__(self):
rows = []
for y in range(self.height - 1, -1, -1):
rows.append('|' + ''.join(
'#' if self.tower[y * self.width + x] else '.'
for x in range(self.width)) + '|')
return '\n'.join(rows + ['+' + '-' * self.width + '+'])
def __setitem__(self, key, value):
if self.height <= key.y:
needed = self.width * (key.y - self.height + 1)
self.tower.extend(repeat(False, needed))
self.tower[key.y * self.width + key.x] = value
def __getitem__(self, key):
if key.x < 0 or key.x >= self.width or key.y < 0: raise IndexError
try: return self.tower[key.y * self.width + key.x]
except IndexError: return False
def get(self, key, default=None):
try: return self[key]
except IndexError: return default
def place_piece(tower, origin, piece):
for offset in piece:
tower[origin + offset] = True
def piece_fits(tower, origin, piece):
for offset in piece:
if tower.get(origin + offset, True): return False
return True
with open_day(17) as f:
conv = { '<': -1, '>': 1 }
gusts = [conv[c] for c in f.read().rstrip()]
def solve(gusts, cycles=2022):
tower = Tower()
it_gusts_i = cycle(range(len(gusts)))
gust_i = len(gusts) - 1
states = {}
heights = []
for piece_i, i in zip(cycle(range(len(pieces))), range(cycles)):
piece = pieces[piece_i]
pos = P(2, tower.height + 3)
for gust_i in it_gusts_i:
gust = gusts[gust_i]
nextpos = pos + P(gust, 0)
if piece_fits(tower, nextpos, piece):
pos = nextpos
nextpos = pos + P(0, -1)
if not piece_fits(tower, nextpos, piece):
break
pos = nextpos
place_piece(tower, pos, piece)
top_row = sum(1 << x if tower.get(P(x, tower.height-1), True) else 0 for x in range(tower.width))
state_key = (top_row, piece_i, gust_i)
if state_key in states: break
states[state_key] = i, tower.height
heights.append(tower.height)
else: return tower.height
base_i, base_height = states[state_key]
cycle_len = i - base_i
cycle_height = tower.height - base_height
height = (cycles - base_i) // cycle_len * cycle_height
height += heights[(cycles - 1) % cycle_len]
return height
print(solve(gusts))
print(solve(gusts, 1000000000000))
|
