From 353dfada9165d80eedbc50223b23e813bec401f2 Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Fri, 16 Dec 2022 13:21:48 +0100
Subject: day 16 part 1

---
 22.16/main.cpp | 25 +++++++++----------------
 1 file changed, 9 insertions(+), 16 deletions(-)

(limited to '22.16/main.cpp')

diff --git a/22.16/main.cpp b/22.16/main.cpp
index 8ccabed..9f7641a 100644
--- a/22.16/main.cpp
+++ b/22.16/main.cpp
@@ -1,3 +1,4 @@
+#include <algorithm>
 #include <deque>
 #include <iostream>
 #include <string>
@@ -50,28 +51,21 @@ void findLengths(Graph &g, int base) {
 
 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();
+int rec(int cur, vector<int> &avail, int time, int score) {
+	int best = score;
 	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);
+		if (time2 < 30) {
+			int score2 = score + g.rates[n] * (30 - time2);
+			best = max(best, rec(n, avail, time2, score2));
+		}
 		avail[i] = n;
 	}
+	return best;
 }
 
 int main() {
@@ -97,6 +91,5 @@ int main() {
 	for (int base : nonzero)
 		findLengths(g, base);
 
-	vector<int> start = {0};
-	rec(start, nonzero, 0, 0);
+	cout << rec(0, nonzero, 0, 0) << endl;
 }
-- 
cgit 1.4.1-2-gfad0