diff options
| -rw-r--r-- | 22.c | 153 |
1 files changed, 153 insertions, 0 deletions
@@ -147,6 +147,21 @@ faceid_orientation(int topid, int destid, enum direction destdir) } +struct point { + int x; + int y; +}; + + +struct point * +point_init(struct point * pt, int x, int y) +{ + pt->x = x; + pt->y = y; + return pt; +} + + struct map { char * _buf; int cols; @@ -155,6 +170,9 @@ struct map { }; +int map_outline(struct point ** outline, struct map const * map); + + // Initialise a map from a buffer. // // The map takes ownership of the buffer from when it's called, whether @@ -200,6 +218,20 @@ map_init(struct map * map, char * buf, size_t buflen, enum map_type type) map->_buf[pos * map->cols + map->cols - 1] = '\n'; } + if (map->type == M_NET) { + struct point * outline; + int len; + + if ((len = map_outline(&outline, map)) < 0) { + free(map->_buf); + return NULL; + } + + fprintf(stderr, "Outline has %d corners\n", len - 1); + + free(outline); + } + return map; } @@ -226,6 +258,127 @@ map_elem(struct map const * map, int x, int y) } +// Get the outline of the map, anti-clockwise +// +// 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. +// +// Duplicates the first/last corner, because this makes some things easier. +// +// Returns number of corners found (including duplicate), or -1 on error +int +map_outline(struct point ** outline, struct map const * map) +{ + struct point * pt; + int len = 2; + enum direction dir; + + if ((*outline = malloc(len * sizeof(struct point))) == NULL) { + fprintf(stderr, "%s: Bad malloc(%ld)\n", + __FUNCTION__, len * sizeof(struct point)); + return -1; + } + + // Start from the top-left, because we know there has to be a + // starting point for the elf there, and head south. + pt = *outline; + point_init(pt, 0, map->rows - 1); + while (map_elem(map, pt->x, pt->y) == ' ') + ++pt->x; + ++pt->y; + dir = D_SOUTH; + + while (1) { + struct point pt_move, pt_left, pt_right; + enum direction turn_left, turn_right; + + // Based on which direction we're going, figure out how to move + // forward, which elements to look at to decide if we need to + // turn left or right, and which way is left and right. + switch (dir) { + case D_NORTH: + point_init(&pt_move, 0, 1); + point_init(&pt_left, -1, 0); + point_init(&pt_right, 0, 0); + turn_left = D_WEST; + turn_right = D_EAST; + break; + + case D_SOUTH: + point_init(&pt_move, 0, -1); + point_init(&pt_left, 0, -1); + point_init(&pt_right, -1, -1); + turn_left = D_EAST; + turn_right = D_WEST; + break; + + case D_EAST: + point_init(&pt_move, 1, 0); + point_init(&pt_left, 0, 0); + point_init(&pt_right, 0, -1); + turn_left = D_NORTH; + turn_right = D_SOUTH; + break; + + case D_WEST: + point_init(&pt_move, -1, 0); + point_init(&pt_left, -1, -1); + point_init(&pt_right, -1, 1); + turn_left = D_SOUTH; + turn_right = D_NORTH; + break; + } + + // Move forward until we need to turn + pt = *outline + len - 1; + point_init(pt, (pt - 1)->x, (pt - 1)->y); + while (1) { + pt->x += pt_move.x; + pt->y += pt_move.y; + + if (map_elem(map, pt->x + pt_left.x, pt->y + pt_left.y) == ' ') { + dir = turn_left; + break; + } + if (map_elem(map, pt->x + pt_right.x, pt->y + pt_right.y) != ' ') { + dir = turn_right; + break; + } + } + + // Is the turning point back at the start? If so, we're done. + if (len > 4 && pt->x == (*outline)->x && pt->y == (*outline)->y) + return len; + + // Sanity check + if (len > 100) { + fprintf(stderr, "%s: Too many corners (%d)!\n", + __FUNCTION__, len); + free(*outline); + *outline = NULL; + return -1; + } + + // No? OK, add a new point to check for. + ++len; + if ((pt = realloc(*outline, len * sizeof(struct point))) == NULL) { + fprintf(stderr, "%s: Bad realloc(%ld)\n", + __FUNCTION__, len * sizeof(struct point)); + free(*outline); + *outline = NULL; + return -1; + } + *outline = pt; + } + + fprintf(stderr, "%s: Unreachable!\n", __FUNCTION__); + free(*outline); + *outline = NULL; + return -1; +} + + struct elf { int x; int y; |