From 118f8d9868c74d27a8a66573e7fbceab835f8bba Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Tue, 10 Dec 2024 18:29:48 +0100
Subject: aoc 2024, day 10, part 2

---
 2024/src/day10.cpp | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 51 insertions(+), 3 deletions(-)

(limited to '2024/src')

diff --git a/2024/src/day10.cpp b/2024/src/day10.cpp
index 43dbd6e..58b797f 100644
--- a/2024/src/day10.cpp
+++ b/2024/src/day10.cpp
@@ -33,10 +33,10 @@ neighbors(pos_type pos)
 	return { { x - 1, y }, { x, y - 1 }, { x + 1, y }, { x, y + 1 } };
 }
 
-long
+size_t
 bfs(const map<pos_type, int>& data, pos_type start_pos)
 {
-	long peaks = 0;
+	size_t peaks = 0;
 
 	set<pos_type>   seen;
 	queue<pos_type> queue;
@@ -77,16 +77,64 @@ part1(const map<pos_type, int>& data)
 		}
 	}
 
-	long sum = 0;
+	size_t sum = 0;
 	for ( const auto& start: starts ) {
 		sum += bfs(data, start);
 	}
 	cout << sum << endl;
 }
 
+size_t
+bfs2(const map<pos_type, int>& data, pos_type start_pos)
+{
+	size_t paths = 0;
+
+	queue<pos_type> queue;
+
+	queue.push(start_pos);
+
+	while ( !queue.empty() ) {
+		auto pos = queue.front();
+		queue.pop();
+
+		if ( data.at(pos) == 9 ) {
+			++paths;
+			continue;
+		}
+
+		for ( const auto& neighbor: neighbors(pos) ) {
+			if ( !data.contains(neighbor) ||
+			     data.at(neighbor) != data.at(pos) + 1 ) {
+				continue;
+			}
+
+			queue.emplace(neighbor);
+		}
+	}
+	return paths;
+}
+
+void
+part2(const map<pos_type, int>& data)
+{
+	vector<pos_type> starts;
+	for ( const auto& [pos, value]: data ) {
+		if ( value == 0 ) {
+			starts.push_back(pos);
+		}
+	}
+
+	size_t sum = 0;
+	for ( const auto& start: starts ) {
+		sum += bfs2(data, start);
+	}
+	cout << sum << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day10.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3