2018 day7 part1

3 files changed, 82 insertions, 1 deletions

diff --git a/src/2018/day7/aoc.cpp b/src/2018/day7/aoc.cpp
index e879fb5..6210814 100644
--- a/src/2018/day7/aoc.cpp
+++ b/src/2018/day7/aoc.cpp
@@ -1,4 +1,25 @@
 #include "aoc.h"
 
 namespace aoc2018 {
+std::map<char, instruction*> instruction::instructions = {};
+
+void day7(line_view file, char sequence[]) {
+  per_line(file, [](line_view lv) {
+    char p1 = *(lv.line + 5);
+    char p2 = *(lv.line + 36);
+    instruction* i1 = instruction::make(p1);
+    instruction* i2 = instruction::make(p2);
+    i2->add_dependency(i1);
+    return true;
+  });
+
+  instruction* n = instruction::next();
+  int i{0};
+  while (n != nullptr) {
+    sequence[i++] = n->label;
+    n->make_done();
+    n = instruction::next();
+  }
 }
+
+} // namespace aoc2018
diff --git a/src/2018/day7/aoc.h b/src/2018/day7/aoc.h
index bd2634a..25d127d 100644
--- a/src/2018/day7/aoc.h
+++ b/src/2018/day7/aoc.h
@@ -1,5 +1,58 @@
 #pragma once
 #include "common.h"
+#include <map>
+#include <set>
 
 namespace aoc2018 {
-}
+
+struct instruction {
+  static std::map<char, instruction*> instructions;
+
+  static instruction* make(char x) {
+    auto it = instructions.find(x);
+    if (it == instructions.end()) {
+      auto p = instructions.insert({x, new instruction{x, false, {}}});
+      return p.first->second;
+    }
+    return it->second;
+  }
+
+  static instruction* next() {
+    instruction* n = nullptr;
+    for (auto& kv : instructions) {
+      if (kv.second->ready()) {
+        if (n == nullptr) {
+          n = kv.second;
+        } else {
+          if (*kv.second < *n) {
+            n = kv.second;
+          }
+        }
+      }
+    }
+    return n; // if nullptr all done
+  }
+
+  char label;
+  bool done;
+  std::set<instruction*> deps;
+
+  void add_dependency(instruction* x) noexcept { deps.insert(x); }
+  void make_done() noexcept { done = true; }
+  bool operator<(const instruction& other) const noexcept { return label < other.label; }
+
+  bool ready(const std::set<instruction*> ds) const noexcept {
+    for (auto& i : ds) {
+      if (!i->done) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  bool ready() const noexcept { return !done && (deps.empty() || ready(deps)); }
+};
+
+void day7(line_view, char[]);
+
+} // namespace aoc2018
diff --git a/src/2018/day7/input0 b/src/2018/day7/input0
new file mode 100644
index 0000000..9ab25bf
--- /dev/null
+++ b/src/2018/day7/input0
@@ -0,0 +1,7 @@
+Step C must be finished before step A can begin.
+Step C must be finished before step F can begin.
+Step A must be finished before step B can begin.
+Step A must be finished before step D can begin.
+Step B must be finished before step E can begin.
+Step D must be finished before step E can begin.
+Step F must be finished before step E can begin.