day 16 part 1 partial solution - keeping the path

1 files changed, 102 insertions, 0 deletions

diff --git a/22.16/main.cpp b/22.16/main.cpp
new file mode 100644
index 0000000..8ccabed
--- /dev/null
+++ b/22.16/main.cpp
@@ -0,0 +1,102 @@
+#include <deque>
+#include <iostream>
+#include <string>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+using namespace std;
+
+int parseID(string s) {
+	return (s[0] - 'A') * ('Z' - 'A' + 1) + (s[1] - 'A');
+}
+
+// Fucking hell.
+struct hash_pair {
+	template<typename T1, typename T2>
+	size_t operator()(const pair<T1, T2>& p) const
+	{
+		auto h1 = hash<T1>{}(p.first);
+		auto h2 = hash<T1>{}(p.second);
+		return h1 ^ (h2 << 1);
+	}
+};
+
+struct Graph {
+	unordered_multimap<int, int> conns;
+	unordered_map<int, int> rates;
+
+	unordered_map<pair<int, int>, int, hash_pair> dist;
+};
+
+void findLengths(Graph &g, int base) {
+	deque<int> frontier;
+	frontier.push_back(base);
+	g.dist.insert({{base, base}, 0});
+	while (!frontier.empty()) {
+		// i love c++ i love c++ i love c++
+		int from = frontier.front();
+		int dist = g.dist[{base, from}];
+		frontier.pop_front();
+		auto range = g.conns.equal_range(from);
+		for (auto it = range.first; it != range.second; it++) {
+			int to = it->second;
+			if (g.dist.count({base, to}) != 0)
+				continue;
+			g.dist.insert({{base, to}, dist + 1});
+			frontier.push_back(to);
+		}
+	}
+}
+
+Graph g;
+
+void rec(vector<int> path, vector<int> &avail, int time, int score) {
+	cout << score << "\t" << time << "\t";
+	for (int n : path)
+		cout << n << ",";
+	cout << endl;
+
+	int cur = path.back();
+	for (int i = 0; i < avail.size(); i++) {
+		int n = avail[i];
+		if (n == 0) continue;
+		avail[i] = 0;
+
+		vector<int> path2 = path;
+		path2.push_back(n);
+
+		int time2 = time + g.dist[{cur, n}] + 1;
+		if (30 < time2) continue;
+		int score2 = score + g.rates[n] * (30 - time2);
+
+		rec(path2, avail, time2, score2);
+		avail[i] = n;
+	}
+}
+
+int main() {
+	vector<int> nonzero;
+	for (string s; getline(cin, s); ) {
+		auto numStart = s.find('=') + 1;
+		auto numEnd = s.find(';', numStart) - numStart;
+
+		int from = parseID(s.substr(6, 2));
+		int rate = stoi(s.substr(numStart, numEnd));
+
+		g.rates[from] = rate;
+		if (rate != 0) nonzero.push_back(from);
+
+		s = s.substr(s.find(' ', s.find("valve")) + 1);
+		for (int i = 0; i + 2 <= s.size(); i += 4) {
+			int to = parseID(s.substr(i, 2));
+			g.conns.insert({from, to});
+		}
+	}
+
+	findLengths(g, 0);
+	for (int base : nonzero)
+		findLengths(g, base);
+
+	vector<int> start = {0};
+	rec(start, nonzero, 0, 0);
+}