advent-of-code

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