aoc 2015, day 9

1 files changed, 102 insertions, 0 deletions

diff --git a/2015/src/day09.cpp b/2015/src/day09.cpp
new file mode 100644
index 0000000..45cd5c4
--- /dev/null
+++ b/2015/src/day09.cpp
@@ -0,0 +1,102 @@
+#include <algorithm>
+#include <fstream>
+#include <iostream>
+#include <limits>
+#include <map>
+#include <sstream>
+#include <string>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+auto
+split(const string& line, char sep)
+{
+        vector<string> parts;
+        stringstream   input{ line };
+
+        for ( string part; getline(input, part, sep); ) {
+                parts.emplace_back(part);
+        }
+
+        return parts;
+}
+
+auto
+read_file(string_view filename)
+{
+        fstream                        input{ filename };
+        map<string, map<string, long>> distances;
+
+        for ( string line; getline(input, line); ) {
+                const auto parts = split(line, ' ');
+
+                distances[parts[0]][parts[2]] = stol(parts[4]);
+                distances[parts[2]][parts[0]] = stol(parts[4]);
+        }
+
+        return distances;
+}
+
+void
+part1(map<string, map<string, long>>& distances)
+{
+        vector<string> vertex;
+
+        vertex.reserve(distances.size());
+        for ( const auto& iter: distances ) {
+                vertex.emplace_back(iter.first);
+        }
+
+        long min_path = numeric_limits<long>::max();
+
+        do {
+                long current_min_path = 0;
+
+                auto start = vertex[0];
+                for ( const auto& ver: vertex ) {
+                        current_min_path += distances[start][ver];
+                        start = ver;
+                }
+
+                min_path = min(min_path, current_min_path);
+        } while ( next_permutation(begin(vertex), end(vertex)) );
+
+        cout << min_path << endl;
+}
+
+void
+part2(map<string, map<string, long>>& distances)
+{
+        vector<string> vertex;
+
+        vertex.reserve(distances.size());
+        for ( const auto& iter: distances ) {
+                vertex.emplace_back(iter.first);
+        }
+
+        long max_path = numeric_limits<long>::min();
+
+        do {
+                long current_max_path = 0;
+
+                auto start = vertex[0];
+                for ( const auto& ver: vertex ) {
+                        current_max_path += distances[start][ver];
+                        start = ver;
+                }
+
+                max_path = max(max_path, current_max_path);
+        } while ( next_permutation(begin(vertex), end(vertex)) );
+
+        cout << max_path << endl;
+}
+
+int
+main()
+{
+        auto distances = read_file("data/day09.txt");
+        part1(distances);
+        part2(distances);
+}