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

---
 src/day21.cpp | 74 +++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 62 insertions(+), 12 deletions(-)

(limited to 'src')

diff --git a/src/day21.cpp b/src/day21.cpp
index 91611c5..740c3ae 100644
--- a/src/day21.cpp
+++ b/src/day21.cpp
@@ -47,7 +47,7 @@ find_neighbours(position pos, const vector<string>& lines)
 		const auto nrow = row + drow;
 		const auto ncol = col + dcol;
 
-		if ( nrow < lines.size() && ncol < lines[0].size() && lines[nrow][ncol] == '.' ) {
+		if ( nrow < lines.size() && ncol < lines[0].size() && (lines[nrow][ncol] == '.' || lines[nrow][ncol] == 'S') ) {
 			neighbours.emplace(nrow, ncol);
 		}
 	}
@@ -55,17 +55,14 @@ find_neighbours(position pos, const vector<string>& lines)
 	return neighbours;
 }
 
-void
-part1()
+size_t
+count(vector<string> lines, position start, size_t rounds)
 {
-	auto lines          = read_file("data/day21.txt");
-	auto start_position = find_start_position(lines);
-
 	queue<position> positions;
-	positions.emplace(start_position);
+	positions.emplace(start);
 
-	long sum = 0;
-	for ( int round = 0; round != 64; ++round ) {
+	size_t sum = 0;
+	for ( size_t round = 0; round != rounds; ++round ) {
 		set<position> next_positions;
 
 		sum = 0;
@@ -73,7 +70,7 @@ part1()
 			const auto [curr_row, curr_col] = positions.front();
 			lines[curr_row][curr_col]       = '.';
 
-			auto neighbours = find_neighbours(positions.front(), lines);
+			const auto neighbours = find_neighbours(positions.front(), lines);
 			positions.pop();
 
 			for ( const auto& [row, col]: neighbours ) {
@@ -87,11 +84,64 @@ part1()
 			positions.emplace(position);
 		}
 	}
-	cout << sum << endl;
+	return sum;
+}
+
+void
+part1(const vector<string>& lines)
+{
+	const auto start = find_start_position(lines);
+	cout << count(lines, start, 64) << endl;
+}
+
+void
+part2(const vector<string>& lines)
+{
+	const auto start      = find_start_position(lines);
+	const auto [row, col] = start;
+
+	const auto pow2 = [](size_t val) -> size_t {
+		return val * val;
+	};
+
+	const auto   size       = lines.size();
+	const size_t steps      = 26501365;
+	const auto   grid_width = steps / size - 1;
+
+	const auto odd  = pow2(grid_width / 2 * 2 + 1);
+	const auto even = pow2((grid_width + 1) / 2 * 2);
+
+	const auto odd_points  = count(lines, start, size * 2 + 1);
+	const auto even_points = count(lines, start, size * 2);
+
+	const auto corner_t = count(lines, { size - 1, col }, size - 1);
+	const auto corner_r = count(lines, { row, 0 }, size - 1);
+	const auto corner_b = count(lines, { 0, col }, size - 1);
+	const auto corner_l = count(lines, { row, size - 1 }, size - 1);
+
+	const auto small_tr = count(lines, { size - 1, 0 }, size / 2 - 1);
+	const auto small_tl = count(lines, { size - 1, size - 1 }, size / 2 - 1);
+	const auto small_br = count(lines, { 0, 0 }, size / 2 - 1);
+	const auto small_bl = count(lines, { 0, size - 1 }, size / 2 - 1);
+
+	const auto large_tr = count(lines, { size - 1, 0 }, size * 3 / 2 - 1);
+	const auto large_tl = count(lines, { size - 1, size - 1 }, size * 3 / 2 - 1);
+	const auto large_br = count(lines, { 0, 0 }, size * 3 / 2 - 1);
+	const auto large_bl = count(lines, { 0, size - 1 }, size * 3 / 2 - 1);
+
+	auto total = odd * odd_points;
+	total += even * even_points;
+	total += corner_t + corner_r + corner_b + corner_l;
+	total += (grid_width + 1) * (small_tr + small_tl + small_br + small_bl);
+	total += grid_width * (large_tr + large_tl + large_br + large_bl);
+
+	cout << total << endl;
 }
 
 int
 main()
 {
-	part1();
+	auto lines = read_file("data/day21.txt");
+	part1(lines);
+	part2(lines);
 }
-- 
cgit v1.3