From df47c6d9dae41768a0b4f25a0e16a296ce3bbef7 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Tue, 10 Dec 2024 17:26:41 +0100
Subject: aoc 2024, day 10, part 1

---
 2024/src/day10.cpp | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)
 create mode 100644 2024/src/day10.cpp

(limited to '2024/src/day10.cpp')

diff --git a/2024/src/day10.cpp b/2024/src/day10.cpp
new file mode 100644
index 0000000..43dbd6e
--- /dev/null
+++ b/2024/src/day10.cpp
@@ -0,0 +1,92 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+#include <tuple>
+#include <vector>
+using namespace std;
+
+using pos_type = tuple<size_t, size_t>;
+
+map<pos_type, int>
+read_file(string_view filename)
+{
+	fstream            input{ filename };
+	map<pos_type, int> data;
+
+	size_t yPos = 0;
+	for ( string line; getline(input, line); ) {
+		for ( size_t xPos = 0; xPos != line.size(); ++xPos ) {
+			data[{ xPos, yPos }] = line.at(xPos) - '0';
+		}
+		++yPos;
+	}
+	return data;
+}
+
+constexpr vector<pos_type>
+neighbors(pos_type pos)
+{
+	const auto [x, y] = pos;
+	return { { x - 1, y }, { x, y - 1 }, { x + 1, y }, { x, y + 1 } };
+}
+
+long
+bfs(const map<pos_type, int>& data, pos_type start_pos)
+{
+	long peaks = 0;
+
+	set<pos_type>   seen;
+	queue<pos_type> queue;
+
+	queue.emplace(start_pos);
+	seen.emplace(start_pos);
+
+	while ( !queue.empty() ) {
+		auto pos = queue.front();
+		queue.pop();
+
+		if ( data.at(pos) == 9 ) {
+			++peaks;
+			continue;
+		}
+
+		for ( const auto& neighbor: neighbors(pos) ) {
+			if ( !data.contains(neighbor) ||
+			     seen.contains(neighbor) ||
+			     data.at(neighbor) != data.at(pos) + 1 ) {
+				continue;
+			}
+
+			queue.emplace(neighbor);
+			seen.insert(neighbor);
+		}
+	}
+	return peaks;
+}
+
+void
+part1(const map<pos_type, int>& data)
+{
+	vector<pos_type> starts;
+	for ( const auto& [pos, value]: data ) {
+		if ( value == 0 ) {
+			starts.push_back(pos);
+		}
+	}
+
+	long sum = 0;
+	for ( const auto& start: starts ) {
+		sum += bfs(data, start);
+	}
+	cout << sum << endl;
+}
+
+int
+main()
+{
+	auto data = read_file("data/day10.txt");
+	part1(data);
+}
-- 
cgit v1.3