day18.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
#include <math.h>
#include "../lib.h"

typedef enum {
        SHUT,
        OPEN,
        NUMB
} node_type_t;

typedef struct {
        int num;
        node_type_t type;
} node_t;

typedef struct {
        node_t nodes[1 << 14];
        int node_count;
} nester_t;

nester_t parse(char *input, char **endptr) {
        nester_t result = { 0 };
        while (*input) {
                if (*input == '[') {
                        result.nodes[result.node_count++] = (node_t) { 0, OPEN };
                        input += 1;
                }
                else if (*input == ']') {
                        result.nodes[result.node_count++] = (node_t) { 0, SHUT };
                        input += 1;
                }
                else if (*input >= '0' && *input <= '9') {
                        char *end = NULL;
                        long num = strtol(input, &end, 10);
                        input = end;
                        result.nodes[result.node_count++] = (node_t) { num, NUMB };
                }
                else if (*input == ',') {
                        input += 1;
                }
                else if (*input == '\n') {
                        break;
                }
                else {
                        fprintf(stderr, "Invalid character `%c'", *input);
                        exit(-1);
                }
        }
        
        *endptr = input;
        return result;
}

bool explode(nester_t *nested) {
        nester_t result = { 0 };
        node_t *leftnum = NULL; 
        int rightadd = 0;
        bool done = false;
        int depth = 0;

        for (int i = 0; i < nested->node_count; i += 1) {
                if (nested->nodes[i].type == OPEN) {
                        depth += 1;
                        if (!done && nested->nodes[i+1].type == NUMB && nested->nodes[i+2].type == NUMB && nested->nodes[i+3].type == SHUT && depth > 4) {
                                if (leftnum) {
                                        leftnum->num += nested->nodes[i+1].num;
                                }
                                rightadd = nested->nodes[i+2].num;
                                done = true;
                                result.nodes[result.node_count++] = (node_t) { 0, NUMB };
                                i += 3;
                        }
                        else {
                                result.nodes[result.node_count++] = (node_t) { 0, OPEN };
                        }
                }
                else if (nested->nodes[i].type == SHUT) {
                        depth -= 1;
                        result.nodes[result.node_count++] = (node_t) { 0, SHUT };
                }
                else {
                        result.nodes[result.node_count++] = (node_t) { nested->nodes[i].num + rightadd, NUMB };
                        leftnum = &result.nodes[result.node_count-1];
                        rightadd = 0;
                }
        }
        *nested = result;
        return done;
}

bool split(nester_t *nested) {
        nester_t result = { 0 };
        bool done = false;

        for (int i = 0; i < nested->node_count; i += 1) {
                if (nested->nodes[i].num > 9 && !done) {
                        int left = floor(nested->nodes[i].num/2.0);
                        int right = ceil(nested->nodes[i].num/2.0);
                        result.nodes[result.node_count++] = (node_t) { 0, OPEN };
                        result.nodes[result.node_count++] = (node_t) { left, NUMB };
                        result.nodes[result.node_count++] = (node_t) { right, NUMB };
                        result.nodes[result.node_count++] = (node_t) { 0, SHUT };
                        done = true;
                }
                else {
                        result.nodes[result.node_count++] = nested->nodes[i];
                }
        }
        
        *nested = result;
        return done;
}

nester_t add(nester_t *a, nester_t *b) {
        nester_t result = { 0 };
        result.nodes[result.node_count++] = (node_t) { 0, OPEN };

        for (int i = 0; i < a->node_count; i += 1) {
                result.nodes[result.node_count++] = a->nodes[i];
        }

        for (int i = 0; i < b->node_count; i += 1) {
                result.nodes[result.node_count++] = b->nodes[i];
        }
        
        result.nodes[result.node_count++] = (node_t) { 0, SHUT };
        
        return result;
}

int num(nester_t *nester, int *it) {
        int a = 0;

        if (nester->nodes[*it].type == OPEN) {
                *it += 1;
                a += num(nester, it)*3;
                *it += 1;
        }
        else {
                a += nester->nodes[*it].num*3;
                *it += 1;
        }
        
        if (nester->nodes[*it].type == OPEN) {
                *it += 1;
                a += num(nester, it)*2;
                *it += 1;
        }
        else {
                a += nester->nodes[*it].num*2;
                *it += 1;
        }
        
        return a;
}

void printnester(nester_t *nester) {
        int depth = 0;
        for (int i = 0; i < nester->node_count; i += 1) {
                if (nester->nodes[i].type == OPEN) {
                        depth += 1;
                        if (depth > 4) {
                                printf("\x1b[31m");
                        }
                        printf("[");
                }
                if (nester->nodes[i].type == SHUT) {
                        printf("]");
                        if (depth > 4) {
                                printf("\x1b[0m");
                        }
                        depth -= 1;
                        if (nester->nodes[i+1].type != SHUT) 
                                printf(", ");
                }
                if (nester->nodes[i].type == NUMB) {
                        printf("%d", nester->nodes[i].num);
                        if (nester->nodes[i+1].type != SHUT) 
                                printf(", ");
                }
        }
        printf("\n");
}

int main() {
        char *input = read_file("./day18/test_input.txt");
        char *src = input;
        nester_t *parsed = malloc(sizeof(nester_t) * 100);
        int nester_count = 0;
        
        while (*input) {
                char *endptr = 0;
                parsed[nester_count++] = parse(input, &endptr);
                input = endptr;
                while (isspace(*input)) input++;
        }
        
        nester_t x = parsed[0];
        for (int i = 1; i < nester_count; i += 1) {
                x = add(&x, &parsed[i]);
                while (explode(&x) || split(&x));
        }
        
        
        int it = 1;
        printf("Part 1: %d\n", num(&x, &it));
        
        int max = 0;
        for (int i = 0; i < nester_count; i += 1) {
                for (int j = 0; j < nester_count; j += 1) {
                        if (i == j) continue;
                        // < 4686
                        nester_t compound = add(&parsed[i], &parsed[j]);
                        while (explode(&compound) || split(&compound));
                                        
                        int iter = 1;
                        int n = num(&compound, &iter);
                        
                        if (n > max) {
                                max = n;
                        }
                }
        }
        
        printf("Part 2: %d\n", max); 
        
        free(src);
        free(parsed);
}