#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);
}