From b3dd0ea6decb1568570a2ebd8491fcd06919886e Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 11 Dec 2025 18:19:31 +0100
Subject: aoc 2025, day 11, alternative solution for part 2

---
 2025/src/day11.cpp | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)

(limited to '2025/src')

diff --git a/2025/src/day11.cpp b/2025/src/day11.cpp
index 1bf8d44..dc05ae3 100644
--- a/2025/src/day11.cpp
+++ b/2025/src/day11.cpp
@@ -99,6 +99,39 @@ part2(const Graph& graph)
 	cout << "Part 2: " << dfs("svr", false, false) << '\n';
 }
 
+void
+part2_alt(const Graph& graph)
+{
+	map<tuple<string, string>, long> cache;
+
+	function<long(const string&, const string&)> dfs = [&](const string& src, const string& dst) {
+		if ( src == dst ) {
+			return 1L;
+		}
+
+		const auto args = make_tuple(src, dst);
+
+		if ( cache.contains(args) ) {
+			return cache.at(args);
+		}
+
+		long count = 0;
+		if ( graph.contains(src) ) {
+			for ( const auto& node: graph.at(src) ) {
+				count += dfs(node, dst);
+			}
+		}
+		return cache[args] = count;
+	};
+
+	// clang-format off
+	const auto total = (dfs("svr", "dac") * dfs("dac", "fft") * dfs("fft", "out"))
+	                 + (dfs("svr", "fft") * dfs("fft", "dac") * dfs("dac", "out"));
+	// clang-format on
+
+	cout << "Part 2 (alternative): " << total << '\n';
+}
+
 } // namespace
 
 int
@@ -107,4 +140,5 @@ main()
 	auto graph = read_file("data/day11.txt");
 	part1(graph);
 	part2(graph);
+	part2_alt(graph);
 }
-- 
cgit v1.3