#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <unordered_set>

using namespace std;

namespace {

using Plants = unordered_set<long>;
using Rules  = map<string, char>;
using Puzzle = tuple<Plants, Rules>;

Puzzle
read_file(const filesystem::path& filename)
{
	fstream file{ filename };

	string line;
	getline(file, line);
	line.erase(0, line.find(": ") + 2);

	Plants plants;
	for ( size_t idx = 0; idx != line.length(); ++idx ) {
		if ( line.at(idx) == '#' ) {
			plants.insert(static_cast<long>(idx));
		}
	}

	getline(file, line);

	Rules rules;
	while ( getline(file, line) ) {
		auto lhs = line.substr(0, 5);
		auto rhs = line.substr(9);

		rules[lhs] = rhs.at(0);
	}

	return { plants, rules };
}

Plants
update(const Plants& current, const Rules& rules)
{
	auto [min, max] = ranges::minmax(current);

	Plants next;

	for ( auto i = min - 2; i <= max + 2; ++i ) {
		string pattern;
		pattern += current.contains(i - 2) ? '#' : '.';
		pattern += current.contains(i - 1) ? '#' : '.';
		pattern += current.contains(i) ? '#' : '.';
		pattern += current.contains(i + 1) ? '#' : '.';
		pattern += current.contains(i + 2) ? '#' : '.';

		if ( rules.contains(pattern) && rules.at(pattern) == '#' ) {
			next.insert(i);
		}
	}

	return next;
}

void
part1(const Puzzle& puzzle)
{
	auto [state, rules] = puzzle;

	for ( int i = 0; i != 20; ++i ) {
		state = update(state, rules);
	}

	long sum = 0;
	for ( const auto pos: state ) {
		sum += pos;
	}
	cout << "Part 1: " << sum << '\n';
}

void
part2(const Puzzle& puzzle)
{
	auto [state, rules] = puzzle;

	auto to_string = [&] {
		string result;

		auto [min, max] = ranges::minmax(state);
		for ( auto pos = min; pos <= max; ++pos ) {
			result += (state.contains(pos) ? '#' : '.');
		}

		return result;
	};

	unordered_set<string> seen;
	for ( long shift = 50000000000;; --shift ) {
		auto pattern = to_string();

		if ( seen.contains(pattern) ) {
			long sum = 0;
			for ( const auto pos: state ) {
				sum += pos + shift;
			}
			cout << "Part 2: " << sum << '\n';
			return;
		}

		seen.insert(pattern);

		state = update(state, rules);
	}
}

} // namespace

int
main()
{
	auto puzzle = read_file("data/day12.txt");
	part1(puzzle);
	part2(puzzle);
}