Advent of Code Day 18

aoc.c

#include <fcntl.h>
#include <unistd.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

typedef struct Element
{
    int regular;
    struct Element *children[2];
} Element;

bool isNumber(char c)
{
    return c > 47 && c < 58;
}

void freeTree(Element *cur)
{
    if (cur->children[0] != NULL)
    {
        freeTree(cur->children[0]);
        freeTree(cur->children[1]);
        free(cur->children[0]);
        free(cur->children[1]);
    }
}

Element *copyTree(Element *cur)
{
    Element *newTree = malloc(sizeof(Element));
    if (newTree == NULL)
    {
        puts("malloc failed");
        return NULL;
    }
    newTree->regular = cur->regular;
    if (cur->children[0] != NULL)
    {
        newTree->children[0] = copyTree(cur->children[0]);
        newTree->children[1] = copyTree(cur->children[1]);
    }
    else
    {
        newTree->children[0] = NULL;
        newTree->children[1] = NULL;
    }
    return newTree;
}

bool parseInput(char **ptr, Element *cur)
{
    if (isNumber(**ptr))
    {
        cur->regular = **ptr - 48;
        cur->children[0] = NULL;
        cur->children[1] = NULL;
        (*ptr)++;
        return true;
    }
    else if (**ptr == '[')
    {
        cur->children[0] = malloc(sizeof(Element));
        cur->children[1] = malloc(sizeof(Element));
        if (cur->children[0] == NULL || cur->children[1] == NULL)
        {
            puts("malloc failed");
            return false;
        }
        (*ptr)++;
        if (!parseInput(ptr, cur->children[0]))
        {
            return false;
        }
        (*ptr)++;
        if (!parseInput(ptr, cur->children[1]))
        {
            return false;
        }
        (*ptr)++;
        return true;
    }
    else
    {
        printf("Unexpected character: %c\n", **ptr);
        return false;
    }
}

void printTree(Element *cur)
{
    if (cur->children[0] == NULL)
    {
        printf("%d", cur->regular);
    }
    else
    {
        putchar('[');
        printTree(cur->children[0]);
        putchar(',');
        printTree(cur->children[1]);
        putchar(']');
    }
}

Element *add(Element *e1, Element *e2)
{
    Element *result = malloc(sizeof(Element));
    if (result == NULL)
    {
        puts("malloc failed");
        return NULL;
    }
    result->children[0] = e1;
    result->children[1] = e2;
    return result;
}

bool findLeft(Element *cur, Element *explode, Element **prev, bool *found)
{
    if (cur == explode)
    {
        *found = true;
    }
    if (*found)
    {
        return true;
    }
    if (cur->children[0] == NULL)
    {
        *prev = cur;
    }
    if (cur->children[0] != NULL)
    {
        if (findLeft(cur->children[0], explode, prev, found))
        {
            return true;
        }
        if (findLeft(cur->children[1], explode, prev, found))
        {
            return true;
        }
    }
    return false;
}

bool explodeRight(Element *cur, Element *explode, bool *found)
{
    if (cur == explode)
    {
        *found = true;
    }
    else if (*found && cur->children[0] == NULL)
    {
        cur->regular += explode->regular;
        return true;
    }
    if (cur->children[0] != NULL)
    {
        if (explodeRight(cur->children[0], explode, found))
        {
            return true;
        }
        if (explodeRight(cur->children[1], explode, found))
        {
            return true;
        }
    }
    return false;
}

bool explode(Element *cur, int nested)
{
    static Element *head;
    if (nested == 0)
    {
        head = cur;
    }
    if (cur->children[0] != NULL)
    {
        if (nested == 4)
        {
            bool found = false;
            Element *prev = NULL;
            findLeft(head, cur, &prev, &found);
            if (prev != NULL)
            {
                prev->regular += cur->children[0]->regular;
            }
            found = false;
            explodeRight(head, cur->children[1], &found);
            cur->children[0] = NULL;
            cur->children[1] = NULL;
            cur->regular = 0;
            return true;
        }
        else
        {
            if (explode(cur->children[0], nested + 1))
            {
                return true;
            }
            if (explode(cur->children[1], nested + 1))
            {
                return true;
            }
        }
    }
    return false;
}

bool split(Element *cur)
{
    if (cur->children[0] == NULL)
    {
        if (cur->regular >= 10)
        {
            cur->children[0] = malloc(sizeof(Element));
            cur->children[1] = malloc(sizeof(Element));
            if (cur->children[0] == NULL || cur->children[1] == NULL)
            {
                puts("malloc failed");
                return false;
            }
            cur->children[0]->children[0] = NULL;
            cur->children[0]->children[1] = NULL;
            cur->children[0]->regular = cur->regular / 2;
            cur->children[1]->children[0] = NULL;
            cur->children[1]->children[1] = NULL;
            cur->children[1]->regular = (cur->regular / 2) + (cur->regular % 2);
            return true;
        }
    }
    else
    {
        if (split(cur->children[0]))
        {
            return true;
        }
        if (split(cur->children[1]))
        {
            return true;
        }
    }
    return false;
}

void reduce(Element *cur)
{
    bool needsReduction = true;
    while (needsReduction)
    {
        bool needsExplosion = true;
        while (needsExplosion)
        {
            needsExplosion = explode(cur, 0);
        }
        needsReduction = split(cur);
    }
}

uint64_t getMagnitude(Element *cur)
{
    if (cur->children[0] == NULL)
    {
        return cur->regular;
    }
    uint64_t left = getMagnitude(cur->children[0]);
    uint64_t right = getMagnitude(cur->children[1]);
    return (left * 3) + (right * 2);
}

void part1(Element *numbers, int entries)
{
    Element **copies = malloc(entries * sizeof(Element *));
    if (copies == NULL)
    {
        puts("malloc failed");
        return;
    }
    for (int i = 0; i < entries; i++)
    {
        copies[i] = copyTree(&numbers[i]);
    }
    Element *result = add(copies[0], copies[1]);
    reduce(result);
    for (int i = 2; i < entries; i++)
    {
        result = add(result, copies[i]);
        reduce(result);
    }
    puts("Part 1:");
    printTree(result);
    putchar('\n');
    uint64_t magnitude = getMagnitude(result);
    printf("Magnitude: %lu\n", magnitude);
    for (int i = 0; i < entries; i++)
    {
        freeTree(copies[i]);
    }
    free(copies);
}

void part2(Element *numbers, int entries)
{
    uint64_t largestMagnitude = 0;
    for (int i = 0; i < entries; i++)
    {
        for (int j = 0; j < entries; j++)
        {
            if (j != i)
            {
                Element *copy = copyTree(&numbers[i]);
                Element *copy2 = copyTree(&numbers[j]);
                Element *result = add(copy, copy2);
                reduce(result);
                uint64_t magnitude = getMagnitude(result);
                if (magnitude > largestMagnitude)
                {
                    largestMagnitude = magnitude;
                }
                freeTree(copy);
                freeTree(copy2);
            }
        }
    }
    printf("\nPart 2:\nLargest Magnitude: %lu\n", largestMagnitude);
}

int main()
{
    int fd = open("input", O_RDONLY);
    if (fd == -1)
    {
        perror("open");
        return 1;
    }
    struct stat fileInfo;
    if (fstat(fd, &fileInfo) != 0)
    {
        perror("fstat");
        close(fd);
        return 1;
    }
    char *data = malloc(fileInfo.st_size);
    if (data == NULL)
    {
        puts("malloc failed");
        close(fd);
        return 1;
    }
    ssize_t bytesRead = read(fd, data, fileInfo.st_size);
    close(fd);
    if (bytesRead == -1)
    {
        perror("read");
        free(data);
        return 1;
    }
    if (bytesRead != fileInfo.st_size)
    {
        printf("Error: read %d bytes. %d expected.\n", bytesRead, fileInfo.st_size);
        free(data);
        return 1;
    }
    int entries = 0;
    for (ssize_t i = 0; i < bytesRead; i++)
    {
        if (data[i] == '\n')
        {
            entries++;
        }
    }
    Element *numbers = malloc(entries * sizeof(Element));
    if (numbers == NULL)
    {
        puts("malloc failed");
        free(data);
        return 1;
    }
    char *readPointer = data;
    for (int i = 0; i < entries; i++)
    {
        if (!parseInput(&readPointer, &numbers[i]))
        {
            puts("Input parsing failed");
            free(data);
            return 1;
        }
        readPointer++;
    }
    free(data);
    part1(numbers, entries);
    part2(numbers, entries);
    return 0;
}