diff options
Diffstat (limited to '11.c')
| -rw-r--r-- | 11.c | 230 |
1 files changed, 230 insertions, 0 deletions
@@ -0,0 +1,230 @@ + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +enum worry_op { + WO_NONE, + WO_ADD, + WO_MUL, + WO_SQR, +}; + + +struct monkey { + int * items; + int nitems; + enum worry_op wo; + int wparam; + int test_div; + int test_true; + int test_false; + int 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(int)); + if (!p) + return 0; + m->items = p; + m->items[m->nitems - 1] = worry; + return 1; +} + + +void +monkey_dump(struct monkey const * m, int n) +{ + int * i; + + fprintf(stderr, "Monkey %d: %d/%d/%d/%d/%d/%d: ", + n, m->wo, m->wparam, m->test_div, m->test_true, m->test_false, m->inspections); + for (i = m->items; i < m->items + m->nitems; ++i) { + fprintf(stderr, "%s%d", i == m->items ? "" : ", ", *i); + } + fprintf(stderr, "\n"); +} + + +int +main() +{ + char buf[BUFSIZ]; + struct monkey * monkeys = NULL, * m = NULL; + int nmonkeys = 0; + int i, j; + + // 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 %d/%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 < 20; ++i) { + for (m = monkeys; m < monkeys + nmonkeys; ++m) { + int * 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: *item += m->wparam; break; + case WO_MUL: *item *= m->wparam; break; + case WO_SQR: *item *= *item; break; + } + *item /= 3; + + 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: %d (%d * %d)\n", i * j, i, j); + + // Done. + for (m = monkeys; m < monkeys + nmonkeys; ++m) { + monkey_dtor(m); + } + free(monkeys); + + return 0; +} + |