#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;
}