path: root/11.c

#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>


enum worry_op {
	WO_NONE,
	WO_ADD,
	WO_MUL,
	WO_SQR,
};


struct monkey {
	unsigned long * items;
	int nitems;
	enum worry_op wo;
	int wparam;
	int test_div;
	int test_true;
	int test_false;
	long inspections;
};


void
monkey_init(struct monkey * m)
{
	m->items = NULL;
	m->nitems = 0;
	m->wo = WO_NONE;
	m->wparam = 0;
	m->test_div = 0;
	m->test_true = 0;
	m->test_false = 0;
	m->inspections = 0;
}


void
monkey_dtor(struct monkey * m)
{
	free(m->items);
}


int
monkey_isvalid(struct monkey const * m, int max)
{
	return m->wo != WO_NONE
		&& m->test_div != 0
		&& m->test_true >= 0 && m->test_true < max
		&& m->test_false >= 0 && m->test_false < max;
}


int
monkey_additem(struct monkey * m, int worry)
{
	void * p;

	++m->nitems;
	p = realloc(m->items, m->nitems * sizeof(unsigned long));
	if (!p)
		return 0;
	m->items = p;
	m->items[m->nitems - 1] = worry;
	return 1;
}


void
monkey_dump(struct monkey const * m, int n)
{
	unsigned long * item;

	fprintf(stderr, "Monkey %d: %d/%d/%d/%d/%d/%ld: ",
			n, m->wo, m->wparam, m->test_div, m->test_true, m->test_false, m->inspections);
	for (item = m->items; item < m->items + m->nitems; ++item) {
		fprintf(stderr, "%s%lu", item == m->items ? "" : ", ", *item);
	}
	fprintf(stderr, "\n");
}


int
main(int argc, char ** argv)
{
	char buf[BUFSIZ];
	struct monkey * monkeys = NULL, * m = NULL;
	int nmonkeys = 0;
	long i, j;
	int calming = 3, rounds = 20;

	while ((i = getopt(argc, argv, "p:c:r:")) != -1) {
		switch (i) {
		case 'p':
			switch (atol(optarg)) {
			case 1: calming = 3; rounds = 20; break;
			case 2: calming = 1; rounds = 10000; break;
			default:
				fprintf(stderr, "Unexpected part %d\n", atoi(optarg));
				return -1;
			}
			break;

		case 'c':
			calming = atoi(optarg);
			if (calming == 0) {
				fprintf(stderr, "Unexpected calming factor %d\n", calming);
				return -1;
			}
			break;

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

		default:
			return -1;
		}
	}

	// Read monkey data
	while (fgets(buf, sizeof(buf), stdin)) {
		if (buf[0] == '\n') {
			// Ignore blank line
		}
		else if (strncmp(buf, "Monkey ", 7) == 0 && isdigit(buf[7])) {
			void * p;

			++nmonkeys;

			if ((i = atoi(buf + 7)) != nmonkeys - 1) {
				fprintf(stderr, "Bad monkey %ld/%d!\n", i, nmonkeys);
				free(monkeys);
				return -1;
			}
			p = realloc(monkeys, nmonkeys * sizeof(struct monkey));
			if (!p) {
				fprintf(stderr, "realloc(%zd) fail\n", nmonkeys * sizeof(struct monkey));
				free(monkeys);
				return -1;
			}
			monkeys = p;
			m = monkeys + nmonkeys - 1;
			monkey_init(m);
		}
		else if (strncmp(buf, "  Starting items: ", 18) == 0 && isdigit(buf[18])) {
			char * cur, * next;
			int worry;

			cur = buf + 18;
			worry = strtol(cur, &next, 10);
			while (next != cur) {
				monkey_additem(m, worry);
				cur = next + 1;
				worry = strtol(cur, &next, 10);
			}
		}
		else if (strncmp(buf, "  Operation: new = old ", 23) == 0) {
			switch (buf[23]) {
			case '+': m->wo = WO_ADD; break;
			case '*': m->wo = WO_MUL; break;
			default:
				  fprintf(stderr, "Unexpected op %c\n", buf[23]);
				  free(monkeys);
				  return -1;
			}
			if (strncmp(buf + 25, "old", 3) == 0 && m->wo == WO_MUL) {
				m->wo = WO_SQR;
			}
			else {
				m->wparam = atoi(buf + 25);
			}
		}
		else if (strncmp(buf, "  Test: divisible by ", 21) == 0 && isdigit(buf[21])) {
			m->test_div = atoi(buf + 21);
		}
		else if (strncmp(buf, "    If true: throw to monkey ", 29) == 0 && isdigit(buf[29])) {
			m->test_true = atoi(buf + 29);
		}
		else if (strncmp(buf, "    If false: throw to monkey ", 30) == 0 && isdigit(buf[30])) {
			m->test_false = atoi(buf + 30);
		}
		else {
			fprintf(stderr, "Unexpected monkey: %s\n", buf);
			free(monkeys);
			return -1;
		}
	}

	// Check monkeys are valid
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
#if 0
		monkey_dump(m, m - monkeys);
#endif
		if (!monkey_isvalid(m, nmonkeys)) {
			fprintf(stderr, "Bad monkey %d\n", (int) (m - monkeys));
			monkey_dump(m, m - monkeys);
			free(monkeys);
			return -1;
		}
	}

	// Perform monkey inspection rounds
	for (i = 0; i < rounds; ++i) {
		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
			unsigned long * item;

			for (item = m->items; item < m->items + m->nitems; ++item) {
				int catcher;

				switch (m->wo) {
				case WO_NONE:
					break; /* shouldn't happen */
				case WO_ADD:
					if (*item > ULONG_MAX - m->wparam)
						fprintf(stderr, "%ld/%d/%d: Overflow: %lu > %lu - %d\n",
								i, (int) (monkeys - m), (int) (item - m->items),
								*item, ULONG_MAX, m->wparam);
					*item += m->wparam;
					break;
				case WO_MUL:
					if (*item >= ULONG_MAX / m->wparam)
						fprintf(stderr, "%ld/%d/%d: Overflow: %lu >= %lu / %d\n",
								i, (int) (monkeys - m), (int) (item - m->items),
								*item, ULONG_MAX, m->wparam);
					*item *= m->wparam;
					break;
				case WO_SQR:
					if (*item >= ULONG_MAX / *item)
						fprintf(stderr, "%ld/%d/%d: Overflow: %lu >= %lu / %lu\n",
								i, (int) (monkeys - m), (int) (item - m->items),
								*item, ULONG_MAX, *item);
					*item *= *item;
					break;
				}
				*item /= calming;

				catcher = *item % m->test_div ? m->test_false : m->test_true;
				monkey_additem(monkeys + catcher, *item);

				++m->inspections;
			}
			m->nitems = 0;
		}

#if 0
		for (m = monkeys; m < monkeys + nmonkeys; ++m) {
			monkey_dump(m, m - monkeys);
		}
#endif
	}

	// Calculate monkey business
	i = j = 0;
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
		if (m->inspections > i) {
			j = i;
			i = m->inspections;
		}
		else if (m->inspections > j) {
			j = m->inspections;
		}
	}
	printf("Monkey business: %ld (%ld * %ld)\n", i * j, i, j);

	// Done.
	for (m = monkeys; m < monkeys + nmonkeys; ++m) {
		monkey_dtor(m);
	}
	free(monkeys);

	return 0;
}