134 lines
3 KiB
C
134 lines
3 KiB
C
|
#include<stdlib.h>
|
||
|
|
#include<stdio.h>
|
||
|
|
#include<string.h>
|
||
|
|
#include<stdbool.h>
|
||
|
|
#include<unistd.h>
|
||
|
|
|
||
|
|
char **grid_copy(char **original, int width, int height)
|
||
|
|
{
|
||
|
|
char **copy = malloc(width * sizeof(char*));
|
||
|
|
copy[0] = malloc(width * height);
|
||
|
|
for (int i = 1; i < width; i++) {
|
||
|
|
copy[i] = copy[0] + i * height;
|
||
|
|
}
|
||
|
|
for (int i = 0; i < height; i++) {
|
||
|
|
for (int j = 0; j < width; j++) {
|
||
|
|
copy[j][i] = original[j][i];
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return copy;
|
||
|
|
}
|
||
|
|
|
||
|
|
bool check_loop(char **grid, int x, int y, int width, int height)
|
||
|
|
{
|
||
|
|
int guard[2] = {x, y};
|
||
|
|
int rot = 0;
|
||
|
|
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
|
||
|
|
// step (mark current X, check forward, step or rotate) until oob
|
||
|
|
while (true) {
|
||
|
|
// graphics!
|
||
|
|
/*
|
||
|
|
printf("\e[1;1H\e[2J");
|
||
|
|
for (int i = 0; i < width; i++) {
|
||
|
|
for (int j = 0; j < height; j++) {
|
||
|
|
if (grid[j][i] == '#')
|
||
|
|
printf("%c", grid[j][i]);
|
||
|
|
else if (grid[j][i] & 0b1111)
|
||
|
|
printf("X");
|
||
|
|
else
|
||
|
|
printf(".");
|
||
|
|
}
|
||
|
|
printf("\n");
|
||
|
|
}
|
||
|
|
usleep(20000);
|
||
|
|
printf("\e[1;1H\e[2J");
|
||
|
|
*/
|
||
|
|
// mark square dir
|
||
|
|
if (grid[guard[0]][guard[1]] & ( 1 << rot)) {
|
||
|
|
return 1;
|
||
|
|
}
|
||
|
|
grid[guard[0]][guard[1]] |= 1 << rot;
|
||
|
|
|
||
|
|
// oob?
|
||
|
|
if (guard[0] + dir[rot][0] < 0 ||
|
||
|
|
guard[0] + dir[rot][0] >= height ||
|
||
|
|
guard[1] + dir[rot][1] < 0 ||
|
||
|
|
guard[1] + dir[rot][1] >= height)
|
||
|
|
break;
|
||
|
|
// There is definitely an edge case here where the guard turns
|
||
|
|
// and instantly checks oob
|
||
|
|
while (grid[guard[0] + dir[rot][0]][guard[1] + dir[rot][1]] == '#')
|
||
|
|
rot = (rot + 1) % 4;
|
||
|
|
// step
|
||
|
|
guard[0] += dir[rot][0];
|
||
|
|
guard[1] += dir[rot][1];
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
int main ()
|
||
|
|
{
|
||
|
|
int guard[2];
|
||
|
|
|
||
|
|
// figure out data dimensions
|
||
|
|
FILE *input = fopen("./input", "r");
|
||
|
|
int width = 0;
|
||
|
|
int height = 1;
|
||
|
|
while (fgetc(input) != '\n') width++;
|
||
|
|
for (char c = fgetc(input); c != EOF; c = fgetc(input)) {
|
||
|
|
if (c == '\n')
|
||
|
|
height++;
|
||
|
|
}
|
||
|
|
rewind(input);
|
||
|
|
printf("Dimensions: %d x %d\n", width, height);
|
||
|
|
|
||
|
|
// make 2d array
|
||
|
|
char **grid = malloc(width * sizeof(char*));
|
||
|
|
grid[0] = malloc(width * height);
|
||
|
|
for (int i = 1; i < width; i++) {
|
||
|
|
grid[i] = grid[0] + i * height;
|
||
|
|
}
|
||
|
|
|
||
|
|
// put the data in the array
|
||
|
|
for (int i = 0; i < height; i++) {
|
||
|
|
for (int j = 0; j < width; j++) {
|
||
|
|
char c = fgetc(input);
|
||
|
|
if (c == '.') {
|
||
|
|
grid[j][i] = 0;
|
||
|
|
printf(".");
|
||
|
|
} else {
|
||
|
|
grid[j][i] = c;
|
||
|
|
printf("%c", c);
|
||
|
|
}
|
||
|
|
if (grid[j][i] == '^') {
|
||
|
|
guard[0] = j;
|
||
|
|
guard[1] = i;
|
||
|
|
grid[j][i] = 0;
|
||
|
|
// printf("guard coords: %d/%d\n", guard[0], guard[1]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
// skip newline
|
||
|
|
printf("\n");
|
||
|
|
fgetc(input);
|
||
|
|
}
|
||
|
|
fclose(input);
|
||
|
|
|
||
|
|
int sum = 0;
|
||
|
|
// for each non '#' square
|
||
|
|
for (int i = 0; i < height; i++) {
|
||
|
|
for (int j = 0; j < width; j++) {
|
||
|
|
// copy grid into a temp-grid
|
||
|
|
if (grid[j][i] != '#' && !(j == guard[0] && i == guard[1])) {
|
||
|
|
char **tmp = grid_copy(grid, width, height);
|
||
|
|
tmp[j][i] = '#';
|
||
|
|
bool test = check_loop(tmp, guard[0], guard[1], width, height);
|
||
|
|
sum += test;
|
||
|
|
if (test)
|
||
|
|
printf("%dx%d found!\n", j, i);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
printf("total possibilities: %d\n", sum);
|
||
|
|
}
|