Advent of Code Day 24 Part 1

part1.c

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

#define BLIZZARD_LEFT 1
#define BLIZZARD_RIGHT 2
#define BLIZZARD_UP 4
#define BLIZZARD_DOWN 8
#define WALL 16

#define MAX_GRIDS 256

typedef struct Grid
{
    int width;
    int height;
    int entrance;
    int exit;
    int num_grids;
    uint8_t *data[MAX_GRIDS];
} Grid;

typedef struct Queue
{
    int x;
    int y;
    int minute;
    struct Queue *next;
} Queue;

static void parse_input(Grid *grid)
{
    int fd = open("input", O_RDONLY);
    if (fd == -1) {
        perror("open");
        exit(-1);
    }
    struct stat file_info;
    if (fstat(fd, &file_info) == -1) {
        perror("fstat");
        exit(-1);
    }
    char *buffer = malloc(file_info.st_size);
    if (buffer == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    ssize_t bytes = read(fd, buffer, file_info.st_size);
    if (bytes != file_info.st_size) {
        if (bytes == -1) {
            perror("read");
        } else {
            fprintf(stderr, "%zd bytes read. %zu expected\n", bytes, file_info.st_size);
        }
        exit(-1);
    }
    close(fd);
    grid->width = 0;
    grid->height = 0;
    grid->entrance = -1;
    grid->exit = -1;
    grid->num_grids = 1;
    ssize_t index = 0;
    while (buffer[index] != '\n') {
        index += 1;
        grid->width += 1;
    }
    while (index < bytes) {
        if (buffer[index] == '\n') {
            grid->height += 1;
        }
        index += 1;
    }
    grid->data[0] = malloc(grid->width * grid->height);
    if (grid->data[0] == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    index = 0;
    uint8_t *grid_ptr = grid->data[0];
    while (index < bytes) {
        switch(buffer[index]) {
            case '#':
                *grid_ptr++ = WALL;
                break;
            case '.':
                *grid_ptr++ = 0;
                break;
            case '<':
                *grid_ptr++ = BLIZZARD_LEFT;
                break;
            case '>':
                *grid_ptr++ = BLIZZARD_RIGHT;
                break;
            case '^':
                *grid_ptr++ = BLIZZARD_UP;
                break;
            case 'v':
                *grid_ptr++ = BLIZZARD_DOWN;
                break;
            case '\n':
                break;
            default:
                fprintf(stderr, "Unexpected character in input: %c\n", buffer[index]);
        }
        index += 1;
    }
    for (int x = 0; x < grid->width; x++) {
        if (grid->data[0][x] == 0) {
            grid->entrance = x;
            break;
        }
    }
    if (grid->entrance == -1) {
        fprintf(stderr, "Failed to find entrance\n");
        exit(-1);
    }
    grid_ptr = grid->data[0] + (grid->width * (grid->height - 1));
    for (int x = 0; x < grid->width; x++) {
        if (grid_ptr[x] == 0) {
            grid->exit = x;
            break;
        }
    }
    if (grid->exit == -1) {
        fprintf(stderr, "Failed to find exit\n");
        exit(-1);
    }
    free(buffer);
}

static int count_blizzards(uint8_t cell)
{
    int blizzards = 0;
    for (int i = 0; i < 4; i++) {
        blizzards += cell & 1;
        cell >>= 1;
    }
    return blizzards;
}

static void print_grid(Grid *grid, int minute)
{
    uint8_t *ptr = grid->data[minute];
    for (int y = 0; y < grid->height; y++) {
        for (int x = 0; x < grid->width; x++) {
            int num_blizzards = count_blizzards(*ptr);
            if (num_blizzards > 1) {
                putchar(num_blizzards + '0');
            } else {
                switch(*ptr) {
                    case 0:
                        putchar('.');
                        break;
                    case WALL:
                        putchar('#');
                        break;
                    case BLIZZARD_LEFT:
                        putchar('<');
                        break;
                    case BLIZZARD_RIGHT:
                        putchar('>');
                        break;
                    case BLIZZARD_UP:
                        putchar('^');
                        break;
                    case BLIZZARD_DOWN:
                        putchar('v');
                        break;
                }
            }
            ptr++;
        }
        putchar('\n');
    }
}

static void simulate_blizzard(Grid *grid, int minute)
{
    if (minute >= MAX_GRIDS) {
        fprintf(stderr, "Minute %d exceeds maximum numbers of grids\n", minute);
        exit(-1);
    }
    if (minute < grid->num_grids) {
        return;
    }
    if (minute != grid->num_grids) {
        simulate_blizzard(grid, minute - 1);
    }
    int bytes = grid->width * grid->height;
    uint8_t *cur = malloc(bytes);
    if (cur == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    grid->data[minute] = cur;
    grid->num_grids += 1;
    uint8_t *prev = grid->data[minute - 1];
    for (int i = 0; i < bytes; i++) {
        if (prev[i] == WALL) {
            cur[i] = WALL;
        } else {
            cur[i] = 0;
        }
    }
    for (int y = 0; y < grid->height; y++) {
        for (int x = 0; x < grid->width; x++) {
            if (*prev & BLIZZARD_LEFT) {
                int left = x - 1;
                if (left == 0) {
                    left = grid->width - 2;
                }
                cur[(y * grid->width) + left] |= BLIZZARD_LEFT;
            }
            if (*prev & BLIZZARD_RIGHT) {
                int right = x + 1;
                if (right == grid->width - 1) {
                    right = 1;
                }
                cur[(y * grid->width) + right] |= BLIZZARD_RIGHT;
            }
            if (*prev & BLIZZARD_UP) {
                int up = y - 1;
                if (up == 0) {
                    up = grid->height - 2;
                }
                cur[(up * grid->width) + x] |= BLIZZARD_UP;
            }
            if (*prev & BLIZZARD_DOWN) {
                int down = y + 1;
                if (down == grid->height - 1) {
                    down = 1;
                }
                cur[(down * grid->width) + x] |= BLIZZARD_DOWN;
            }
            prev++;
        }
    }
}

static void add_queue(Queue **queue_head, Queue **queue_tail, Queue *node)
{
    Queue *ins = malloc(sizeof(Queue));
    if (ins == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(-1);
    }
    memcpy(ins, node, sizeof(Queue));
    ins->next = NULL;
    if (*queue_tail == NULL) {
        *queue_head = ins;
    } else {
        (*queue_tail)->next = ins;
    }
    *queue_tail = ins;
}

static bool pop_queue(Queue **queue_head, Queue **queue_tail, Queue *node)
{
    if (*queue_head == NULL) {
        return false;
    }
    Queue *old = *queue_head;
    memcpy(node, old, sizeof(Queue));
    *queue_head = old->next;
    if (*queue_head == NULL) {
        *queue_tail = NULL;
    }
    free(old);
    return true;
}

static bool is_empty(Grid *grid, Queue *neighbor)
{
    if (neighbor->x < 0 || neighbor->x >= grid->width || neighbor->y < 0 || neighbor->y >= grid->height) {
        return false;
    }
    return grid->data[neighbor->minute][(neighbor->y * grid->width) + neighbor->x] == 0;
}

int main(void)
{
    Grid grid;
    parse_input(&grid);
    Queue *queue_head = NULL;
    Queue *queue_tail = NULL;
    Queue node;
    node.x = grid.entrance;
    node.y = 0;
    node.minute = 0;
    add_queue(&queue_head, &queue_tail, &node);
    while (pop_queue(&queue_head, &queue_tail, &node)) {
        if (node.x == grid.exit && node.y == grid.height - 1) {
            printf("Answer: %d minutes\n", node.minute);
            return 0;
        }
        node.minute += 1;
        simulate_blizzard(&grid, node.minute);
        if (is_empty(&grid, &node)) {
            add_queue(&queue_head, &queue_tail, &node);
        }
        node.x -= 1;
        if (is_empty(&grid, &node)) {
            add_queue(&queue_head, &queue_tail, &node);
        }
        node.x += 2;
        if (is_empty(&grid, &node)) {
            add_queue(&queue_head, &queue_tail, &node);
        }
        node.x -= 1;
        node.y -= 1;
        if (is_empty(&grid, &node)) {
            add_queue(&queue_head, &queue_tail, &node);
        }
        node.y += 2;
        if (is_empty(&grid, &node)) {
            add_queue(&queue_head, &queue_tail, &node);
        }
    }
    puts("Failed to find exit cell in BFS");
    return 0;
}