Advent of Code Day 9

aoc.c

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

typedef struct Point
{
    int x;
    int y;
} Point;

int width;
int height;
uint64_t basinSizes[2000];
Point *basinPoints;
uint8_t *grid;

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

bool pointInBasin(int x, int y, uint64_t basinIndex)
{
    for (int i = 0; i < basinSizes[basinIndex]; i++)
    {
        if (basinPoints[i].x == x && basinPoints[i].y == y)
        {
            return true;
        }
    }
    return false;
}

void findBasin(int x, int y, uint64_t basinIndex)
{
    if (grid[(y * width) + x] == 9)
    {
        return;
    }
    if (pointInBasin(x, y, basinIndex))
    {
        return;
    }
    basinPoints[basinSizes[basinIndex]].x = x;
    basinPoints[basinSizes[basinIndex]].y = y;
    basinSizes[basinIndex]++;
    if (x > 0)
    {
        findBasin(x - 1, y, basinIndex);
    }
    if (x < width - 1)
    {
        findBasin(x + 1, y, basinIndex);
    }
    if (y > 0)
    {
        findBasin(x, y - 1, basinIndex);
    }
    if (y < height - 1)
    {
        findBasin(x, y + 1, basinIndex);
    }
}

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);
    if (bytesRead == -1)
    {
        perror("read");
        close(fd);
        free(data);
        return 1;
    }
    if (bytesRead != fileInfo.st_size)
    {
        printf("Error: read %d bytes. %d expected.\n", bytesRead, fileInfo.st_size);
        close(fd);
        free(data);
        return 1;
    }
    close(fd);
    ssize_t dataIndex = 0;
    while(isNumber(data[dataIndex]))
    {
        width++;
        dataIndex++;
    }
    for (dataIndex = 0; dataIndex < bytesRead; dataIndex++)
    {
        if (data[dataIndex] == '\n')
        {
            height++;
        }
    }
    grid = malloc(width * height);
    basinPoints = malloc(width * height * sizeof(Point));
    if (grid == NULL || basinPoints == NULL)
    {
        puts("malloc failed");
        free(data);
        return 1;
    }
    int gridIndex = 0;
    for (dataIndex = 0; dataIndex < bytesRead; dataIndex++)
    {
        while(isNumber(data[dataIndex]))
        {
            grid[gridIndex++] = data[dataIndex++] - 48;
        }
    }
    free(data);
    uint64_t answer = 0;
    uint64_t numBasins = 0;
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            uint8_t adjacent[4];
            if (x > 0)
            {
                adjacent[0] = grid[(y * width) + (x - 1)];
            }
            else
            {
                adjacent[0] = 255;
            }
            if (x < width - 1)
            {
                adjacent[1] = grid[(y * width) + (x + 1)];
            }
            else
            {
                adjacent[1] = 255;
            }
            if (y > 0)
            {
                adjacent[2] = grid[((y - 1) * width) + x];
            }
            else
            {
                adjacent[2] = 255;
            }
            if (y < height - 1)
            {
                adjacent[3] = grid[((y + 1) * width) + x];
            }
            else
            {
                adjacent[3] = 255;
            }
            uint8_t cur = grid[(y * width) + x];
            bool lowPoint = true;
            for (int i = 0; i < 4; i++)
            {
                if (cur >= adjacent[i])
                {
                    lowPoint = false;
                    break;
                }
            }
            if (lowPoint)
            {
                answer += cur + 1;
                findBasin(x, y, numBasins);
                numBasins++;
            }
        }
    }
    free(grid);
    free(basinPoints);
    // Insertion sort
    for (int i = 1; i < numBasins; i++)
    {
        for (int j = i; j > 0 && basinSizes[j - 1] > basinSizes[j]; j--)
        {
            uint64_t temp = basinSizes[j];
            basinSizes[j] = basinSizes[j - 1];
            basinSizes[j - 1] = temp;
        }
    }
    uint64_t answer2 = basinSizes[numBasins - 1] * basinSizes[numBasins - 2] * basinSizes[numBasins - 3];
    printf("Part 1: %lu\nPart 2: %lu\n", answer, answer2);
    return 0;
}