From 8c96639ec1f6757570510fc27f1c5fabece35eaf Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 16 Nov 2025 13:23:34 +0100
Subject: aoc 2018, days 1-11

---
 2018/src/day07.cpp | 194 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 194 insertions(+)
 create mode 100644 2018/src/day07.cpp

(limited to '2018/src/day07.cpp')

diff --git a/2018/src/day07.cpp b/2018/src/day07.cpp
new file mode 100644
index 0000000..e6147d6
--- /dev/null
+++ b/2018/src/day07.cpp
@@ -0,0 +1,194 @@
+#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';
+	}
+}
-- 
cgit v1.3