day23.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

typedef struct Circle {
    struct Node **refs;
    struct Node *head;
    int len;
} Circle;

void init_circle(Circle **c, int *values, int len) {
    *c = (Circle*) malloc(sizeof(Circle));

    (*c)->refs = (Node**) malloc(sizeof(Node*) * (len + 1));
    (*c)->len = len + 1;

    for (int i = 0; i < len; i++) {
        (*c)->refs[values[i]] = (Node*) malloc(sizeof(Node));
        (*c)->refs[values[i]]->value = values[i];
    }

    (*c)->head = (*c)->refs[values[0]];

    Node *tail = (*c)->head;
    for (int i = 1; i < len; i++) {
        tail->next = (*c)->refs[values[i]];
        tail = tail->next;
    }

    tail->next = (*c)->head;
}

typedef struct Bulk {
    Node *head;
    Node *tail;
} Bulk;

void circle_remove_bulk_after(Circle *c, Node *after, Bulk *bulk) {
    Node *first = after->next;
    Node *second = first->next;
    Node *third = second->next;

    bulk->head = first;
    bulk->tail = third;

    after->next = third->next;

    c->refs[first->value] = NULL;
    c->refs[second->value] = NULL;
    c->refs[third->value] = NULL;
}

void circle_insert_bulk_after(Circle *c, Node *after, Bulk *bulk) {
    bulk->tail->next = after->next;
    after->next = bulk->head;

    c->refs[bulk->head->value] = bulk->head;
    c->refs[bulk->head->next->value] = bulk->head->next;
    c->refs[bulk->head->next->next->value] = bulk->head->next->next;
}

Node *circle_find_destination(Circle *c) {
    int value = c->head->value;
    while (1) {
        if (value == 1) {
            value = c->len - 1;
        } else {
            value -= 1;
        }

        if (c->refs[value] != NULL)
            return c->refs[value];
    }
}

void circle_shift_head(Circle *c) {
    c->head = c->head->next;
}

void circle_print_from(Circle *c, Node *from) {
    Node *cur = from;
    while (1) {
        printf("%d ", cur->value);
        if (cur->next == from) {
            break;
        }
        cur = cur->next;
    }
    printf("\n");
}

void play(Circle *c, int times) {
    Bulk bulk;

    for (int i = 0; i < times; i++) {
        circle_remove_bulk_after(c, c->head, &bulk);
        
        Node *dest = circle_find_destination(c);

        circle_insert_bulk_after(c, dest, &bulk);

        circle_shift_head(c);
    }
}

int input[] = {7, 8, 9, 4, 6, 5, 1, 2, 3};

void solve_p1() {
    Circle *c;
    init_circle(&c, input, 9);

    play(c, 100);

    printf("day 23/1: ");
    circle_print_from(c, c->refs[1]);
}

void solve_p2() {
    int *extended_input = (int*) malloc(1000000 * sizeof(int));
    memcpy(extended_input, input, sizeof(int) * 9);

    for (int i = 9; i < 1000000; i++) {
        extended_input[i] = i + 1;
    }

    Circle *c;    
    init_circle(&c, extended_input, 1000000);

    play(c, 10000000);

    long long first = c->refs[1]->next->value;
    long long second = c->refs[1]->next->next->value;

    printf("day 23/2: %lld\n", (first * second));
}


int main(int argc, char** argv) {
    solve_p1();
    solve_p2();
    
    return 0;
}