From fc989f4274f02aed8b895dcb9412dad6280ba55f Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 21 Dec 2023 17:45:32 +0100
Subject: Lösungen für Tag 21, Teil 1
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 makefile      |  3 +-
 src/day21.cpp | 97 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 99 insertions(+), 1 deletion(-)
 create mode 100644 src/day21.cpp

diff --git a/makefile b/makefile
index e5149a7..a54e3aa 100644
--- a/makefile
+++ b/makefile
@@ -19,7 +19,8 @@ all: bin/day01 \
 	 bin/day17 \
 	 bin/day18 \
 	 bin/day19 \
-	 bin/day20
+	 bin/day20 \
+	 bin/day21
 
 bin:
 	mkdir $@
diff --git a/src/day21.cpp b/src/day21.cpp
new file mode 100644
index 0000000..91611c5
--- /dev/null
+++ b/src/day21.cpp
@@ -0,0 +1,97 @@
+#include <cstddef>
+#include <fstream>
+#include <iostream>
+#include <queue>
+#include <set>
+#include <string>
+#include <vector>
+using namespace std;
+
+using position = tuple<size_t, size_t>;
+
+vector<string>
+read_file(string_view filename)
+{
+	fstream        input{ filename };
+	vector<string> data;
+
+	for ( string line; getline(input, line); ) {
+		data.emplace_back(line);
+	}
+
+	return data;
+}
+
+position
+find_start_position(const vector<string>& lines)
+{
+	for ( size_t row = 0; row != lines.size(); ++row ) {
+		for ( size_t col = 0; col != lines[row].size(); ++col ) {
+			if ( lines[row][col] == 'S' ) {
+				return { row, col };
+			}
+		}
+	}
+	return {};
+}
+
+set<position>
+find_neighbours(position pos, const vector<string>& lines)
+{
+	static const vector<position> movements = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
+
+	set<position> neighbours;
+	const auto [row, col] = pos;
+
+	for ( const auto& [drow, dcol]: movements ) {
+		const auto nrow = row + drow;
+		const auto ncol = col + dcol;
+
+		if ( nrow < lines.size() && ncol < lines[0].size() && lines[nrow][ncol] == '.' ) {
+			neighbours.emplace(nrow, ncol);
+		}
+	}
+
+	return neighbours;
+}
+
+void
+part1()
+{
+	auto lines          = read_file("data/day21.txt");
+	auto start_position = find_start_position(lines);
+
+	queue<position> positions;
+	positions.emplace(start_position);
+
+	long sum = 0;
+	for ( int round = 0; round != 64; ++round ) {
+		set<position> next_positions;
+
+		sum = 0;
+		while ( !positions.empty() ) {
+			const auto [curr_row, curr_col] = positions.front();
+			lines[curr_row][curr_col]       = '.';
+
+			auto neighbours = find_neighbours(positions.front(), lines);
+			positions.pop();
+
+			for ( const auto& [row, col]: neighbours ) {
+				lines[row][col] = 'O';
+				next_positions.emplace(row, col);
+				++sum;
+			}
+		}
+
+		for ( const auto& position: next_positions ) {
+			positions.emplace(position);
+		}
+	}
+	cout << sum << endl;
+}
+
+int
+main()
+{
+	part1();
+}
-- 
cgit v1.3