Solution for AoC 2023 Day 17

2023d17.c

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <ctype.h>

#ifdef TEST
#define INPUT "input_test"
#define GRID_SIZE 13
#else
#define GRID_SIZE 141
#define INPUT "input"
#endif
#define QUEUE_SIZE 100 * GRID_SIZE * GRID_SIZE
#define NB_CARDINAL_DIRECTIONS 4

#define VALID_COORDS(row, col) (row >= 0 && row < GRID_SIZE && col >= 0 && col < GRID_SIZE)

typedef struct pos_s {
    int row;
    int col;
} pos_t;

typedef enum direction_e {
    NORTH = '^',
    EAST = '>',
    SOUTH = 'v',
    WEST = '<',
    NONE = ' ',
} direction_t;

// auxiliary structure to store a position and direction
// for any given position on the path
typedef struct posdir_s {
    pos_t pos;
    direction_t dir;
    int consecutive; // number of consecutive times we've used this direction
} posdir_t;

int grid[GRID_SIZE][GRID_SIZE] = {0};

char idx_to_dir(int idx) {
    switch (idx) {
    case 0:
        return '^';
    case 1:
        return '>';
    case 2:
        return 'v';
    case 3:
        return '<';
    default:
        return '^';
    }
}

int dir_to_idx(char c) {
    switch (c) {
    case '^':
        return 0;
    case '>':
        return 1;
    case 'v':
        return 2;
    case '<':
        return 3;
    default:
        return 0;
    }
}

pos_t convert_dir(char c) {
    switch (c) {
    case '>':
        return (pos_t) {0, 1};
    case '<':
        return (pos_t) {0, -1};
    case 'v':
        return (pos_t) {1, 0};
    case '^':
        return (pos_t) {-1, 0};
    default:
        return (pos_t) {0, 0};
    }
}

int min_cardinal_distance(int dist[NB_CARDINAL_DIRECTIONS][3]) {
    int min = INT_MAX;
    for (int i = 0; i < NB_CARDINAL_DIRECTIONS; i++) {
        for (int j = 0; j < 3; j++) {
            if (dist[i][j] < min) {
                min = dist[i][j];
            }
        }
    }
    return min;
}

void display_queue(posdir_t* queue, int queue_size) {
    for (int i = 0; i < queue_size; i++) {
        printf("(%d,%d,%c,%d) ", queue[i].pos.row, queue[i].pos.col, queue[i].dir, queue[i].consecutive);
    }
    printf("\n");
}

void display_grid() {
    for (int i = 0; i < GRID_SIZE; i++) {
        for (int j = 0; j < GRID_SIZE; j++) {
            printf("%d", grid[i][j]);
        }
        printf("\n");
    }
}

posdir_t pop(posdir_t* queue, int* queue_size) {
    posdir_t res = queue[0];
    for (int i = 0; i < *queue_size - 1; i++) {
        queue[i] = queue[i + 1];
    }
    *queue_size -= 1;
    return res;
}

void push(posdir_t* queue, posdir_t posdir, int* queue_size) {
    if (*queue_size >= QUEUE_SIZE) {
        printf("‼️  queue is full\n");
        exit(1);
    }
    queue[*queue_size] = posdir;
    *queue_size += 1;
}

bool is_enqueued(posdir_t* queue, posdir_t posdir, int queue_size) {
    for (int i = 0; i < queue_size; i++) {
        if (queue[i].pos.row == posdir.pos.row && queue[i].pos.col == posdir.pos.col && queue[i].dir == posdir.dir&& queue[i].consecutive == posdir.consecutive) {
            return true;
        }
    }
    return false;
}

// For a given position coming from a given direction, we want to know which directions we can go to
// The restrictions are:
// - we can't go back
// - we can't go forward in the same direction more than 3 times
posdir_t* allowed_neighbors(posdir_t current, int* nb) {
    posdir_t* neighbors = NULL;
    int nb_neighbors = 0;

    char directions[] = { NORTH, EAST, SOUTH, WEST };
    for (int i = 0; i < NB_CARDINAL_DIRECTIONS; i++) {
        direction_t dir = directions[i];

        if ((dir == NORTH && current.dir == SOUTH) ||
            (dir == SOUTH && current.dir == NORTH) ||
            (dir == EAST && current.dir == WEST) ||
            (dir == WEST && current.dir == EAST)) {
            continue; // we don't want to look back
        }

        pos_t direction_delta = convert_dir(dir);

        posdir_t neighbor;
        neighbor.pos.row = current.pos.row + direction_delta.row;
        neighbor.pos.col = current.pos.col + direction_delta.col;

        int row = neighbor.pos.row;
        int col = neighbor.pos.col;

        if (!VALID_COORDS(row, col)) {
            continue;
        }

        neighbor.dir = dir;

        if (dir == current.dir && current.consecutive == 3) {
            continue; // can't go forward in the same direction
        }

        neighbor.consecutive = (neighbor.dir == current.dir) ? current.consecutive + 1 : 1;

        neighbors = realloc(neighbors, sizeof(posdir_t) * (nb_neighbors + 1));
        neighbors[nb_neighbors++] = neighbor;
    }

    *nb = nb_neighbors;
    return neighbors;
}

posdir_t pop_position_with_least_dist(posdir_t* queue, int* queue_size, int dist[GRID_SIZE][GRID_SIZE][NB_CARDINAL_DIRECTIONS][3]) {
    int min = INT_MAX;
    int min_idx = 0;
    for (int i = 0; i < *queue_size; i++) {
        posdir_t current = queue[i];
        int dir_idx = dir_to_idx(current.dir);
        for (int j = 0; j < 3; ++j) {
            int d = dist[current.pos.row][current.pos.col][dir_idx][j];
            if (d < min) {
                min = d;
                min_idx = i;
            }
        }
    }

    posdir_t res = queue[min_idx];
    for (int i = min_idx; i < *queue_size - 1; i++) {
        queue[i] = queue[i + 1];
    }
    *queue_size -= 1;

    return res;
}

void show_route(int dist[GRID_SIZE][GRID_SIZE][NB_CARDINAL_DIRECTIONS][3], posdir_t path[GRID_SIZE][GRID_SIZE][NB_CARDINAL_DIRECTIONS][3], pos_t start, pos_t end, int res) {
    posdir_t* route = malloc(sizeof(posdir_t) * 1000); // just allocate 'enough' room for the size of the route
    int route_size = 0;

    posdir_t cur;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (dist[end.row][end.col][i][j] == res) {
                push(route, (posdir_t) { (pos_t) { end.row, end.col }, .dir = idx_to_dir(i), .consecutive = j }, &route_size);
                cur = path[end.row][end.col][i][j];
                break;
            }
        }
    }

    while (!(cur.pos.row == start.row && cur.pos.col == start.col)) {
        posdir_t new_prev = path[cur.pos.row][cur.pos.col][dir_to_idx(cur.dir)][cur.consecutive];
        push(route, cur, &route_size);
        cur = new_prev;
    }

    for (int i = route_size - 1; i >= 0; --i) {
        printf("(%d,%d,%c,%d) ", route[i].pos.row, route[i].pos.col, route[i].dir, route[i].consecutive);
    }
    printf("\n");

    char grid_with_route[GRID_SIZE][GRID_SIZE];
    for (int i = 0; i < GRID_SIZE; i++) {
        for (int j = 0; j < GRID_SIZE; j++) {
            grid_with_route[i][j] = '.';
        }
    }

    for (int i = 0; i < route_size; i++) {
        grid_with_route[route[i].pos.row][route[i].pos.col] = route[i].dir;
    }

    for (int i = 0; i < GRID_SIZE; i++) {
        for (int j = 0; j < GRID_SIZE; j++) {
            printf("%c", grid_with_route[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    
    free(route);
}

int distance(pos_t start, pos_t end) {
    // For each position on the grid, there can be 4 distances, one for each direction we can come from
    // 0: N, 1: E, 2: S, 3: W
    int dist[GRID_SIZE][GRID_SIZE][NB_CARDINAL_DIRECTIONS][3];
    for (int i = 0; i < GRID_SIZE; i++) {
        for (int j = 0; j < GRID_SIZE; j++) {
            for (int k = 0; k < 3; ++k) {
                dist[i][j][0][k] = INT_MAX;
                dist[i][j][1][k] = INT_MAX;
                dist[i][j][2][k] = INT_MAX;
                dist[i][j][3][k] = INT_MAX;
            }
        }
    }
    for (int i = 0; i  < NB_CARDINAL_DIRECTIONS; i++) {
        // For the starting position the distance is null
        for (int j = 0; j < 3; ++j) {
            dist[start.row][start.col][i][j] = 0;
        }
    }

    posdir_t* queue = malloc(sizeof(posdir_t) * QUEUE_SIZE);
    queue[0] = (posdir_t) { .pos = start, .dir = NONE, .consecutive = 0 };
    int queue_size = 1; // initially, we only have the start position in the queue

    posdir_t* seen = malloc(sizeof(posdir_t) * QUEUE_SIZE);
    int seen_size = 0;

    posdir_t path[GRID_SIZE][GRID_SIZE][NB_CARDINAL_DIRECTIONS][3];

    // While there are still elements in the queue, we take the first element (pop) and explore its neighbors
    // if there is a distance with a lower value for a given direction, we update it in distances array
    while (queue_size) {
        // display_queue(queue, queue_size);

        posdir_t current = pop_position_with_least_dist(queue, &queue_size, dist);

        // sanity check
        if (!VALID_COORDS(current.pos.row, current.pos.col)) {
            printf("‼️  invalid coords %d,%d\n", current.pos.row, current.pos.col);
            return -1;
        }

        // we've already seen this position, we don't want to explore it again
        if (is_enqueued(seen, current, seen_size)) {
            continue;
        }

        // we've reached the end, we don't want to continue exploring from this point, but we need to process the queue
        // as long as there are elements in it
        if (current.pos.row == end.row && current.pos.col == end.col) {
            continue;
        }

        int dist_current = dist[current.pos.row][current.pos.col][dir_to_idx(current.dir)][current.consecutive];
        printf("ℹ️  CURRENT: (%d,%d,%c,%d), dist: %d\n", current.pos.row, current.pos.col, current.dir, current.consecutive, dist_current);


        // If we reached this point, this means we haven't seen this position yet
        // and we will explore its neighbors
        push(seen, current, &seen_size);

        int nb_neighbors = 0;
        posdir_t* neighbors = allowed_neighbors(current, &nb_neighbors);
        for (int i = 0; i < nb_neighbors; i++) {
            posdir_t neighbor = neighbors[i];
            int row = neighbor.pos.row;
            int col = neighbor.pos.col;

            // current dist (to the source)
            int dir_idx = dir_to_idx(neighbor.dir);

            // potential new distance (to the neighbor)
            int new_distance = dist_current + grid[row][col];
            if (new_distance < dist[row][col][dir_idx][neighbor.consecutive]) {
                dist[row][col][dir_idx][neighbor.consecutive] = new_distance;
                printf("new distance to %d,%d coming from %d,%d,%c: %d\t absolute dist: %d\n",
                        row, col, current.pos.row, current.pos.col, neighbor.dir, new_distance, min_cardinal_distance(dist[row][col]));

                path[row][col][dir_idx][neighbor.consecutive] = current;
            }

            // in all cases we push to the queue, maybe it minimizes the distance
            push(queue, neighbor, &queue_size);
        }

        free(neighbors);
    }

    free(queue);
    free(seen);

    int res = min_cardinal_distance(dist[end.row][end.col]);
    
    // uncomment if you want to show the route leading to the goal
    // show_route(dist, path, start, end, res);

    return res;
}

int main() {
    FILE* f = fopen(INPUT, "r");
    if (!f) {
        perror("fopen failed");
        return 1;
    }

    int res = 0;

    char line[1000];
    int lines = 0;
    while (fgets(line, sizeof(line), f)) {
        char* p = line;
        while (*p) {
            grid[lines][p - line] = (*p - '0');
            p++;
        }

        lines++;
    }

#ifdef TEST
    display_grid();
#endif

    pos_t start = (pos_t) {0, 0};
    pos_t end = (pos_t) {GRID_SIZE - 1, GRID_SIZE - 1};

    res = distance(start, end);
    printf("res: %d\n", res);

    fclose(f);
}