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

using namespace std;

namespace {

vector<string>
split(const string& line)
{
	stringstream   strm{ line };
	vector<string> words;

	for ( string word; getline(strm, word, ' '); ) {
		words.emplace_back(word);
	}

	return words;
}

map<string, set<string>>
read_file(const filesystem::path& filename)
{
	ifstream                 file{ filename };
	map<string, set<string>> graph;

	for ( string line; getline(file, line); ) {
		auto words = split(line);
		graph[words.at(1)].emplace(words.at(7));
	}

	return graph;
}

vector<string>
topologicalSort(const map<string, set<string>>& graph)
{
	map<string, int> indegree;

	// Eingangsgrade initialisieren
	for ( const auto& [node, neighbors]: graph ) {
		if ( !indegree.contains(node) ) {
			indegree[node] = 0;
		}
		for ( const auto& neighbor: neighbors ) {
			indegree[neighbor]++;
		}
	}

	// Queue mit Knoten, deren Eingangsgrad 0 ist
	priority_queue<string, vector<string>, greater<>> queue;
	for ( const auto& [node, deg]: indegree ) {
		if ( deg == 0 ) {
			queue.push(node);
		}
	}

	vector<string> sorted;

	// Kahn's Algorithmus
	while ( !queue.empty() ) {
		string node = queue.top();
		queue.pop();

		sorted.push_back(node);

		if ( !graph.contains(node) ) {
			continue;
		}

		for ( const auto& neighbor: graph.at(node) ) {
			indegree[neighbor]--;
			if ( indegree[neighbor] == 0 ) {
				queue.push(neighbor);
			}
		}
	}

	// Prüfen auf Zyklus
	if ( sorted.size() != indegree.size() ) {
		throw runtime_error("Zyklus im Graph gefunden! Keine topologische Sortierung möglich.");
	}

	return sorted;
}

void
part1(const map<string, set<string>>& graph)
{
	auto sorted = topologicalSort(graph);

	cout << "Part 1: ";
	ranges::copy(sorted, ostream_iterator<string>(cout));
	cout << '\n';
}

void
part2(const map<string, set<string>>& graph, const int workers, const int base)
{
	map<string, int> indegree;

	// Eingangsgrade initialisieren
	for ( const auto& [node, neighbors]: graph ) {
		if ( !indegree.contains(node) ) {
			indegree[node] = 0;
		}
		for ( const auto& neighbor: neighbors ) {
			indegree[neighbor]++;
		}
	}

	set<string> available;
	for ( const auto& [node, deg]: indegree ) {
		if ( deg == 0 ) {
			available.insert(node);
		}
	}

	set<pair<int, string>> finishing;

	int active_workers = 0;
	int time           = 0;

	while ( !indegree.empty() ) {
		while ( !finishing.empty() && finishing.begin()->first == time ) {
			auto [finish_time, node] = *finishing.begin();
			finishing.erase(finishing.begin());

			active_workers--;

			indegree.erase(node);

			if ( !graph.contains(node) ) {
				continue;
			}

			for ( const auto& neighbor: graph.at(node) ) {
				indegree[neighbor]--;
				if ( indegree[neighbor] == 0 ) {
					available.insert(neighbor);
				}
			}
		}

		while ( active_workers < workers && !available.empty() ) {
			auto node = *available.begin();
			available.erase(available.begin());

			int duration    = base + (node.at(0) - 'A' + 1);
			int finish_time = time + duration;

			finishing.emplace(finish_time, node);
			active_workers++;
		}

		if ( finishing.empty() ) {
			if ( available.empty() ) {
				break;
			}
			else {
				time++;
			}
		}
		else {
			time = finishing.begin()->first;
		}
	}

	cout << "Part 2: " << time << '\n';
}

} // namespace

int
main()
{
	auto graph = read_file("data/day07.txt");
	try {
		part1(graph);

		static const int WORKERS = 5;
		static const int BASE    = 60;
		part2(graph, WORKERS, BASE);
	}
	catch ( exception& e ) {
		cerr << "Fehler: " << e.what() << '\n';
	}
}