From 90e31528ce685cb1d6e02baa40fc47ca88c713e0 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 14 Nov 2024 21:25:25 +0100
Subject: aoc 2015, day 9

---
 2015/src/day09.cpp | 102 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 102 insertions(+)
 create mode 100644 2015/src/day09.cpp

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);
+}
-- 
cgit v1.3