1 files changed, 194 insertions, 0 deletions

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';
+        }
+}