Puzzle 22: Reorder net faces in array to match their faceid

This makes it so that, given cube face 0 is in map->faces[0] and
pointing north, cube face 1 will be in map->faces[1], cube face 2 will
be in map->faces[2], etc..., with their orientations set appropriately.

This will allow us to be able to tell where on the cube an elf is, and
where they're going if they walk off an edge.

1 files changed, 110 insertions, 0 deletions

diff --git a/22.c b/22.c
index 1b880bb..862dbda 100644
--- a/22.c
+++ b/22.c
@@ -147,6 +147,27 @@ faceid_orientation(int topid, int destid, enum direction destdir)
 }
 
 
+int
+mymemswap(void * a, void * b, size_t len)
+{
+	char tmp[BUFSIZ];
+
+	if (a == b)
+		return 0;
+
+	while (len > 0) {
+		size_t chunk = len < sizeof(tmp) ? len : sizeof(tmp);
+
+		memcpy(tmp, a, chunk);
+		memcpy(a, b, chunk);
+		memcpy(b, tmp, chunk);
+		len -= chunk;
+	}
+
+	return 0;
+}
+
+
 struct point {
 	int x;
 	int y;
@@ -195,9 +216,75 @@ struct map {
 
 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);
 
 
+static
+int
+map__init_faces_reorder(struct map * map, struct face const * face, struct face const * from)
+{
+	static enum direction const dirs[] = { D_NORTH, D_WEST, D_SOUTH, D_EAST };
+
+	int fsrcid, dir;
+
+	fsrcid = face - map->faces;
+
+	for (dir = 0; dir < 4; ++dir) {
+		struct face * nbr;
+		int nbrid;
+
+		// Get the neighbour in the net in one of the directions
+		switch (dirs[dir]) {
+		case D_NORTH:
+			nbr = (struct face *) map_face_at(map, face->vertices[3].x, face->vertices[3].y);
+			break;
+
+		case D_WEST:
+			nbr = (struct face *) map_face_at(map, face->vertices[0].x - 1, face->vertices[0].y);
+			break;
+
+		case D_SOUTH:
+			nbr = (struct face *) map_face_at(map, face->vertices[0].x, face->vertices[0].y - 1);
+			break;
+
+		case D_EAST:
+			nbr = (struct face *) map_face_at(map, face->vertices[1].x, face->vertices[1].y);
+			break;
+
+		default:
+			nbr = NULL;
+			break;
+		}
+
+		if (!nbr)
+			// There is no neighbour in the net at that location.
+			continue;
+		if (nbr == from)
+			// The neighbour is the face that told us to rearrange
+			// our neighbours. Do nothing.
+			continue;
+
+		// Find the id of the neighbour
+		nbrid = faceid_look(fsrcid, face->dir, dirs[dir]);
+
+		// Move the face into the right position in faces[]
+		mymemswap(map->faces + nbrid, nbr, sizeof(struct face));
+		nbr = map->faces + nbrid;
+
+		// Set its direction.
+		nbr->dir = faceid_orientation(nbrid, fsrcid, dirs[(dir + 2) % 4]);
+
+		// And reorder the faces around it
+		map__init_faces_reorder(map, nbr, face);
+	}
+
+	return 0;
+}
+
+
+static
 int
 map__init_faces(struct map * map)
 {
@@ -269,6 +356,11 @@ map__init_faces(struct map * map)
 		return -1;
 	}
 
+	// Reorder the faces around face 0, so that each face is in the right
+	// place in the faces[] array, and oriented appropriately, according
+	// to faceids[]
+	map__init_faces_reorder(map, map->faces + 0, NULL);
+
 	free(outline);
 	return 0;
 }
@@ -354,6 +446,24 @@ map_elem(struct map const * map, int x, int y)
 }
 
 
+// Get the face at a particular x,y co-ordinate
+struct face const *
+map_face_at(struct map const * map, int x, int y)
+{
+	struct face const * face;
+
+	if (map->type != M_NET)
+		return NULL;
+
+	for (face = map->faces; face < map->faces + 6; ++face)
+		if (x >= face->vertices[0].x && x < face->vertices[2].x
+				&& y >= face->vertices[0].y && y < face->vertices[2].y)
+			return face;
+
+	return NULL;
+}
+
+
 // Get the outline of the map, anti-clockwise
 //
 // Note that for lengths to be correct, as we're tracing south and east we keep