#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.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(int argc, char ** argv)
{
	int part = 1;
	regex_t coords;
	char buf[BUFSIZ];
	char * cave = NULL;
	int xmin = 500, xmax = 500, ymax = 0;
	int grain;

	while ((grain = getopt(argc, argv, "p:")) != -1) {
		switch (grain) {
		case 'p':
			part = atoi(optarg);
			break;

		default:
			return -1;
		}
	}

	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 (part == 2) {
		// Lowest floor is 2 below original max, of infinite width. Only
		// need to keep track of one level of sand below
		if (cave_resize(&cave, &xmin, &xmax, &ymax, xmin, ymax + 1) != 0) {
			fprintf(stderr, "Unable to resize cave for %d,%d\n", xmin, xmax + 1);
			free(cave);
			regfree(&coords);
			return -1;
		}
	}

#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
		// at the bottom and either falling off as there's nothing below
		// it, or coming to rest on the infinite floor. 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;
			}
			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;
			}
			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 (x < xmin || x > xmax) {
				if (cave_resize(&cave, &xmin, &xmax, &ymax, (x < xmin ? x - 10 : x + 10), ymax) != 0) {
					fprintf(stderr, "Unable to resize cave for %d,%d\n", x, ymax);
					free(cave);
					regfree(&coords);
					return -1;
				}
			}
		}

#if 0
		cave_dump(cave, xmin, xmax, ymax);
#endif

		if (y >= ymax) {
			if (part == 2) {
				// Grain at rest on infinite floor
				cave[cavepos(xmin, xmax, ymax, x, y)] = 'o';
			}
			else if (part == 1) {
				// Grain fell out of cave
				break;
			}
			else {
				fprintf(stderr, "Unexpected part %d\n", part);
				break;
			}
		}
	}

	printf("Grains: %d\n", grain);

	free(cave);
	regfree(&coords);

	return 0;
}