#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


#define arrlen(x) (sizeof(x)/sizeof((x)[0]))

#define max(a, b) ((a) > (b) ? (a) : (b))


enum MATERIAL {
	ORE,
	CLAY,
	BSDN,
	GEOD,
};


struct blueprint {
	int id;
	int ore_ore;
	int clay_ore;
	int bsdn_ore;
	int bsdn_clay;
	int geod_ore;
	int geod_bsdn;

	int max_ore;
	int max_clay;
	int max_bsdn;
};


void
blueprint_ctor(struct blueprint * b, int id, int ore_ore, int clay_ore,
		int bsdn_ore, int bsdn_clay, int geod_ore, int geod_bsdn)
{
	b->id = id;
	b->ore_ore = ore_ore;
	b->clay_ore = clay_ore;
	b->bsdn_ore = bsdn_ore;
	b->bsdn_clay = bsdn_clay;
	b->geod_ore = geod_ore;
	b->geod_bsdn = geod_bsdn;

	b->max_ore = max(max(b->ore_ore, b->clay_ore), max(b->bsdn_ore, b->geod_ore));
	b->max_clay = b->bsdn_clay;
	b->max_bsdn = b->geod_bsdn;
}


struct material {
	int amount;
	int robots;
};


void
material_ctor(struct material * m, int amount, int robots)
{
	m->amount = amount;
	m->robots = robots;
}


// Tick a material.
//
// Amount increases by the number of robots
// Number of robots increases by number of pending robots
void
material_tick(struct material * m, int build)
{
	m->amount += m->robots;
	if (build)
		++m->robots;
}


struct inventory {
	struct material ore;
	struct material clay;
	struct material bsdn;
	struct material geod;
	enum MATERIAL pending;
};


void
inventory_init(struct inventory * i)
{
	material_ctor(&i->ore, 0, 1);
	material_ctor(&i->clay, 0, 0);
	material_ctor(&i->bsdn, 0, 0);
	material_ctor(&i->geod, 0, 0);
	i->pending = -1;
}


int
inventory_cmp(struct inventory const * a, struct inventory const * b)
{
	if (a->geod.amount != b->geod.amount)
		return a->geod.amount - b->geod.amount;
	if (a->geod.robots != b->geod.robots)
		return a->geod.robots - b->geod.robots;
	if (a->bsdn.amount != b->bsdn.amount)
		return a->bsdn.amount - b->bsdn.amount;
	if (a->bsdn.robots != b->bsdn.robots)
		return a->bsdn.robots - b->bsdn.robots;
	if (a->clay.amount != b->clay.amount)
		return a->clay.amount - b->clay.amount;
	if (a->clay.robots != b->clay.robots)
		return a->clay.robots - b->clay.robots;
	if (a->ore.amount != b->ore.amount)
		return a->ore.amount - b->ore.amount;
	return a->ore.robots - b->ore.robots;
}


void
inventory_tick(struct inventory * i)
{
	material_tick(&i->ore, i->pending == ORE);
	material_tick(&i->clay, i->pending == CLAY);
	material_tick(&i->bsdn, i->pending == BSDN);
	material_tick(&i->geod, i->pending == GEOD);
	i->pending = -1;
}


// Try to build a robot out of material #m
int
inventory_build(struct inventory * i, struct blueprint const * b, enum MATERIAL m)
{
	switch (m) {
	case ORE:
		if (i->pending != -1
				|| i->ore.amount < b->ore_ore)
			return -1;
		i->ore.amount -= b->ore_ore;
		i->pending = ORE;
		break;

	case CLAY:
		if (i->pending != -1
				|| i->ore.amount < b->clay_ore)
			return -1;
		i->ore.amount -= b->clay_ore;
		i->pending = CLAY;
		break;

	case BSDN:
		if (i->pending != -1
				|| i->ore.amount < b->bsdn_ore
				|| i->clay.amount < b->bsdn_clay)
			return -1;
		i->ore.amount -= b->bsdn_ore;
		i->clay.amount -= b->bsdn_clay;
		i->pending = BSDN;
		break;

	case GEOD:
		if (i->pending != -1
				|| i->ore.amount < b->geod_ore
				|| i->bsdn.amount < b->geod_bsdn)
			return -1;
		i->ore.amount -= b->geod_ore;
		i->bsdn.amount -= b->geod_bsdn;
		i->pending = GEOD;
		break;

	default:
		return -1;
	}

	return 0;
}


// Most basic build algorithm. Build as many of the most important things that you
// can, and then as many of the next most important, and so on.
//
// Not optimal. But it helps get the structure of the program working.
void
inventory_build_basic(struct inventory * i, struct blueprint const * b, int remaining)
{
	int t;

	for (t = 0; t < remaining; ++t) {
		while (inventory_build(i, b, GEOD) == 0)
			;

		while (inventory_build(i, b, BSDN) == 0)
			;

		while (inventory_build(i, b, CLAY) == 0)
			;

		while (inventory_build(i, b, ORE) == 0)
			;

		inventory_tick(i);

		fprintf(stderr, "Blueprint %d tick %d, ore: %d/%d, clay %d/%d, bsdn %d/%d, geod %d/%d\n",
				b->id, t + 1,
				i->ore.amount, i->ore.robots,
				i->clay.amount, i->clay.robots,
				i->bsdn.amount, i->bsdn.robots,
				i->geod.amount, i->geod.robots);
	}
}


long exhaustive_iter;


void
inventory_build_exhaustive(struct inventory * i, struct blueprint const * b, int remaining)
{
	struct inventory best, test;

	if (!remaining)
		// No time to do anything!
		return;

	++exhaustive_iter;

	// Try doing nothing else this round.
	best = *i;
	inventory_tick(&best);
//	fprintf(stderr, "%d: doing nothing\n", remaining);
	inventory_build_exhaustive(&best, b, remaining - 1);

	test = *i;

	// Try building a geode robot, and check if that's better than doing nothing.
	if (inventory_build(&test, b, GEOD) == 0) {
//		fprintf(stderr, "%d: building a geod robot (%ld)\n", remaining, test.geod.amount);
		inventory_tick(&test);
		inventory_build_exhaustive(&test, b, remaining - 1);
		if (inventory_cmp(&test, &best) > 0)
			best = test;
		test = *i;
	}

	// Try building a obsidian robot, and checking if that's better than anything else
	if (i->bsdn.robots < b->max_bsdn
			&& inventory_build(&test, b, BSDN) == 0)
	{
//		fprintf(stderr, "%d: building a bsdn robot (%ld)\n", remaining, test.bsdn.amount);
		inventory_tick(&test);
		inventory_build_exhaustive(&test, b, remaining - 1);
		if (inventory_cmp(&test, &best) > 0)
			best = test;
		test = *i;
	}

	// Try building a clay robot, and checking if that's better than anything else
	if (i->clay.robots < b->max_clay
			&& inventory_build(&test, b, CLAY) == 0)
	{
//		fprintf(stderr, "%d: building a clay robot (%ld)\n", remaining, test.clay.amount);
		inventory_tick(&test);
		inventory_build_exhaustive(&test, b, remaining - 1);
		if (inventory_cmp(&test, &best) > 0)
			best = test;
		test = *i;
	}

	// Try building a ore robot, and checking if that's better than anything else
	if (i->ore.robots < b->max_ore
			&& inventory_build(&test, b, ORE) == 0)
	{
//		fprintf(stderr, "%d: building a ore robot (%ld)\n", remaining, test.ore.amount);
		inventory_tick(&test);
		inventory_build_exhaustive(&test, b, remaining - 1);
		if (inventory_cmp(&test, &best) > 0)
			best = test;
		test = *i;
	}

	*i = best;
}


int
main(int argc, char ** argv)
{
	int rounds = 24;
	char const * build = "basic";
	int i;
	regex_t reblueprint;
	char buf[BUFSIZ];

	while ((i = getopt(argc, argv, "b:r:")) != -1)
	{
		switch (i) {
		case 'b':
			build = optarg;
			break;

		case 'r':
			rounds = atoi(optarg);
			break;

		default:
			return -1;
		}
	}

	if (regcomp(&reblueprint, "Blueprint ([[:digit:]]+):"
				" Each ore robot costs ([[:digit:]]+) ore."
				" Each clay robot costs ([[:digit:]]+) ore."
				" Each obsidian robot costs ([[:digit:]]+) ore and ([[:digit:]]+) clay."
				" Each geode robot costs ([[:digit:]]+) ore and ([[:digit:]]+) obsidian.",
				REG_EXTENDED) != 0)
	{
		fprintf(stderr, "Bad regex\n");
		return -1;
	}

	while (fgets(buf, sizeof(buf), stdin)) {
		regmatch_t rematch[8];
		struct blueprint b;
		struct inventory i;

		if (regexec(&reblueprint, buf, arrlen(rematch), rematch, 0) != 0) {
			fprintf(stderr, "Unexpected blueprint in %s\n", buf);
			continue;
		}

		blueprint_ctor(&b,
				atoi(buf + rematch[1].rm_so),
				atoi(buf + rematch[2].rm_so),
				atoi(buf + rematch[3].rm_so),
				atoi(buf + rematch[4].rm_so),
				atoi(buf + rematch[5].rm_so),
				atoi(buf + rematch[6].rm_so),
				atoi(buf + rematch[7].rm_so));

		inventory_init(&i);

		if (strcmp(build, "basic") == 0) {
			inventory_build_basic(&i, &b, rounds);
		}
		else if (strcmp(build, "exhaustive") == 0) {
			exhaustive_iter = 0;
			inventory_build_exhaustive(&i, &b, rounds);
			fprintf(stdout, "Blueprint %d, iterations %ld, ore %d/%d, clay %d/%d, bsdn %d/%d, geod %d/%d\n",
				b.id, exhaustive_iter,
				i.ore.amount, i.ore.robots,
				i.clay.amount, i.clay.robots,
				i.bsdn.amount, i.bsdn.robots,
				i.geod.amount, i.geod.robots);
		}
		else {
			fprintf(stderr, "Unknown build strategy: %s\n", build);
			regfree(&reblueprint);
			return -1;
		}

		printf("Blueprint %d geodes = %d\n", b.id, i.geod.amount);
	}

	regfree(&reblueprint);

	return 0;
}