~quf/computers-are-fast-2020

computers-are-fast-2020/src/20.c -rw-r--r-- 11.7 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <errno.h>

#define LENGTH(arr) (sizeof (arr) / sizeof (*arr))

typedef enum {
  O_ROT0, /* do nothing */
  O_ROT1, /* rotate clockwise by a quarter turn */
  O_ROT2, /* rotate clocwkise by a half turn */
  O_ROT3,
  O_ROT0_FLIPV, /* flip vertically */
  O_ROT1_FLIPV, /* rotate clockwise by a quarter turn, then flip */
  O_ROT2_FLIPV,
  O_ROT3_FLIPV,
} orientation_t;

typedef struct {
  unsigned n;
  unsigned edges[8];
  /* edges[0] is the top edge (left to right)
   * edges[1] is the left edge (down to up)
   * edges[2] is the bottom edge (right to left)
   * edges[3] is the right edge (up to down)
   * edges[4] is the top edge (right to left)
   * edges[5] is the left edge (up to down)
   * edges[6] is the bottom edge (left to right)
   * edges[7] is the right edge (down to up)
   */
  orientation_t orientation;
  /* the orientation only affects "data", not "edges"! */
  bool data[8*8];
} tile_t;

#define flatten(i, j, N) ((i) + (N) * (j))

unsigned reverse_bits(unsigned n) {
  unsigned m = 0;
  for (size_t i = 0; i < 10; ++i) {
    m = (m << 1) | (n & 1);
    n >>= 1;
  }
  return m;
}

unsigned count_bits(unsigned n) {
  unsigned count = 0;
  for (; n; count += (n & 1), n >>= 1);
  return count;
}

void rotate_edges_counterclockwise(unsigned edges[8]) {
  unsigned tmp;
  tmp = edges[3];
  edges[3] = edges[2];
  edges[2] = edges[1];
  edges[1] = edges[0];
  edges[0] = tmp;
  edges[4] = reverse_bits(edges[0]);
  edges[5] = reverse_bits(edges[1]);
  edges[6] = reverse_bits(edges[2]);
  edges[7] = reverse_bits(edges[3]);
}

void flip_edges_vertically(unsigned edges[8]) {
  edges[0] = edges[4];
  edges[1] = edges[7];
  edges[2] = edges[6];
  edges[3] = edges[5];
  edges[4] = reverse_bits(edges[0]);
  edges[5] = reverse_bits(edges[1]);
  edges[6] = reverse_bits(edges[2]);
  edges[7] = reverse_bits(edges[3]);
}

void reorient_edges(unsigned edges[8], orientation_t o) {
  switch (o) {
    case O_ROT3: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT2: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT1: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT0: break;
    case O_ROT3_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT2_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT1_FLIPV: rotate_edges_counterclockwise(edges); /* fall through */
    case O_ROT0_FLIPV: flip_edges_vertically(edges);
  }
}

bool find_matching_edge(const tile_t *tiles, const bool *used, size_t n_tiles, unsigned edge, size_t *which_tile, int *which_edge) {
  for (size_t i = 0; i < n_tiles; ++i) {
    const tile_t *t = tiles + i;
    if (used[i]) {
      continue;
    }
    for (int j = 0; j < 8; ++j) {
      if (t->edges[j] == edge) {
        *which_tile = i;
        *which_edge = j;
        return true;
      }
    }
  }
  return false;
}

bool matching_edge_exists(const tile_t *tiles, const bool *used, size_t n_tiles, unsigned edge) {
  size_t i;
  int e;
  return find_matching_edge(tiles, used, n_tiles, edge, &i, &e);
}

void rotate_data_counterclockwise(bool *data, size_t sx, size_t sy) {
  bool copy[sx * sy];
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      copy[flatten(iy, sx -1 - ix, sy)] = data[flatten(ix, iy, sx)];
    }
  }
  for (size_t i = 0; i < sx * sy; ++i) {
    data[i] = copy[i];
  }
}

void flip_data_vertically(bool *data, size_t sx, size_t sy) {
  bool copy[sx * sy];
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      copy[flatten(ix, iy, sx)] = data[flatten(sx - 1 - ix, iy, sx)];
    }
  }
  for (size_t i = 0; i < sx * sy; ++i) {
    data[i] = copy[i];
  }
}

void reorient_data(bool *data, size_t sx, size_t sy, orientation_t o) {
  switch (o) {
    case O_ROT3_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT2_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT1_FLIPV: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT0_FLIPV: flip_data_vertically(data, sx, sy); break;
    case O_ROT3: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT2: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT1: rotate_data_counterclockwise(data, sx, sy); // fall through
    case O_ROT0: break;
  }
}

int find_and_remove_monsters(bool *data, size_t sdx, size_t sdy, const bool *monster, size_t smx, size_t smy) {
  int n = 0;
  for (size_t ix = 0; ix + smx <= sdx; ++ix) {
    for (size_t iy = 0; iy + smy <= sdy; ++iy) {
      size_t overlap = 0;
      for (size_t dx = 0; dx < smx; ++dx) {
        for (size_t dy = 0; dy < smy; ++dy) {
          overlap += data[flatten(ix+dx, iy+dy, sdx)] & monster[flatten(dx, dy, smx)];
        }
      }
      if (overlap == 15) {
        /* the monster has 15 set tiles; got a match for all of them. */
        ++n;
        for (size_t dx = 0; dx < smx; ++dx) {
          for (size_t dy = 0; dy < smy; ++dy) {
            data[flatten(ix+dx, iy+dy, sdx)] &= !monster[flatten(dx, dy, smx)];
          }
        }
      }
    }
  }
  return n;
}

int main(void) {
  tile_t tiles[12*12];
  size_t n_tiles = 0;

  /* read tiles */
  while (n_tiles < LENGTH(tiles) && scanf("Tile %u:\n", &tiles[n_tiles].n) == 1) {
    bool data_with_edges[10*10] = { 0 };
    for (size_t j = 0; j < 10; ++j) {
      for (size_t i = 0; i < 10; ++i) {
        data_with_edges[flatten(i, j, 10)] = getchar() == '#';
      }
      (void) getchar();
    }
    (void) getchar();
    for (size_t j = 0; j < 8; ++j) {
      for (size_t i = 0; i < 8; ++i) {
        tiles[n_tiles].data[flatten(i, j, 8)] = data_with_edges[flatten(i+1, j+1, 10)];
      }
    }
    for (size_t i = 0; i < 8; ++i) {
      tiles[n_tiles].edges[i] = 0;
    }
    for (size_t i = 0; i < 10; ++i) {
      tiles[n_tiles].edges[0] = (tiles[n_tiles].edges[0] << 1) | data_with_edges[flatten(  i,   0, 10)];
      tiles[n_tiles].edges[1] = (tiles[n_tiles].edges[1] << 1) | data_with_edges[flatten(  0, 9-i, 10)];
      tiles[n_tiles].edges[2] = (tiles[n_tiles].edges[2] << 1) | data_with_edges[flatten(9-i,   9, 10)];
      tiles[n_tiles].edges[3] = (tiles[n_tiles].edges[3] << 1) | data_with_edges[flatten(  9,   i, 10)];
    }
    for (size_t i = 0; i < 4; ++i) {
      tiles[n_tiles].edges[i+4] = reverse_bits(tiles[n_tiles].edges[i]);
    }
    tiles[n_tiles].orientation = O_ROT0;
    ++n_tiles;
  }
  if (ferror(stdin) || !feof(stdin)) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }

  /* find a corner tile and place it at the top left, oriented such that its edges point down and right */
  bool used[LENGTH(tiles)] = { 0, };
  tile_t *tile_grid[LENGTH(tiles)] = { 0, };

  for (size_t i = 0; i < n_tiles; ++i) {
    used[i] = true;
    int m = 0;
    for (size_t e = 0; e < 4; ++e) {
      m |= matching_edge_exists(tiles, used, n_tiles, tiles[i].edges[e]) << e; // does the e'th edge (clockwise from the top) have a match?
    }
    if (count_bits(m) == 2) {
      tile_t *t = tiles + i;
      tile_grid[0] = t;
      switch(m) {
        case (1 | 2): // top and left have a match
          t->orientation = O_ROT2; break;
        case (1 | 8): // top and right have a match
          t->orientation = O_ROT3; break;
        case (2 | 4): // left and bottom have a match
          t->orientation = O_ROT1; break;
        case (4 | 8): // bottom and right have a match
          t->orientation = O_ROT0; break;
        default:
          fprintf(stderr, "huh?\n");
          return 1;
      }
      reorient_edges(t->edges, t->orientation);
      break;
    }
    used[i] = false;
  }

  if (!tile_grid[0]) {
    fprintf(stderr, "No edge tile found.\n");
    return 1;
  }

  /* fill the top row */
  size_t sx = 12;
  for (size_t ix = 1; ix < sx; ++ix) {
    unsigned target_edge = tile_grid[ix-1]->edges[3];
    int e = -1;
    size_t i = 0;
    if (find_matching_edge(tiles, used, n_tiles, target_edge, &i, &e)) {
      used[i] = true;
      tile_t *t = tiles + i;
      tile_grid[flatten(ix, 0, 12)] = t;
      switch (e) {
        /* NOTE: the orientations here run counter to the one of the tile on the left.
         * If we find a perfect match for edge 1 (left - bottom up) here, then we actually have to flip the tile horizontally!
         */
        case 0: t->orientation = O_ROT3_FLIPV; break;
        case 1: t->orientation = O_ROT2_FLIPV; break;
        case 2: t->orientation = O_ROT1_FLIPV; break;
        case 3: t->orientation = O_ROT0_FLIPV; break;
        case 4: t->orientation = O_ROT1; break;
        case 5: t->orientation = O_ROT0; break;
        case 6: t->orientation = O_ROT3; break;
        case 7: t->orientation = O_ROT2; break;
        default:
          fprintf(stderr, "huh?\n");
          return 1;
      }
      reorient_edges(t->edges, t->orientation);
    }
    else {
      sx = ix;
    }
  }

  /* fill the rows below */
  size_t sy = 12;
  for (size_t iy = 1; iy < sy; ++iy) {
    bool any_match = false;
    for (size_t ix = 0; ix < sx; ++ix) {
      unsigned target_edge = tile_grid[flatten(ix, iy-1, 12)]->edges[2];
      int e = -1;
      size_t i = 0;
      if (find_matching_edge(tiles, used, n_tiles, target_edge, &i, &e)) {
        any_match = true;
        used[i] = true;
        tile_t *t = tiles + i;
        tile_grid[flatten(ix, iy, 12)] = t;
        switch (e) {
        /* NOTE: the orientations here run counter to the one of the tile on the left.
         * If we find a perfect match for edge 0 (top - left right) here, then we actually have to flip the tile vertically!
         */
          case 0: t->orientation = O_ROT0_FLIPV; break;
          case 1: t->orientation = O_ROT3_FLIPV; break;
          case 2: t->orientation = O_ROT2_FLIPV; break;
          case 3: t->orientation = O_ROT1_FLIPV; break;
          case 4: t->orientation = O_ROT0; break;
          case 5: t->orientation = O_ROT3; break;
          case 6: t->orientation = O_ROT2; break;
          case 7: t->orientation = O_ROT1; break;
          default:
            fprintf(stderr, "huh?\n");
            return 1;
        }
        reorient_edges(t->edges, t->orientation);
      }
      else {
        break;
      }
    }
    if (!any_match) {
      sy = iy;
      break;
    }
  }

  /* part1: product of tile numbers for the edges */
  printf("%llu\n",
    ((unsigned long long) tile_grid[flatten(0,       0, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(sx-1,    0, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(0,    sy-1, 12)]->n)
  * ((unsigned long long) tile_grid[flatten(sx-1, sy-1, 12)]->n));

  /* re-join image data */
  bool image_data[8*12*8*12] = { 0, };
  for (size_t iy = 0; iy < sy; ++iy) {
    for (size_t ix = 0; ix < sx; ++ix) {
      reorient_data(tile_grid[flatten(ix, iy, 12)]->data, 8, 8, tile_grid[flatten(ix, iy, 12)]->orientation);
      tile_grid[flatten(ix, iy, 12)]->orientation = O_ROT0;
      for (size_t jy = 0; jy < 8; ++jy) {
        for (size_t jx = 0; jx < 8; ++jx) {
          image_data[flatten(ix*8+jx, iy*8+jy, 8*12)] = tile_grid[flatten(ix, iy, 12)]->data[flatten(jx, jy, 8)];
        }
      }
    }
  }

  /* look for sea monster */
  bool monster[3*20] = {
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
    1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1,
    0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,
  };
  size_t smx = 20;
  size_t smy = 3;

  for (int i = 0; i < 8; ++i) {
    if (find_and_remove_monsters(image_data, 8*12, 8*12, monster, smx, smy)) {
      break;
    }
    rotate_data_counterclockwise(monster, smx, smy);
    { size_t tmp = smx; smx = smy; smy = tmp; }
    if (i == 4) {
      flip_data_vertically(monster, smx, smy);
    }
  }

  size_t sum = 0;
  for (size_t i = 0; i < LENGTH(image_data); ++i) {
    sum += image_data[i];
  }
  printf("%zu\n", sum);

  return 0;
}