#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>

bool IsBad(const std::vector<long> &row, const std::map<long, std::set<long>> &rules, size_t &bad_i);

int main()
{
	const std::string filename = "data.txt";
	std::ifstream ifs(filename);
	if(!ifs.is_open())
	{
		std::cerr << "Missing " << filename << "." << std::endl;
		return -1;
	}

	unsigned long total = 0;
	unsigned long total_pt2 = 0;

	std::map<long, std::set<long>> rules;
	std::vector<std::vector<long>> production;

	bool reading_page_numbers = true;
	for(std::string line; std::getline(ifs, line); )
	{
		if(line == "")
		{
			// one blank line is the break between reading page numbers and records.
			if(reading_page_numbers)
				reading_page_numbers = false;

			continue;
		}

		std::istringstream input(line);
		if(reading_page_numbers)
		{
			// for each value in the line:
			std::vector<long> numbers;
			for(std::string value; std::getline(input, value, '|'); )
			{
				try {
					numbers.push_back(std::atoi(value.c_str()));
				} catch (const std::exception &e) {
					std::cout << "Error parsing rule number from " << value << std::endl;
					exit(-1);
				}
			}
			if(numbers.size() != 2)
			{
				std::cout << "Error: Incorrect amount of page numbers (" << numbers.size()
				          << ") in rules import sequence." << std::endl;
				exit(-1);
			}
			rules[numbers[0]].insert(numbers[1]);
		}
		else
		{
			// for each value in the line:
			production.push_back({});
			for(std::string value; std::getline(input, value, ','); )
			{
				try {
					production.back().push_back(std::atoi(value.c_str()));
				} catch (const std::exception &e) {
					std::cout << "Error parsing production number from " << value << std::endl;
					exit(-1);
				}
			}
		}
	}

	// // Debug:
	// std::cout << "RULES:" << std::endl;
	// for(auto rule : rules)
	// {
	// 	std::cout << rule.first << " prints before ";
	// 	for(auto page : rule.second)
	// 		std::cout << page << ",";
	// 	std::cout << std::endl;
	// }
	// std::cout << std::endl;
	// std::cout << "PRODUCTION:" << std::endl;
	// for(auto row : production)
	// {
	// 	for(auto num : row)
	// 		std::cout << num << ",";
	// 	std::cout << std::endl;
	// }

	// For each production run:
	for(auto row : production)
	{
		size_t bad_idx;
		auto bad = IsBad(row, rules, bad_idx);

		// Part 1:
		if(!bad)
			total += row[row.size() / 2];
		// Part 2:
		else
		{
			std::vector<long> working;
			for(auto n : row)
				working.push_back(n);

			while(IsBad(working, rules, bad_idx))
			{
				auto temp = working[bad_idx];
				working.erase(working.begin() + bad_idx);
				working.insert(working.begin(), temp);

				// Debug Sort:
				// std::cout << "Trying again: ";
				// for(auto i : working)
				// 	std::cout << i << ",";
				// std::cout << std::endl;
			}

			total_pt2 += working[working.size() / 2];
		}
	}

	std::cout << "    Total: " <<     total << std::endl;
	std::cout << "PT2 Total: " << total_pt2 << std::endl;

	return 0;
}

bool IsBad(const std::vector<long> &row, const std::map<long, std::set<long>> &rules, size_t &bad_i)
{
	std::set<long> already_passed;
	bool bad = false;
	// For each page number in that production run:
	int i = 0;
	for(auto num : row)
	{
		// Check against all page numbers it shouldn't print after
		for(auto before : rules.at(num))
		{
			// If found, it's a bad row!
			if(std::find(already_passed.begin(), already_passed.end(), before) != already_passed.end())
			{
				bad = true;
				bad_i = i;
				break;
			}
		}

		// Keep track of numbers we've looked at already:
		already_passed.insert(num);
		++i;
	}
	return bad;
}