commit 6998e1ac8e3a02cbcbd1ab5b2995c02cb3877c7f
parent ebc174add5feef05162d239ae56e69392aa91edf
Author: aabacchus <ben@bvnf.space>
Date: Mon, 12 Dec 2022 11:59:25 +0000
22.11 in C
Diffstat:
| A | 2022/11/a.c | | | 237 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/11/example | | | 27 | +++++++++++++++++++++++++++ |
| A | 2022/11/input | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 319 insertions(+), 0 deletions(-)
diff --git a/2022/11/a.c b/2022/11/a.c
@@ -0,0 +1,237 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define NUM_MONKEYS 8
+#define ROUNDS 10000
+
+struct monkey {
+ size_t n;
+ long *items;
+ int test;
+ int true_to;
+ int false_to;
+ char op_op; /* like '*' or '+' */
+ int op_rhs; /* 0 means self */
+ long inspected;
+};
+
+void
+push_item(struct monkey *m, long item) {
+ if (m == NULL)
+ return;
+
+ long *tmp = realloc(m->items, sizeof (long) * (m->n + 1));
+ if (tmp == NULL) {
+ perror("realloc");
+ exit(1);
+ }
+
+ tmp[m->n] = item;
+ m->items = tmp;
+ m->n++;
+}
+
+long
+pop_item(struct monkey *m) {
+ if (m->n < 1) {
+ fprintf(stderr, "no items to pop!\n");
+ exit(1);
+ }
+ long d = m->items[0];
+
+ for (int i = 1; i < m->n; i++) {
+ m->items[i - 1] = m->items[i];
+ }
+ m->n--;
+
+ return d;
+}
+
+int
+inspect(struct monkey *m, long *n, long lcm) {
+ long new;
+ long old = pop_item(m);
+ long rhs = m->op_rhs;
+ if (rhs == 0)
+ rhs = old;
+
+ if (m->op_op == '+')
+ new = old + rhs;
+ else if (m->op_op == '*')
+ new = old * rhs;
+ else {
+ fprintf(stderr, "unknown operation '%c'\n", m->op_op);
+ return 0;
+ }
+
+ m->inspected++;
+
+ /* UNCOMMENT FOR PART A */
+ /* new /= 3; */
+ new = new % lcm;
+
+ *n = new;
+ if (new < 0) {
+ fprintf(stderr, "! %ld %c %ld -> %ld\n", old, m->op_op, rhs, new);
+ }
+
+ if (new % m->test == 0)
+ return 1;
+ else
+ return -1;
+}
+
+int
+main(int argc, char **argv) {
+ char *buf = NULL;
+ size_t buflen = 0;
+ ssize_t n;
+ FILE *f;
+ struct monkey monkeys[NUM_MONKEYS] = {0};
+
+ if (argc != 2) {
+ fprintf(stderr, "usage: %s input\n", argv[0]);
+ return 1;
+ }
+
+ f = fopen(argv[1], "r");
+ if (f == NULL) {
+ perror(argv[1]);
+ return 1;
+ }
+
+ int mn = -1;
+ long d;
+ char *s = NULL;
+ while ((n = getline(&buf, &buflen, f)) != -1) {
+ if (buf[n - 1] == '\n') {
+ buf[n - 1] = '\0';
+ n--;
+ }
+ if (n == 0)
+ continue;
+ if (buf[0] == 'M') {
+ /* next monkey init. not necessary to parse number since they are in order. */
+ mn++;
+ assert(mn < NUM_MONKEYS);
+ continue;
+ }
+ switch (buf[2]) {
+ case 'S':
+ /* starting items */
+ s = buf+17;
+ while (s != NULL) {
+ s++;
+ if (sscanf(s, "%ld", &d) != 1) {
+ perror("sscanf");
+ return 1;
+ }
+ push_item(&monkeys[mn], d);
+
+ s = strchr(s, ',');
+ }
+ break;
+ case 'O':
+ /* operation */
+ assert(n > 25);
+ monkeys[mn].op_op = buf[23];
+ if (buf[25] == 'o') {
+ monkeys[mn].op_rhs = 0; /* old OP old */
+ } else {
+ if (sscanf(buf+25, "%ld", &d) != 1) {
+ perror("sscanf");
+ return 1;
+ }
+ monkeys[mn].op_rhs = d;
+ }
+ break;
+ case 'T':
+ /* test */
+ if (sscanf(buf+2, "Test: divisible by %ld", &d) != 1) {
+ perror("sscanf");
+ return 1;
+ }
+ monkeys[mn].test = d;
+ break;
+ default:
+ if (buf[2] == ' ') {
+ assert(n > 29);
+ if (buf[7] == 't') {
+ /* true */
+ /* don't sscanf because it's a single digit (NUM_MONKEYS < 10) */
+ monkeys[mn].true_to = buf[29] - '0';
+ } else {
+ /* false */
+ monkeys[mn].false_to = buf[30] - '0';
+ }
+ }
+ break;
+ }
+ }
+
+ free(buf);
+ fclose(f);
+
+ /* I cheated and looked up what to do for part 2. I modulus the new worry
+ * levels against the LCM of all the divisors - this way, the remainders
+ * will all be the same, but the numbers don't get stupidly big.
+ */
+
+ long lcm = 1;
+ for (mn = 0; mn < NUM_MONKEYS; mn++)
+ lcm *= monkeys[mn].test;
+
+ for (int round = 0; round < ROUNDS; round++) {
+ for (mn = 0; mn < NUM_MONKEYS; mn++) {
+ size_t todo = monkeys[mn].n; /* store because it decreases for each inspect() */
+ for (size_t i = 0; i < todo; i++) {
+ long new = 0;
+ int test;
+ test = inspect(&monkeys[mn], &new, lcm);
+ if (test == 1) {
+ /* true */
+ push_item(&monkeys[monkeys[mn].true_to], new);
+ } else if (test == -1) {
+ /* false */
+ push_item(&monkeys[monkeys[mn].false_to], new);
+ } else {
+ /* error */
+ exit(1);
+ }
+ }
+ }
+ /*
+ fprintf(stderr, "After round %d:\n", round);
+ for (int i = 0; i < NUM_MONKEYS; i++) {
+ fprintf(stderr, "Monkey %d:", i);
+ for (size_t j = 0; j < monkeys[i].n; j++) {
+ fprintf(stderr, " %ld", monkeys[i].items[j]);
+ }
+ fprintf(stderr, "\n");
+ }
+ */
+ }
+
+ long max1, max2;
+ max1 = max2 = 0;
+ for (int i = 0; i < NUM_MONKEYS; i++) {
+ long me = monkeys[i].inspected;
+ if (me > max1) {
+ max2 = max1;
+ max1 = me;
+ } else if (me > max2) {
+ max2 = me;
+ }
+ }
+
+ printf("%ld\n", max1 * max2);
+
+ for (int i = 0; i < NUM_MONKEYS; i++) {
+ printf("%d inspected %ld\n", i, monkeys[i].inspected);
+ free(monkeys[i].items);
+ }
+
+ return 0;
+}
diff --git a/2022/11/example b/2022/11/example
@@ -0,0 +1,27 @@
+Monkey 0:
+ Starting items: 79, 98
+ Operation: new = old * 19
+ Test: divisible by 23
+ If true: throw to monkey 2
+ If false: throw to monkey 3
+
+Monkey 1:
+ Starting items: 54, 65, 75, 74
+ Operation: new = old + 6
+ Test: divisible by 19
+ If true: throw to monkey 2
+ If false: throw to monkey 0
+
+Monkey 2:
+ Starting items: 79, 60, 97
+ Operation: new = old * old
+ Test: divisible by 13
+ If true: throw to monkey 1
+ If false: throw to monkey 3
+
+Monkey 3:
+ Starting items: 74
+ Operation: new = old + 3
+ Test: divisible by 17
+ If true: throw to monkey 0
+ If false: throw to monkey 1
diff --git a/2022/11/input b/2022/11/input
@@ -0,0 +1,55 @@
+Monkey 0:
+ Starting items: 52, 78, 79, 63, 51, 94
+ Operation: new = old * 13
+ Test: divisible by 5
+ If true: throw to monkey 1
+ If false: throw to monkey 6
+
+Monkey 1:
+ Starting items: 77, 94, 70, 83, 53
+ Operation: new = old + 3
+ Test: divisible by 7
+ If true: throw to monkey 5
+ If false: throw to monkey 3
+
+Monkey 2:
+ Starting items: 98, 50, 76
+ Operation: new = old * old
+ Test: divisible by 13
+ If true: throw to monkey 0
+ If false: throw to monkey 6
+
+Monkey 3:
+ Starting items: 92, 91, 61, 75, 99, 63, 84, 69
+ Operation: new = old + 5
+ Test: divisible by 11
+ If true: throw to monkey 5
+ If false: throw to monkey 7
+
+Monkey 4:
+ Starting items: 51, 53, 83, 52
+ Operation: new = old + 7
+ Test: divisible by 3
+ If true: throw to monkey 2
+ If false: throw to monkey 0
+
+Monkey 5:
+ Starting items: 76, 76
+ Operation: new = old + 4
+ Test: divisible by 2
+ If true: throw to monkey 4
+ If false: throw to monkey 7
+
+Monkey 6:
+ Starting items: 75, 59, 93, 69, 76, 96, 65
+ Operation: new = old * 19
+ Test: divisible by 17
+ If true: throw to monkey 1
+ If false: throw to monkey 3
+
+Monkey 7:
+ Starting items: 89
+ Operation: new = old + 2
+ Test: divisible by 19
+ If true: throw to monkey 2
+ If false: throw to monkey 4
