advent-of-code

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define HEIGHT 41//5
#define WIDTH  171//8

struct point {
    int x, y;
};

struct nodel {
    int dist;
    struct point p;
    struct nodel *next;
};

struct nodel *nodetop = NULL;
int grid[HEIGHT][WIDTH] = {0};

/* insert a node for dist and p so that nodetop is sorted */
void
node_push(int dist, struct point p) {
    struct nodel *n = malloc(sizeof(struct nodel));
    if (n == NULL) {
        perror("malloc");
        exit(1);
    }
    n->dist = dist;
    n->p.x = p.x;
    n->p.y = p.y;

    struct nodel *t = nodetop;
    if (t == NULL || t->dist < dist) {
        n->next = t;
        nodetop = n;
        return;
    }
    for (; t != NULL; t = t->next) {
        /* If anyone ever reads this, can you explain why part 2 requires `>=` and not `>`? Please tell me! */
        if (t->next == NULL || t->next->dist >= dist) {
            n->next = t->next;
            t->next = n;
            break;
        }
    }
}

struct nodel *
node_pop(void) {
    struct nodel *n = nodetop;
    if (n != NULL)
        nodetop = n->next;
    return n;
}

void
push_if_valid(int dist, int x, int y, int curheight, char partB) {
    if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT)
        return;
    struct point p = {x, y};
    if (partB == 0) {
        if (grid[y][x] <= curheight + 1)
            node_push(dist, p);
    } else {
        if (curheight <= grid[y][x] + 1)
            node_push(dist, p);
    }
}

int
main(int argc, char **argv) {
    char *buf = NULL;
    size_t buflen = 0;
    ssize_t n;
    FILE *f;
    struct point start, end;

    int visited[HEIGHT][WIDTH] = {0};

    nodetop = NULL;

    if (argc != 2) {
        fprintf(stderr, "usage: %s input\n", argv[0]);
        return 1;
    }

    f = fopen(argv[1], "r");
    if (f == NULL) {
        perror(argv[1]);
        return 1;
    }

    size_t row = 0;
    while ((n = getline(&buf, &buflen, f)) != -1) {
        if (buf[n - 1] == '\n') {
            buf[n - 1] = '\0';
            n--;
        }
        assert(n == WIDTH);
        for (ssize_t i = 0; i < n; i++) {
            switch (buf[i]) {
                case 'S':
                    start.x = i;
                    start.y = row;
                    buf[i] = 'a';
                    break;
                case 'E':
                    end.x = i;
                    end.y = row;
                    buf[i] = 'z';
                    break;
            }
            grid[row][i] = buf[i] - 'a';
        }
        row++;
    }

    free(buf);
    fclose(f);

    printf("start at (%d,%d)\nend at (%d,%d)\n", start.x, start.y, end.x, end.y);

    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++)
            printf("%c", grid[i][j] + 'a');
        printf("\n");
    }

    node_push(0, start);
    struct nodel *endpath;

    while (1) {
        struct nodel *n = node_pop();
        if (n == NULL) {
            fprintf(stderr, "reached end of node list.\n");
            exit(1);
        }
        if (visited[n->p.y][n->p.x]) {
            goto cont;
        }
        visited[n->p.y][n->p.x] = 1;
        //fprintf(stderr, "%d,%d = %d\n", n->p.x, n->p.y, n->dist);
        
        if (n->p.x == end.x && n->p.y == end.y) {
            endpath = n;
            break;
        }

        int curheight = grid[n->p.y][n->p.x];
        push_if_valid(n->dist + 1, n->p.x - 1, n->p.y, curheight, 0);
        push_if_valid(n->dist + 1, n->p.x + 1, n->p.y, curheight, 0);
        push_if_valid(n->dist + 1, n->p.x, n->p.y - 1, curheight, 0);
        push_if_valid(n->dist + 1, n->p.x, n->p.y + 1, curheight, 0);

cont:
        free(n);
    }

    printf("Part A: %d\n", endpath->dist);
    free(endpath);

    /* reset for part B */
    while (node_pop() != NULL) ;
    for (int y = 0; y < HEIGHT; y++)
        for (int x = 0; x < WIDTH; x++)
            visited[y][x] = 0;
    nodetop = NULL;

    /* This time start from the end and find the closest point of elevation a */
    /* Have to reverse the neighbour selection rule so that going from lowest
     * to end will still be possible. */
    node_push(0, end);
    while (1) {
        struct nodel *n = node_pop();
        if (n == NULL) {
            fprintf(stderr, "reached end of node list.\n");
            exit(1);
        }
        if (visited[n->p.y][n->p.x]) {
            goto contB;
        }
        visited[n->p.y][n->p.x] = 1;
        //fprintf(stderr, "%d,%d = %d\n", n->p.x, n->p.y, n->dist);
        
        int curheight = grid[n->p.y][n->p.x];
        if (curheight == 0) {
            endpath = n;
            break;
        }

        push_if_valid(n->dist + 1, n->p.x - 1, n->p.y, curheight, 1);
        push_if_valid(n->dist + 1, n->p.x + 1, n->p.y, curheight, 1);
        push_if_valid(n->dist + 1, n->p.x, n->p.y - 1, curheight, 1);
        push_if_valid(n->dist + 1, n->p.x, n->p.y + 1, curheight, 1);

contB:
        free(n);
    }

    printf("Part B: %d (%d,%d)\n", endpath->dist, endpath->p.x, endpath->p.y);
    free(endpath);

    return 0;
}