-
Notifications
You must be signed in to change notification settings - Fork 0
/
d14.py
178 lines (139 loc) · 4.67 KB
/
d14.py
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
from itertools import cycle
print('Day 14 of Advent of Code!')
STONE = 'O'
BLOCK = '#'
UP = 'U'
DOWN = 'D'
LEFT = 'L'
RIGHT = 'R'
DIRECTIONS = cycle((UP, LEFT, DOWN, RIGHT))
def parse_grid(data):
grid = {}
lines = data.splitlines()
for i, line in enumerate(lines):
for j, char in enumerate(line):
grid[(i,j)] = char
return grid, len(lines), len(lines[0])
def get_rows(grid, i, j):
rows = []
for row in range(i):
rows.append(([grid[row,col] for col in range(j)]))
return rows
def get_cols(grid, i, j):
cols = []
for col in range(j):
cols.append([grid[row, col] for row in range(i)])
return cols
def hash_grid(grid):
return hash(str(grid.items()))
def parse_col_or_row(colrow, direction):
stones = []
blocks = []
for idx, item in enumerate(colrow):
if item == STONE:
stones.append(idx)
if item == BLOCK:
blocks.append(idx)
if direction == UP or direction == LEFT:
blocks.insert(0, -1)
elif direction == DOWN or direction == RIGHT:
blocks.append(len(colrow))
return stones, blocks
def move_rocks(grid, idx, colrows, direction):
stones, blocks = parse_col_or_row(colrows[idx], direction)
if not stones:
return stones, grid
# remove stones first
if direction == UP or direction == DOWN:
for stone_pos in stones:
grid[stone_pos, idx] = '.'
elif direction == LEFT or direction == RIGHT:
for stone_pos in stones:
grid[idx, stone_pos] = '.'
# move stones
if direction == UP or direction == LEFT:
for i in range(len(stones)):
for j in range(len(blocks)-1, -1, -1):
if blocks[j] < stones[i]:
stones[i] = blocks[j] + 1
blocks[j] += 1
break
elif direction == DOWN or direction == RIGHT:
for i in range(len(stones)-1, -1, -1):
for j in range(0, len(blocks), 1):
if blocks[j] > stones[i]:
stones[i] = blocks[j] - 1
blocks[j] -= 1
break
# put the stones back in grid
if direction == UP or direction == DOWN:
for stone_pos in stones:
grid[stone_pos, idx] = 'O'
elif direction == LEFT or direction == RIGHT:
for stone_pos in stones:
grid[idx, stone_pos] = 'O'
return stones, grid
def count_load(columns):
s = 0
for col in columns:
stones, _ = parse_col_or_row(col, UP)
max_score = len(col)
scores = [max_score - stone for stone in stones]
s += sum(scores)
return s
def spin_cycle(data):
grid, i, j = parse_grid(data)
rounds = 0
hashes = {}
hashes[rounds] = hash_grid(grid)
scores = {}
scores[rounds] = count_load(get_cols(grid, i, j))
cycle_start = None
cycle_lenght = None
while True:
for _ in range(4):
next_dir = next(DIRECTIONS)
if next_dir == UP or next_dir == DOWN:
colrows = get_cols(grid, i, j)
elif next_dir == LEFT or next_dir == RIGHT:
colrows = get_rows(grid, i, j)
for idx in range(len(colrows)):
_, grid = move_rocks(grid, idx, colrows, next_dir)
rounds += 1
current_hash = hash_grid(grid)
for rd, hsh in hashes.items():
if not cycle_start and hsh == current_hash:
cycle_start = rd
if cycle_start and current_hash == hashes[cycle_start]:
cycle_lenght = rounds - cycle_start
hashes[rounds] = current_hash
scores[rounds] = count_load(get_cols(grid, i, j))
if cycle_start and cycle_lenght:
proper_id = cycle_start + ((1000000000 - cycle_start) % cycle_lenght)
return scores[proper_id]
TEST_DATA = '''O....#....
O.OO#....#
.....##...
OO.#O....O
.O.....O#.
O.#..O.#.#
..O..#O..O
.......O..
#....###..
#OO..#....'''
print('Testing...')
test_grid, h, w = parse_grid(TEST_DATA)
test_cols = get_cols(test_grid, h, w)
for col_idx in range(len(test_cols)):
_, test_grid = move_rocks(test_grid, col_idx, test_cols, UP)
print('Part 1:', count_load(get_cols(test_grid, w, h)) == 136)
print('Part 2:', spin_cycle(TEST_DATA) == 64)
with open('inp', mode='r', encoding='utf-8') as inp:
print('Solution...')
actual_data = inp.read()
actual_grid, w, h = parse_grid(actual_data)
actual_cols = get_cols(actual_grid, w, h)
for col_idx in range(len(actual_cols)):
_, actual_grid = move_rocks(actual_grid, col_idx, actual_cols, UP)
print('Part 1:', count_load(get_cols(actual_grid, w, h)))
print('Part 2:', spin_cycle(actual_data))