path: root/19.c

#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);
	}
}


// Exhastive(ish) build strategy
//
// Try all^Wmost combinations of building different robots at different times
//
// We actually cheat and only try building on certain conditions:
//
//	if (i->MATERIAL.robots < b->max_MATERIAL)
//
//		max_MATERIAL is the maximum amount of MATERIAL it takes to build
//		any robot. Given that we can only build one robot per round, we
//		can never spend more than max_MATERIAL units per round, so we
//		never need more than max_MATERIAL robots of that type.
//
//	if (i->MATERIAL.amount < 2 * b->max_MATERIAL)
//
//		If we already have a lot of MATERIAL, we probably don't need
//		another robot to collect that type right now.
//
//	if (i->MATERIAL.amount < 2 * b->ROBOT_MATERIAL)
//
//		If we could have built a robot of a certain type some time ago,
//		but didn't, then either a) this is a good build combination and
//		we don't need it, or b) this is a bad build combination and we
//		did, but there isn't much point in going further down that
//		rabbit hole now.
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;

	best = *i;
	test = *i;

	// If there are some robots we can't build yet, try doing nothing this round.
	if (i->ore.amount < b->max_ore
			|| i->clay.amount < b->max_clay
			|| i->bsdn.amount < b->max_bsdn)
	{
		inventory_tick(&test);
//		fprintf(stderr, "%d: doing nothing\n", remaining);
		inventory_build_exhaustive(&test, b, remaining - 1);
		if (inventory_cmp(&test, &best) > 0)
			best = test;
		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
			&& i->bsdn.amount < 2 * b->max_bsdn
			&& (i->clay.amount < 2 * b->bsdn_clay
				|| i->ore.amount < 2 * b->bsdn_ore)
			&& 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
			&& i->clay.amount < 2 * b->max_clay
			&& i->ore.amount < 2 * b->clay_ore
			&& remaining > 5
			&& 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
			&& i->ore.amount < 2 * b->max_ore
			&& i->ore.amount < 2 * b->ore_ore
			&& remaining > 10
			&& 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 debug = 0, rounds = 24;
	char const * build = "exhaustive", * output = "quality";
	int quality = 0, i;
	unsigned long product = 1;
	regex_t reblueprint;
	char buf[BUFSIZ];

	while ((i = getopt(argc, argv, "dp:b:o:r:")) != -1) {
		switch (i) {
		case 'd':
			debug = 1;
			break;

		case 'p':
			switch (atoi(optarg)) {
			case 1:
				rounds = 24;
				output = "quality";
				break;

			case 2:
				rounds = 32;
				output = "product";
				break;

			default:
				fprintf(stderr, "Unexpected puzzle part: %s\n", optarg);
				return -1;
			}
			break;

		case 'b':
			build = optarg;
			break;

		case 'o':
			output = 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) {
			inventory_build_exhaustive(&i, &b, rounds);
		}
		else {
			fprintf(stderr, "Unknown build strategy: %s\n", build);
			regfree(&reblueprint);
			return -1;
		}

		quality += b.id * i.geod.amount;
		product *= i.geod.amount;

		if (debug)
			fprintf(stderr, "Blueprint %d, ore %d/%d, clay %d/%d, bsdn %d/%d, geod %d/%d\n",
				b.id,
				i.ore.robots, i.ore.amount,
				i.clay.robots, i.clay.amount,
				i.bsdn.robots, i.bsdn.amount,
				i.geod.robots, i.geod.amount);
	}

	if (strcmp(output, "quality") == 0) {
		printf("Total quality level = %d\n", quality);
	}
	else if (strcmp(output, "product") == 0) {
		printf("Total geode product = %lu\n", product);
	}
	else {
		fprintf(stderr, "Unknown output type: %s\n", output);
		regfree(&reblueprint);
		return -1;
	}

	regfree(&reblueprint);

	return 0;
}