Created
December 23, 2020 18:04
-
-
Save whiter4bbit/4fa299226f628a6075714cbfb9fa6774 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment