#include <filesystem>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

namespace {

enum class Direction : uint8_t {
	Up,
	Right,
	Down,
	Left
};

struct Cart {
	size_t        x;
	size_t        y;
	Direction     direction;
	unsigned long intersection{};
};

using Grid  = vector<string>;
using Carts = vector<Cart>;

tuple<Grid, Carts>
read_file(const filesystem::path& filename)
{
	ifstream file{ filename };

	Grid  data;
	Carts carts;

	size_t y = 0;
	for ( string line; getline(file, line); ) {
		for ( size_t x = 0; x != line.size(); ++x ) {
			using enum Direction;

			const char chr = line[x];
			if ( chr == '^' || chr == 'v' ) {
				carts.emplace_back(x, y, chr == '^' ? Up : Down);
			}
			else if ( chr == '<' || chr == '>' ) {
				carts.emplace_back(x, y, chr == '<' ? Left : Right);
			}
		}
		data.emplace_back(line);
		++y;
	}

	return { data, carts };
}

void
sort_carts(Carts& carts)
{
	ranges::sort(carts,
	             [](auto& lhs, auto& rhs) {
		             return tie(lhs.y, lhs.x) < tie(rhs.y, rhs.x);
	             });
}

void
move_cart(Cart& cart)
{
	using enum Direction;

	switch ( cart.direction ) {
	case Up:
		--cart.y;
		break;
	case Right:
		++cart.x;
		break;
	case Down:
		++cart.y;
		break;
	case Left:
		--cart.x;
		break;
	}
}

void
apply_direction_rules(const Grid& grid, Cart& cart)
{
	using enum Direction;

	const char chr = grid[cart.y][cart.x];
	switch ( chr ) {
	case '/':
		if ( cart.direction == Up ) {
			cart.direction = Right;
		}
		else if ( cart.direction == Right ) {
			cart.direction = Up;
		}
		else if ( cart.direction == Down ) {
			cart.direction = Left;
		}
		else if ( cart.direction == Left ) {
			cart.direction = Down;
		}
		break;
	case '\\':
		if ( cart.direction == Up ) {
			cart.direction = Left;
		}
		else if ( cart.direction == Right ) {
			cart.direction = Down;
		}
		else if ( cart.direction == Down ) {
			cart.direction = Right;
		}
		else if ( cart.direction == Left ) {
			cart.direction = Up;
		}
		break;
	case '+':
		switch ( cart.intersection++ % 3 ) {
		case 0:
			cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 3) % 4);
			break;
		case 2:
			cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 1) % 4);
			break;
		default:
			break;
		};
		break;
	default:
		break;
	}
}

void
part1(const Grid& grid, Carts carts)
{
	while ( true ) {
		sort_carts(carts);

		for ( size_t i = 0; i != carts.size(); ++i ) {
			auto& cart = carts[i];

			move_cart(cart);
			apply_direction_rules(grid, cart);

			for ( size_t j = 0; j != carts.size(); ++j ) {
				if ( i == j ) {
					continue;
				}

				const auto& other = carts[j];

				if ( cart.x == other.x && cart.y == other.y ) {
					cout << "Part 1: " << cart.x << ',' << cart.y << '\n';
					return;
				}
			}
		}
	}
}

void
part2(const Grid& grid, Carts carts)
{
	while ( true ) {
		sort_carts(carts);

		vector<size_t> carts_to_be_removed;

		for ( size_t i = 0; i != carts.size(); ++i ) {
			auto& cart = carts[i];

			move_cart(cart);
			apply_direction_rules(grid, cart);

			for ( size_t j = 0; j != carts.size(); ++j ) {
				if ( i == j ) {
					continue;
				}

				const auto& other = carts[j];

				if ( cart.x == other.x && cart.y == other.y ) {
					carts_to_be_removed.emplace_back(i);
					carts_to_be_removed.emplace_back(j);
				}
			}
		}

		// remove carts
		ranges::sort(carts_to_be_removed);
		ranges::reverse(carts_to_be_removed);

		for ( auto num: carts_to_be_removed ) {
			carts.erase(carts.begin() + static_cast<long>(num));
		}

		if ( carts.size() == 1 ) {
			cout << "Part 2: " << carts[0].x << ',' << carts[0].y << '\n';
			return;
		}
	}
}

} // namespace

int
main()
{
	auto [grid, carts] = read_file("data/day13.txt");
	part1(grid, carts);
	part2(grid, carts);
}