Solve puzzle 14 part 1

1 files changed, 228 insertions, 0 deletions

diff --git a/14.c b/14.c
new file mode 100644
index 0000000..4a51c76
--- /dev/null
+++ b/14.c
@@ -0,0 +1,228 @@
+
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#define arrlen(x) (sizeof(x)/sizeof((x)[0]))
+
+
+int
+cavepos(int xmin, int xmax, int ymax, int x, int y)
+{
+	if (x < xmin || x > xmax || y < 0 || y > ymax) {
+		fprintf(stderr, "%s: %d/%d/%d/%d/%d\n", __FUNCTION__, xmin, xmax, ymax, x, y);
+		return 0;
+	}
+	return x - xmin + y * (1 + xmax - xmin);
+}
+
+
+int
+cave_resize(char ** cave, int * xmin, int * xmax, int * ymax,
+		int x, int y)
+{
+	int newxmin, newxmax, newymax;
+	void * p;
+
+	if (y < 0)
+		// Oops
+		return -1;
+
+	if (y <= *ymax && x >= *xmin && x <= *xmax)
+		// Nothing to do.
+		return 0;
+
+	newxmin = x < *xmin ? x : *xmin;
+	newxmax = x > *xmax ? x : *xmax;
+	newymax = y > *ymax ? y : *ymax;
+
+	p = calloc(newymax + 1, 1 + newxmax - newxmin);
+	if (!p)
+		return -1;
+
+	if (*cave) {
+		int i;
+		for (i = 0; i <= *ymax; ++i) {
+			memcpy(p + i * (1 + newxmax - newxmin) + *xmin - newxmin,
+					*cave + i * (1 + *xmax - *xmin),
+					1 + *xmax - *xmin);
+		}
+		free(*cave);
+	}
+
+	*cave = p;
+	*xmin = newxmin;
+	*xmax = newxmax;
+	*ymax = newymax;
+
+	return 0;
+}
+
+
+#if 0
+void
+cave_dump(char * cave, int xmin, int xmax, int ymax)
+{
+	int x, y;
+
+	for (y = 0; y <= ymax; ++y) {
+		for (x = xmin; x <= xmax; ++x) {
+			char c = cave[cavepos(xmin, xmax, ymax, x, y)];
+			fputc(c ? c : '.', stderr);
+		}
+		fputc('\n', stderr);
+	}
+	fputc('\n', stderr);
+}
+#endif
+
+
+int
+main()
+{
+	regex_t coords;
+	char buf[BUFSIZ];
+	char * cave = NULL;
+	int xmin = 500, xmax = 500, ymax = 0;
+	int grain;
+
+	if (regcomp(&coords, "( -> )?([[:digit:]]+),([[:digit:]]+)", REG_EXTENDED) != 0) {
+		fprintf(stderr, "Bad regex\n");
+		return -1;
+	}
+
+	// Read the cave
+	while (fgets(buf, sizeof(buf), stdin)) {
+		char * pos;
+		int x, y;
+		regmatch_t xy[4];
+
+		pos = buf;
+		if (regexec(&coords, pos, arrlen(xy), xy, 0) != 0) {
+			fprintf(stderr, "No coords found in %s\n", pos);
+			free(cave);
+			regfree(&coords);
+			return -1;
+		}
+		x = atoi(buf + xy[2].rm_so);
+		y = atoi(buf + xy[3].rm_so);
+		if (cave_resize(&cave, &xmin, &xmax, &ymax, x, y) != 0) {
+			fprintf(stderr, "Unable to resize cave for %d,%d\n", x, y);
+			free(cave);
+			regfree(&coords);
+			return -1;
+		}
+		pos += xy[0].rm_eo;
+
+		while (regexec(&coords, pos, arrlen(xy), xy, 0) == 0) {
+			int newx, newy, i;
+
+			newx = atoi(pos + xy[2].rm_so);
+			newy = atoi(pos + xy[3].rm_so);
+			if (cave_resize(&cave, &xmin, &xmax, &ymax, newx, newy) != 0) {
+				fprintf(stderr, "Unable to resize cave for %d,%d\n", newx, newy);
+				free(cave);
+				regfree(&coords);
+				return -1;
+			}
+
+			if ((newx != x && newy != y)
+					|| (newx == x && newy == y))
+			{
+				fprintf(stderr, "Unexpected %d,%d -> %d,%d\n", x, y, newx, newy);
+			}
+			else if (newx != x) {
+				for (i = x; i < newx; ++i) {
+					cave[cavepos(xmin, xmax, ymax, i, y)] = '#';
+				}
+				for (i = x; i > newx; --i) {
+					cave[cavepos(xmin, xmax, ymax, i, y)] = '#';
+				}
+			}
+			else if (newy != y) {
+				for (i = y; i < newy; ++i) {
+					cave[cavepos(xmin, xmax, ymax, x, i)] = '#';
+				}
+				for (i = y; i > newy; --i) {
+					cave[cavepos(xmin, xmax, ymax, x, i)] = '#';
+				}
+			}
+
+			x = newx;
+			y = newy;
+			pos += xy[0].rm_eo;
+		}
+
+		cave[cavepos(xmin, xmax, ymax, x, y)] = '#';
+
+		if (*pos != '\n') {
+			fprintf(stderr, "Unexpected remaining line: %s\n", pos);
+		}
+	}
+
+#if 0
+	cave_dump(cave, xmin, xmax, ymax);
+#endif
+
+	// Simulate sand
+	for (grain = 0; 1; ++grain) {
+		int x, y;
+
+		x = 500;
+
+		if (cave[cavepos(xmin, xmax, ymax, x, 0)] != '\0')
+			// Grain can't enter the cave!
+			break;
+
+		// Don't go to "y <= ymax" here. If the grain gets to ymax, it's
+		// falling off the bottom as there's nothing below it. And an
+		// attempt to look at the row below isn't valid.
+		for (y = 0; y < ymax; ++y) {
+			if (cave[cavepos(xmin, xmax, ymax, x, y + 1)] == '\0') {
+				// Do nothing, drop down one
+				(void) 0;
+			}
+			else if (x == xmin) {
+				// Fall off left edge
+				--x;
+				break;
+			}
+			else if (cave[cavepos(xmin, xmax, ymax, x - 1, y + 1)] == '\0') {
+				// Drop down and left
+				--x;
+			}
+			else if (x == xmax) {
+				// Fall off right edge
+				++x;
+				break;
+			}
+			else if (cave[cavepos(xmin, xmax, ymax, x + 1, y + 1)] == '\0') {
+				// Drop down and right
+				++x;
+			}
+			else {
+				// Settle
+				cave[cavepos(xmin, xmax, ymax, x, y)] = 'o';
+				break;
+			}
+		}
+
+#if 0
+		cave_dump(cave, xmin, xmax, ymax);
+#endif
+
+		if (x < xmin || x > xmax || y >= ymax)
+			// Grain fell out of cave
+			break;
+	}
+
+	printf("Grains: %d\n", grain);
+
+	free(cave);
+	regfree(&coords);
+
+	return 0;
+}
+