2019 day6 part1

5 files changed, 121 insertions, 1 deletions

diff --git a/src/2019/day6/README.md b/src/2019/day6/README.md
index 12379e0..7e42ae6 100644
--- a/src/2019/day6/README.md
+++ b/src/2019/day6/README.md
@@ -49,4 +49,53 @@ The total number of direct and indirect orbits in this example is 42.
 
 What is the total number of direct and indirect orbits in your map data?
 
+--- Part Two ---
 
+Now, you just need to figure out how many orbital transfers you (YOU) need to take to get to Santa (SAN).
+
+You start at the object YOU are orbiting; your destination is the object SAN is orbiting. An orbital transfer lets you move from any object to an object orbiting or orbited by that object.
+
+For example, suppose you have the following map:
+
+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
+
+Visually, the above map of orbits looks like this:
+
+                          YOU
+                         /
+        G - H       J - K - L
+       /           /
+COM - B - C - D - E - F
+               \
+                I - SAN
+
+In this example, YOU are in orbit around K, and SAN is in orbit around I. To move from K to I, a minimum of 4 orbital transfers are required:
+
+    K to J
+    J to E
+    E to D
+    D to I
+
+Afterward, the map of orbits looks like this:
+
+        G - H       J - K - L
+       /           /
+COM - B - C - D - E - F
+               \
+                I - SAN
+                 \
+                  YOU
+
+What is the minimum number of orbital transfers required to move from the object YOU are orbiting to the object SAN is orbiting? (Between the objects they are orbiting - not between YOU and SAN.)
diff --git a/src/2019/day6/aoc.cpp b/src/2019/day6/aoc.cpp
index f0cbc1b..e0a8cac 100644
--- a/src/2019/day6/aoc.cpp
+++ b/src/2019/day6/aoc.cpp
@@ -1,5 +1,49 @@
 #include "aoc.h"
+#include <unordered_map>
+#include <vector>
 
 namespace aoc2019 {
 
+star* find(std::unordered_map<line_view, star*>& stars, line_view lv) {
+  auto it = stars.find(lv);
+  star* s = nullptr;
+  if (it == stars.end()) {
+    s = new star{lv};
+    stars.insert({lv, s});
+  } else {
+    s = it->second;
+  }
+  // std::cout << s->name << std::endl;
+  return s;
 }
+
+void count(star* s, std::vector<star*>& vs, int* total) {
+  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);
+      vs.pop_back();
+    }
+  }
+  *total += vs.size();
+}
+
+int day6(line_view file) {
+  std::unordered_map<line_view, star*> stars;
+  per_line(file, [&stars](line_view lv) {
+    const char* p = lv.contains(")");
+    star* s1 = find(stars, line_view{lv.line, p});
+    star* s2 = find(stars, line_view{p + 1, lv.line + lv.length - 1});
+    s1->orbits.insert(s2);
+    return true;
+  });
+
+  int total{0};
+  std::vector<star*> vs;
+  count(stars["COM"], vs, &total);
+  return total;
+}
+
+} // namespace aoc2019
diff --git a/src/2019/day6/aoc.h b/src/2019/day6/aoc.h
index 959d6d8..890e495 100644
--- a/src/2019/day6/aoc.h
+++ b/src/2019/day6/aoc.h
@@ -1,6 +1,16 @@
 #pragma once
 #include "common.h"
+#include <set>
 
 namespace aoc2019 {
 
-}
+struct star {
+  line_view name;
+  std::set<star*> orbits = {};
+
+  star(line_view lv): name(lv) {}
+};
+
+int day6(line_view);
+
+} // namespace aoc2019
diff --git a/src/2019/day6/input0 b/src/2019/day6/input0
new file mode 100644
index 0000000..183242d
--- /dev/null
+++ b/src/2019/day6/input0
@@ -0,0 +1,11 @@
+COM)B
+B)C
+C)D
+D)E
+E)F
+B)G
+G)H
+D)I
+E)J
+J)K
+K)L
diff --git a/test/test_2019.cpp b/test/test_2019.cpp
index dfe66ee..30bdd12 100644
--- a/test/test_2019.cpp
+++ b/test/test_2019.cpp
@@ -40,3 +40,9 @@ TEST_CASE("Sunny with a Chance of Asteroids", "[2019]") {
   REQUIRE(6761139 == p.first);
   REQUIRE(9217546 == p.second);
 }
+
+TEST_CASE("Universal Orbit Map", "[2019]") {
+  line_view lv = load_file("../src/2019/day6/input");
+  auto p = aoc2019::day6(lv);
+  REQUIRE(0 == p);
+}