day9 done

3 files changed, 69 insertions, 4 deletions

diff --git a/src/2015/day9/README.md b/src/2015/day9/README.md
index 184ff48..8956ab4 100644
--- a/src/2015/day9/README.md
+++ b/src/2015/day9/README.md
@@ -23,3 +23,13 @@ The shortest of these is London -> Dublin -> Belfast = 605, and so the answer is
 
 What is the distance of the shortest route?
 
+--- Part Two ---
+
+The next year, just to show off, Santa decides to take the route with the longest distance instead.
+
+He can still start and end at any two (different) locations he wants, and he still must visit each location exactly once.
+
+For example, given the distances above, the longest route would be 982 via (for example) Dublin -> London -> Belfast.
+
+What is the distance of the longest route?
+
diff --git a/src/2015/day9/aoc.cpp b/src/2015/day9/aoc.cpp
index 8a5f8fd..95d65bb 100644
--- a/src/2015/day9/aoc.cpp
+++ b/src/2015/day9/aoc.cpp
@@ -1,14 +1,23 @@
 #include "aoc.h"
 
 namespace aoc2015 {
-int day9(line_view file) {
+std::pair<int, int> day9(line_view file) {
   world_day9 world;
   per_line(file, [&world](line_view lv) {
     world.parse(lv);
     return true;
   });
-  world.check();
-  return 0;
+  std::pair<int, int> d{INT32_MAX, INT32_MIN};
+  for (auto city : world.locations) {
+    auto p = world.plan(city);
+    if (p.first < d.first) {
+      d.first = p.first;
+    }
+    if (p.second > d.second) {
+      d.second = p.second;
+    }
+  }
+  return d;
 }
 
 } // namespace aoc2015
diff --git a/src/2015/day9/aoc.h b/src/2015/day9/aoc.h
index 2a46bc7..c5daefc 100644
--- a/src/2015/day9/aoc.h
+++ b/src/2015/day9/aoc.h
@@ -1,6 +1,7 @@
 #pragma once
 #include "common.h"
 #include <map>
+#include <set>
 #include <vector>
 
 namespace aoc2015 {
@@ -49,8 +50,53 @@ struct world_day9 {
       }
     }
   }
+
+  // backtrace
+  void plan(location* city, std::set<location*>& visited, std::vector<int>& distances, int* d) {
+    if (visited.size() == locations.size()) {
+      // std::cout << city->name << std::endl;
+      distances.push_back(*d);
+      return;
+    }
+    for (auto& kv : city->routes) {
+      auto it = visited.find(kv.first);
+      if (it != visited.end()) {
+        continue;
+      } else { // not visited
+        // std::cout << city->name << " -> ";
+        location* next = kv.first;
+        visited.insert(next);
+        *d += kv.second;
+        plan(next, visited, distances, d);
+        visited.erase(next);
+        *d -= kv.second;
+      }
+    }
+  }
+
+  std::pair<int, int> minmax(const std::vector<int>& ds) {
+    int d1 = INT32_MAX;
+    int d2 = INT32_MIN;
+    for (auto x : ds) {
+      if (x < d1) {
+        d1 = x;
+      }
+      if (x > d2) {
+        d2 = x;
+      }
+    }
+    return {d1, d2};
+  }
+
+  std::pair<int, int> plan(location* city) {
+    std::vector<int> ds;
+    std::set<location*> visited{city};
+    int d{0};
+    plan(city, visited, ds, &d);
+    return minmax(ds);
+  }
 };
 
-int day9(line_view);
+std::pair<int, int> day9(line_view);
 
 } // namespace aoc2015