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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
import aoc20
import sys
import itertools
UP, RIGHT, DOWN, LEFT = 0, 1, 2, 3
def mirror(n):
return int(bin(n)[2:].zfill(10)[::-1], 2)
def rotations(lst):
def rotate_cw(lst):
return [
mirror(lst[LEFT]), # up
lst[UP], # right
mirror(lst[RIGHT]), # down
lst[DOWN]] # left
lst = [lst]
for _ in range(3):
lst += [rotate_cw(lst[-1])]
return lst
def all_tiles(tile):
# assumes 10x10 tile as 100 chars
# returns the eight different transformations:
# [
# rotated cw mirrored through horizontal
# 0 no
# 1 no
# 2 no
# 3 no
# 0 yes
# 1 yes
# 2 yes
# 3 yes
# ]
tiles = []
tiles.append(tile[:10]) # up
tiles.append(tile[9::10]) # right
tiles.append(tile[-10:]) # down
tiles.append(tile[::10]) # left
tiles = list(map(lambda r: int(r.replace("#", "1").replace(".", "0"), 2), tiles))
tiles = rotations(tiles)
# mirror through horizontal by
# flipping up and down
# mirroring left and right respectively
tiles += [[tile[DOWN], # up
mirror(tile[RIGHT]), # right
tile[UP], # down
mirror(tile[LEFT])] # left
for tile in tiles]
return tiles
def neighbours(p, w, h):
# None if outside w, h
return [
(p[0], p[1]-1) if p[1]-1 >= 0 else None,
(p[0]+1, p[1]) if p[0]+1 < w else None,
(p[0], p[1]+1) if p[1]+1 < h else None,
(p[0]-1, p[1]) if p[0]-1 >= 0 else None,
]
def valid(state, p, w, h):
n = neighbours(p, w, h)
# a neighbour is valid if any of the following:
# it's outside w, h
# it's inside w, h but not placed
# it's placed and its corresponding side matches this position's side
return all((
not n[UP] or n[UP] not in state or state[p][UP] == state[n[UP]][DOWN],
not n[RIGHT] or n[RIGHT] not in state or state[p][RIGHT] == state[n[RIGHT]][LEFT],
not n[DOWN] or n[DOWN] not in state or state[p][DOWN] == state[n[DOWN]][UP],
not n[LEFT] or n[LEFT] not in state or state[p][LEFT] == state[n[LEFT]][RIGHT],
))
def next_pos(p, w):
# like a typewriter
x, y = p
return ((x+1) % w, y + (x+1)//w)
def gen_image(_in, w, h):
tile_borders = dict() # id: [sides as encoded numbers]
tiles = dict() # id: [rows as characters]
for tile in "".join(_in)[:-1].split("\n\n"):
num = int(tile.split("\n")[0].split(" ")[1][:-1])
tile_borders[num] = all_tiles(tile[tile.find(":")+2:].replace("\n", ""))
tiles[num] = tile[tile.find(":")+2:]
def test(state, next, left, placed):
# state: {(x, y): (UP, RIGHT, DOWN, LEFT)}
# next: (x, y), next empty position
# left: set(tile), tile indicies available
# placed: [(tile, mod)], placed tiles and their modification id
#
# returns a valid state or None if none exist
if not left:
return state, placed
for tile in left:
for i, mod in enumerate(tile_borders[tile]):
new = state.copy()
new[next] = mod
if valid(new, next, w, h):
test_res = test(new, next_pos(next, w), left - set([tile]), placed + [(tile, i)])
if test_res:
return test_res
return None
return test(dict(), (0, 0), set(tile_borders.keys()), []), tiles
def pt1(_in):
res = gen_image(_in, 12, 12)[0][1]
return res[0][0] * res[11][0] * res[-12][0] * res[-1][0]
def pt2(_in):
image = gen_image(_in, 12, 12)
def rotate_cw(mat, s):
res = [[None for _ in range(s)] for _ in range(s)]
for y in range(s):
for x in range(s):
res[x][s-y-1] = mat[y][x]
return res
def mirror(mat, s):
res = [[None for _ in range(s)] for _ in range(s)]
for y in range(s):
for x in range(s):
res[y][x] = mat[s-y-1][x]
return res
def mir_rot(mat, mod):
for _ in range(mod % 4):
mat = rotate_cw(mat, len(mat))
for _ in range(mod // 4):
mat = mirror(mat, len(mat))
return mat
def has_monster(image, x, y, w, h):
monster = [
" # ",
"# ## ## ###",
" # # # # # # "
]
for dy in range(len(monster)):
img_y = y + dy
if not 0 <= img_y < h:
return False
for dx in range(len(monster[dy])):
img_x = x + dx
if not 0 <= img_x < w:
return False
if monster[dy][dx] == "#" and image[img_y][img_x] != "#":
return False
return True
# orient tiles
tiles = [mir_rot(image[1][tile[0]].split("\n"), tile[1])
for tile in image[0][1]]
# remove borders
tiles = [[row[1:-1]
for row in tile[1:-1]]
for tile in tiles]
# build the total image
total = []
for tile_row in range(12):
for row in range(8):
total.append("".join(["".join(tiles[tile_row*12 + tile][row]) for tile in range(12)]))
#TODO this should work
# total = ["".join(["".join(tiles[tile_row*12 + tile][row])
# for tile in range(12)])
# for row in range(8)
# for tile_row in range(12)]
for mod in range(8):
image = mir_rot(total, mod)
h = len(image)
w = len(image[0])
monsters = sum(1 if has_monster(image, x, y, w, h) else 0
for x in range(w)
for y in range(h))
if monsters != 0:
return sum(row.count("#") for row in image) - monsters * 15
if __name__ == "__main__":
_in = aoc20.read_input(sys.argv[1:], 20)
print(pt1(_in))
print(pt2(_in))
|
