Puzzle 22: Add ability to find the map outline

I need this for working out the shape of the net

1 files changed, 153 insertions, 0 deletions

diff --git a/22.c b/22.c
index e877c5a..60b2291 100644
--- a/22.c
+++ b/22.c
@@ -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;