|
1 | 1 | from collections import namedtuple |
2 | | -from itertools import product, permutations |
| 2 | +from itertools import product |
3 | 3 |
|
4 | 4 | import numpy as np |
5 | | -from imgaug.augmenters.flip import fliplr, flipud |
| 5 | +from imgaug.augmenters.flip import fliplr |
6 | 6 | from imgaug.augmenters.geometric import Rot90 |
7 | | -from tqdm import tqdm |
| 7 | +from scipy.ndimage import generic_filter |
8 | 8 |
|
9 | | -Tile = namedtuple("Tile", "idx ns ts e") |
| 9 | +OrientedTile = namedtuple("OrientedTile", "idx data") |
10 | 10 |
|
11 | | -with open("input2.txt") as f: |
| 11 | +ndim = 12 |
| 12 | +with open("input.txt") as f: |
12 | 13 | parts = f.read().split("\n\n") |
13 | 14 |
|
14 | 15 | tiles = {} |
|
18 | 19 | a = (np.array(k) == "#").astype(np.uint8) |
19 | 20 | tiles[int(p[0].split()[1][:-1])] = a |
20 | 21 |
|
21 | | -def transform(tile, rot, lr, ud): |
| 22 | +def transform(tile, rot, lr): |
22 | 23 | t = Rot90(rot).augment_image(tile) |
23 | 24 | if lr: |
24 | 25 | t = fliplr(t) |
25 | | - if ud: |
26 | | - t = flipud(t) |
27 | 26 | return t |
28 | 27 |
|
| 28 | +def get_all_transforms(arr): |
| 29 | + return [transform(arr, r, f) for r, f in product([0,1,2,3], [False, True])] |
| 30 | + |
29 | 31 | def edge_has_fit(tiles, tile_idx, edge): |
30 | | - k = tiles[tile_idx] |
31 | | - |
32 | | - if edge == 0: e = k[0] |
33 | | - elif edge == 1: e = k[:,-1] |
34 | | - elif edge == 2: e = k[-1] |
35 | | - elif edge == 3: e = k[:,0] |
| 32 | + tile_data = tiles[tile_idx] |
| 33 | + |
| 34 | + if edge == 0: e = tile_data[0] |
| 35 | + elif edge == 1: e = tile_data[:,-1] |
| 36 | + elif edge == 2: e = tile_data[-1] |
| 37 | + elif edge == 3: e = tile_data[:,0] |
36 | 38 |
|
37 | 39 | for idx, tile in tiles.items(): |
38 | 40 | if idx == tile_idx: continue |
39 | 41 |
|
40 | | - for trans in product([0,1,2,3], [False, True], [False, True]): |
41 | | - t = transform(tile, *trans) |
42 | | - for f in [t[0], t[:,-1], t[-1], t[:,0]]: |
43 | | - if np.array_equal(f, e): |
44 | | - return idx, trans |
45 | | - return None, None |
46 | | - |
47 | | -res = [] |
48 | | -# for idx in tqdm(tiles.keys()): |
49 | | -for idx in tiles.keys(): |
50 | | - ns, ts = zip(*[edge_has_fit(tiles, idx, i) for i in range(4)]) |
51 | | - tile = Tile(idx, ns, ts, len([e for e in ns if e is not None])) |
52 | | - res.append(tile) |
53 | | - |
54 | | -# print(int(np.prod(corners))) |
55 | | - |
56 | | -corners = [t for t in res if t.e == 2] |
57 | | -edges = [t for t in res if t.e == 3] |
58 | | -middles = [t for t in res if t.e == 4] |
59 | | - |
60 | | -print([(t.idx, t.ns) for t in corners]) |
61 | | -print([(t.idx, t.ns) for t in edges]) |
62 | | -print([(t.idx, t.ns) for t in middles]) |
63 | | -print("\n\n") |
64 | | - |
65 | | -nrows = 3 |
66 | | -ncols = 3 |
67 | | - |
68 | | -def rotate(l, n): |
69 | | - return list(l[n:] + l[:n]) |
70 | | - |
71 | | -def flip_lr(l): |
72 | | - return [l[0], l[3], l[2], l[1]] |
73 | | - |
74 | | -def flip_ud(l): |
75 | | - return [l[2], l[1], l[0], l[3]] |
76 | | - |
77 | | -def find_and_pop(elems, n_idx): |
78 | | - res = None |
79 | | - del_idx = None |
80 | | - for i, t in enumerate(elems): |
81 | | - if t.idx == n_idx: |
82 | | - res = t |
83 | | - del_idx = i |
84 | | - break |
85 | | - else: |
86 | | - raise RuntimeError(f"{t.idx} was not found in {elems}.") |
87 | | - |
88 | | - del elems[del_idx] |
89 | | - return res |
90 | | - |
91 | | -def match(ns, exp): |
92 | | - assert len(ns) == len(exp) |
93 | | - |
94 | | - for n, e in zip(ns, exp): |
95 | | - if e is None: |
96 | | - if n is not None: |
97 | | - return False |
98 | | - else: |
99 | | - if e == 0: |
100 | | - continue |
101 | | - else: |
102 | | - if n != e: |
103 | | - return False |
104 | | - return True |
105 | | - |
106 | | -def place(tile, exp): |
107 | | - if tile.idx == 1171: |
108 | | - print("orig") |
109 | | - print(tile.ns) |
110 | | - |
111 | | - n = tile.ns |
112 | | - t = tile.ts |
113 | | - for trans in product([0,1,2,3], [False, True], [False, True]): |
114 | | - n = rotate(n, trans[0]) |
115 | | - t = rotate(t, trans[0]) |
116 | | - if trans[1]: |
117 | | - n = flip_lr(n) |
118 | | - t = flip_lr(t) |
119 | | - if trans[2]: |
120 | | - n = flip_ud(n) |
121 | | - t = flip_ud(t) |
122 | | - |
123 | | - if tile.idx == 1171: |
124 | | - print(trans[0], "lr?", trans[1], "ud?", trans[2], end=" ") |
125 | | - print(n, exp) |
126 | | - if match(n, exp): |
127 | | - return Tile(tile.idx, n, t, tile.e) |
128 | | - |
129 | | - raise RuntimeError(tile) |
130 | | - |
131 | | -def print_short(l): |
132 | | - print([(t.idx, t.ns) for t in l]) |
133 | | - |
134 | | -layout = [] |
135 | | - |
136 | | -for idx_row in range(nrows): |
137 | | - if idx_row == 0: |
138 | | - tile = corners.pop() |
139 | | - tile = place(tile, [None, 0, 0, None]) |
140 | | - row = [tile] |
141 | | - elif idx_row == nrows-1: |
142 | | - tile = find_and_pop(corners, layout[idx_row-1][0].ns[2]) |
143 | | - upper = layout[idx_row-1][0].idx |
144 | | - tile = place(tile, [upper, 0, None, None]) |
145 | | - row = [tile] |
146 | | - else: |
147 | | - row = [find_and_pop(edges, layout[idx_row-1][0])] |
148 | | - |
149 | | - for idx_col in range(1, ncols): |
150 | | - prev_tile = row[-1] |
151 | | - n_idx = prev_tile.ns[1] |
| 42 | + for t in get_all_transforms(tile): |
| 43 | + if np.array_equal(t[0], e): |
| 44 | + return idx |
| 45 | + return None |
| 46 | + |
| 47 | +corners = [] |
| 48 | +for tile_idx in tiles: |
| 49 | + ns = [edge_has_fit(tiles, tile_idx, i) for i in range(4)] |
| 50 | + if len([e for e in ns if e is not None]) == 2: |
| 51 | + corners.append(tile_idx) |
| 52 | + if len(corners) == 4: |
| 53 | + break |
| 54 | +print(int(np.prod(corners))) |
| 55 | + |
| 56 | +# Part 2 |
| 57 | +def find_neighbor(tiles, tile, direction, seen): |
| 58 | + if direction == "right": |
| 59 | + arr = tile.data[:,-1] |
| 60 | + elif direction == "down": |
| 61 | + arr = tile.data[-1] |
| 62 | + |
| 63 | + for t_idx, t_data in tiles.items(): |
| 64 | + if t_idx == tile.idx: continue |
| 65 | + if t_idx in seen: continue |
152 | 66 |
|
153 | | - print_short(row) |
154 | | - print(idx_col, n_idx) |
155 | | - |
156 | | - if idx_row in (0, nrows-1): |
157 | | - if idx_col == ncols-1: |
158 | | - elems = corners |
159 | | - else: |
160 | | - elems = edges |
161 | | - else: |
162 | | - if idx_col == ncols-1: |
163 | | - elems = edges |
164 | | - else: |
165 | | - elem = middles |
166 | | - |
167 | | - t = find_and_pop(elems, n_idx) |
168 | | - |
169 | | - if idx_row == 0: |
170 | | - upper = None |
171 | | - else: |
172 | | - upper = layout[idx_row-1][0].idx |
173 | | - |
174 | | - left = prev_tile.idx |
175 | | - |
176 | | - if idx_col == ncols-1: |
177 | | - if idx_row == 0: |
178 | | - row.append(place(t, [None, None, 0, left])) |
179 | | - |
180 | | - elif idx_row == nrows-1: |
181 | | - row.append(place(t, [0, None, None, left])) |
182 | | - |
183 | | - else: |
184 | | - row.append(place(t, [upper, None, 0, left])) |
185 | | - else: |
186 | | - row.append(place(t, [upper, 0, 0, left])) |
187 | | - |
188 | | - layout.append(row) |
189 | | - |
190 | | -print(layout) |
| 67 | + for data in get_all_transforms(t_data): |
| 68 | + if direction == "right" and np.array_equal(arr, data[:,0]): |
| 69 | + return OrientedTile(t_idx, data) |
| 70 | + elif direction == "down" and np.array_equal(arr, data[0]): |
| 71 | + return OrientedTile(t_idx, data) |
| 72 | + |
| 73 | + raise Exception() |
| 74 | + |
| 75 | +corner_idx = corners[0] |
| 76 | +for corner_data in get_all_transforms(tiles[corner_idx]): |
| 77 | + try: |
| 78 | + seen = set() |
| 79 | + display = [[] for _ in range(ndim)] |
| 80 | + display[0].append(OrientedTile(corner_idx, corner_data)) |
| 81 | + seen.add(corners[0]) |
| 82 | + |
| 83 | + for idx_row in range(ndim): |
| 84 | + row = display[idx_row] |
| 85 | + while len(row) < ndim: |
| 86 | + n = find_neighbor(tiles, row[-1], "right", seen) |
| 87 | + row.append(n) |
| 88 | + seen.add(n.idx) |
| 89 | + |
| 90 | + if idx_row < ndim-1: |
| 91 | + n = find_neighbor(tiles, row[0], "down", seen) |
| 92 | + display[idx_row+1].append(n) |
| 93 | + seen.add(n.idx) |
| 94 | + except: |
| 95 | + continue |
| 96 | + break |
| 97 | + |
| 98 | +display2 = np.concatenate([np.concatenate([t.data[1:-1, 1:-1] for t in row], axis=1) for row in display]) |
| 99 | + |
| 100 | +nessi = np.array([list(" # "), |
| 101 | + list("# ## ## ###"), |
| 102 | + list(" # # # # # # ")]) |
| 103 | +nessi = (nessi == "#").astype(np.uint8) |
| 104 | + |
| 105 | +def f(part): |
| 106 | + part = np.reshape(part, nessi.shape) |
| 107 | + for y, row in enumerate(part): |
| 108 | + for x, pix in enumerate(row): |
| 109 | + if nessi[y][x] == 1 and pix == 0: |
| 110 | + return 0 |
| 111 | + return 1 |
| 112 | + |
| 113 | +found = max([np.sum(generic_filter(img, f, nessi.shape, mode="constant", cval=0)) for img in get_all_transforms(display2)]) |
| 114 | +roughness = int(np.count_nonzero(display2) - found*np.sum(nessi)) |
| 115 | +print(roughness) |
0 commit comments