88 lines
2.3 KiB
C
88 lines
2.3 KiB
C
#include "aoc.h"
|
|
|
|
typedef enum Direction {
|
|
Up, Right, Down, Left
|
|
} Direction;
|
|
|
|
static const int offsets[4][2] = {
|
|
[Up] = { 0, -1},
|
|
[Right] = { 1, 0},
|
|
[Down] = { 0, 1},
|
|
[Left] = {-1, 0}
|
|
};
|
|
|
|
i32 traverse(Grid *grid, int x, int y, Direction facing, Arena arena) {
|
|
u8 *visited = ARENA_ALLOC_ARRAY(&arena, u8, grid->width * grid->height);
|
|
|
|
i32 result = 0;
|
|
for (;;) {
|
|
int index = y * grid->width + x;
|
|
if (visited[index] & (1 << facing)) {
|
|
// loop detected
|
|
result = -1;
|
|
break;
|
|
}
|
|
else if (visited[index] == 0) {
|
|
result++;
|
|
}
|
|
visited[index] |= (1 << facing);
|
|
|
|
int nx = x + offsets[facing][0];
|
|
int ny = y + offsets[facing][1];
|
|
if (nx >= 0 && ny >= 0 && nx < grid->width && ny < grid->height) {
|
|
i32 next_index = ny * grid->width + nx;
|
|
if (grid->grid[next_index] == '#') {
|
|
facing = (facing + 1) % 4;
|
|
}
|
|
else {
|
|
x = nx;
|
|
y = ny;
|
|
}
|
|
}
|
|
else {
|
|
break;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
Arena *arena = make_arena(Megabytes(1));
|
|
|
|
str input = read_file(arena, argv[1]);
|
|
Grid grid = parse_grid(input, arena);
|
|
|
|
int start_x = -1, start_y = -1;
|
|
for (int y = 0; y < grid.height; y++) {
|
|
for (int x = 0; x < grid.width; x++) {
|
|
if (grid_at(&grid, x, y) == '^') {
|
|
start_x = x;
|
|
start_y = y;
|
|
grid.grid[y * grid.width + x] = ':';
|
|
}
|
|
}
|
|
}
|
|
|
|
i32 part_1 = traverse(&grid, start_x, start_y, Up, *arena);
|
|
|
|
i32 part_2 = 0;
|
|
for (int y = 0; y < grid.height; y++) {
|
|
for (int x = 0; x < grid.width; x++) {
|
|
if (x == start_x && y == start_y) {
|
|
continue;
|
|
}
|
|
int index = y * grid.width + x;
|
|
u8 saved;
|
|
if ((saved = grid.grid[index]) != '#') {
|
|
grid.grid[index] = '#';
|
|
i32 visited = traverse(&grid, start_x, start_y, Up, *arena);
|
|
part_2 += (visited == -1);
|
|
grid.grid[index] = saved;
|
|
}
|
|
}
|
|
}
|
|
|
|
printf("%d\n", part_1);
|
|
printf("%d\n", part_2);
|
|
}
|