2019 day6

4 files changed, 53 insertions, 8 deletions

diff --git a/src/2019/day6/aoc.cpp b/src/2019/day6/aoc.cpp
index e0a8cac..9ac3f98 100644
--- a/src/2019/day6/aoc.cpp
+++ b/src/2019/day6/aoc.cpp
@@ -1,4 +1,5 @@
 #include "aoc.h"
+#include <algorithm>
 #include <unordered_map>
 #include <vector>
 
@@ -17,20 +18,43 @@ star* find(std::unordered_map<line_view, star*>& stars, line_view lv) {
   return s;
 }
 
-void count(star* s, std::vector<star*>& vs, int* total) {
-  std::cout << s->name << std::endl;
+void count(star* s, std::vector<star*>& vs, int* total, std::vector<star*>& v1, std::vector<star*>& v2) {
+  // std::cout << s->name << std::endl;
   if (s->orbits.size() > 0) {
     std::vector<star*> orbits{s->orbits.begin(), s->orbits.end()};
     for (auto& x : orbits) {
       vs.push_back(x);
-      count(x, vs, total);
+      count(x, vs, total, v1, v2);
       vs.pop_back();
     }
   }
+  if (s->name == "YOU") {
+    v1 = vs;
+  }
+  if (s->name == "SAN") {
+    v2 = vs;
+  }
   *total += vs.size();
 }
 
-int day6(line_view file) {
+void check(std::vector<star*> vs) {
+  std::for_each(vs.begin(), vs.end(), [](star* s) { std::cout << s->name << " <- "; });
+  std::cout << std::endl;
+}
+
+template <typename T>
+static size_t common(const std::vector<T>& v1, const std::vector<T>& v2) {
+  size_t i{0};
+  while (i < v1.size() && i < v2.size()) {
+    if (v1[i] != v2[i]) {
+      return i;
+    }
+    i++;
+  }
+  return i;
+}
+
+std::pair<int, int> day6(line_view file) {
   std::unordered_map<line_view, star*> stars;
   per_line(file, [&stars](line_view lv) {
     const char* p = lv.contains(")");
@@ -42,8 +66,15 @@ int day6(line_view file) {
 
   int total{0};
   std::vector<star*> vs;
-  count(stars["COM"], vs, &total);
-  return total;
+  std::vector<star*> v1;
+  std::vector<star*> v2;
+  count(stars["COM"], vs, &total, v1, v2);
+  // check(v1);
+  // check(v2);
+
+  // printf("%zu %zu %zu\n", common(v1, v2), v1.size(), v2.size());
+  size_t c = common(v1, v2);
+  return {total, (v1.size() - c - 1) + (v2.size() - c - 1)};
 }
 
 } // namespace aoc2019
diff --git a/src/2019/day6/aoc.h b/src/2019/day6/aoc.h
index 890e495..98c05b7 100644
--- a/src/2019/day6/aoc.h
+++ b/src/2019/day6/aoc.h
@@ -11,6 +11,6 @@ struct star {
   star(line_view lv): name(lv) {}
 };
 
-int day6(line_view);
+std::pair<int, int> day6(line_view);
 
 } // namespace aoc2019
diff --git a/src/2019/day6/input1 b/src/2019/day6/input1
new file mode 100644
index 0000000..a1007c6
--- /dev/null
+++ b/src/2019/day6/input1
@@ -0,0 +1,13 @@
+COM)B
+B)C
+C)D
+D)E
+E)F
+B)G
+G)H
+D)I
+E)J
+J)K
+K)L
+K)YOU
+I)SAN
diff --git a/test/test_2019.cpp b/test/test_2019.cpp
index 30bdd12..a591c94 100644
--- a/test/test_2019.cpp
+++ b/test/test_2019.cpp
@@ -44,5 +44,6 @@ TEST_CASE("Sunny with a Chance of Asteroids", "[2019]") {
 TEST_CASE("Universal Orbit Map", "[2019]") {
   line_view lv = load_file("../src/2019/day6/input");
   auto p = aoc2019::day6(lv);
-  REQUIRE(0 == p);
+  REQUIRE(312697 == p.first);
+  REQUIRE(466 == p.second);
 }