From 662e2317c7ff77236601c32b3b204fe89ac5cc5d Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 7 Dec 2025 09:30:23 +0100
Subject: aoc 2025, day 7, part 2

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

(limited to '2025')

diff --git a/2025/src/day07.cpp b/2025/src/day07.cpp
index ca73d87..e902a43 100644
--- a/2025/src/day07.cpp
+++ b/2025/src/day07.cpp
@@ -1,6 +1,8 @@
 #include <filesystem>
 #include <fstream>
+#include <functional>
 #include <iostream>
+#include <map>
 #include <set>
 #include <string>
 #include <vector>
@@ -48,6 +50,37 @@ part1(const vector<string>& grid)
 	cout << "Part 1: " << count << '\n';
 }
 
+void
+part2(const vector<string>& grid)
+{
+	using Pos = tuple<size_t, size_t>;
+
+	map<Pos, long>             cache;
+	function<long(const Pos&)> walk = [&](const Pos& pos) {
+		if ( cache.contains(pos) ) {
+			return cache.at(pos);
+		}
+
+		const auto [col, row] = pos;
+
+		if ( row == grid.size() ) {
+			return (cache[pos] = 1L);
+		}
+
+		if ( grid[row][col] == '^' ) {
+			const auto left  = walk({ col - 1, row });
+			const auto right = walk({ col + 1, row });
+
+			return (cache[pos] = left + right);
+		}
+
+		return (cache[pos] = walk({ col, row + 1 }));
+	};
+
+	const auto col = grid[0].find('S');
+	cout << "Part 2: " << walk(Pos{ col, 0 }) << '\n';
+}
+
 } // namespace
 
 int
@@ -55,4 +88,5 @@ main()
 {
 	auto grid = read_file("data/day07.txt");
 	part1(grid);
+	part2(grid);
 }
-- 
cgit v1.3