diff options
| -rw-r--r-- | 22.c | 72 |
1 files changed, 67 insertions, 5 deletions
@@ -168,6 +168,41 @@ mymemswap(void * a, void * b, size_t len) } +// Not very performant, but we're only dealing with small numbers here. +int +highestcommonfactor(int x, int y) +{ + int hcf = 1, test; + + if (x <= 0 || y <= 0) + return 0; + + // Make sure x is bigger than y. + if (x < y) + return highestcommonfactor(y, x); + + // Quick check, is y a factor of x? + if (x % y == 0) + return y; + + while (x % 2 == 0 && y % 2 == 0) { + x /= 2; + y /= 2; + hcf *= 2; + } + + for (test = 3; test * test < y; test += 2) { + while (x % test == 0 && y % test == 0) { + x /= test; + y /= test; + hcf *= test; + } + } + + return hcf; +} + + struct point { int x; int y; @@ -218,7 +253,7 @@ int map_elem(struct map const * map, int x, int y); struct face const * map_face_at(struct map const * map, int x, int y); -int map_outline(struct point ** outline, struct map const * map); +int map_outline(struct point ** outline, struct map const * map, int sidelen); static @@ -286,12 +321,12 @@ map__init_faces_reorder(struct map * map, struct face const * face, struct face static int -map__init_faces(struct map * map) +map__init_faces(struct map * map, int sidelen) { struct point * outline, * ol, min, max, pt; int len, nfaces; - if ((len = map_outline(&outline, map)) < 0) { + if ((len = map_outline(&outline, map, sidelen)) < 0) { return -1; } @@ -351,6 +386,25 @@ map__init_faces(struct map * map) // TODO: Add face-splitting logic here, to account for e.g. // T-shaped nets, where we don't have outline corners to tell // us where the faces are. + + // I don't have face-splitting logic yet. Been thinking about + // this, and it should be possible to split the faces correctly + // for the net of an arbitrary cuboid, given the side lengths + // and geometry we can infer, but I can't figure it out yet. + // For now, we know that + // a) the Advent of Code challenge is only for cubes + // b) and the map given is the mimimun size required to hold a + // given net, other than the newlines + // c) All 11 possible cube nets are either 4:3 or 5:2, and + // therefore have no common factors in their overall size + if (sidelen == -1) { + sidelen = highestcommonfactor(map->rows, map->cols - 1); + if (map__init_faces(map, sidelen) == 0) { + free(outline); + return 0; + } + } + fprintf(stderr, "%s: Only %d faces\n", __FUNCTION__, nfaces); free(outline); return -1; @@ -412,7 +466,7 @@ map_init(struct map * map, char * buf, size_t buflen, enum map_type type) } if (map->type == M_NET) { - if (map__init_faces(map) != 0) { + if (map__init_faces(map, -1) != 0) { free(map->_buf); return NULL; } @@ -466,6 +520,10 @@ map_face_at(struct map const * map, int x, int y) // Get the outline of the map, anti-clockwise // +// If you know that the map is the net of a cuboid of side length `sidelen`, +// pass that parameter to help it find "corners" on straight edges of the net. +// Otherwise pass -1. +// // Note that for lengths to be correct, as we're tracing south and east we keep // inside the map, but as we're tracing north and west we keep one element // outside the map. @@ -474,7 +532,7 @@ map_face_at(struct map const * map, int x, int y) // // Returns number of corners found (including duplicate), or -1 on error int -map_outline(struct point ** outline, struct map const * map) +map_outline(struct point ** outline, struct map const * map, int sidelen) { struct point * pt; int len = 2; @@ -498,6 +556,7 @@ map_outline(struct point ** outline, struct map const * map) while (1) { struct point pt_move, pt_left, pt_right; enum direction turn_left, turn_right; + int dist = 0; // Based on which direction we're going, figure out how to move // forward, which elements to look at to decide if we need to @@ -542,6 +601,7 @@ map_outline(struct point ** outline, struct map const * map) while (1) { pt->x += pt_move.x; pt->y += pt_move.y; + ++dist; if (map_elem(map, pt->x + pt_left.x, pt->y + pt_left.y) == ' ') { dir = turn_left; @@ -551,6 +611,8 @@ map_outline(struct point ** outline, struct map const * map) dir = turn_right; break; } + if (dist == sidelen) + break; } // Is the turning point back at the start? If so, we're done. |