From b3fc02c96b041e17ce2d0119b3900a97e9ec7cc0 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 4 Dec 2025 18:18:14 +0100
Subject: aoc 2025, day 4, added optimized version

---
 2025/src/day04.cpp | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)

diff --git a/2025/src/day04.cpp b/2025/src/day04.cpp
index ef3b7f5..75c86d9 100644
--- a/2025/src/day04.cpp
+++ b/2025/src/day04.cpp
@@ -94,6 +94,46 @@ part2(set<Pos> grid)
 	cout << "Part 2: " << old_size - grid.size() << '\n';
 }
 
+void
+part2_bfs(set<Pos> grid)
+{
+	const auto old_size = grid.size();
+
+	map<Pos, size_t> counts;
+	for ( const auto& pos: grid ) {
+		counts[pos] = get_nneighbours(grid, pos);
+	}
+
+	queue<Pos> queue;
+	for ( const auto& [pos, count]: counts ) {
+		if ( count < 4 ) {
+			queue.emplace(pos);
+		}
+	}
+
+	while ( !queue.empty() ) {
+		const auto pos = queue.front();
+		queue.pop();
+
+		if ( !grid.contains(pos) ) {
+			continue;
+		}
+
+		grid.erase(pos);
+
+		for ( const auto& neighbour: get_neighbours(pos) ) {
+			if ( !grid.contains(neighbour) ) {
+				continue;
+			}
+			if ( --counts[neighbour] == 3 ) {
+				queue.emplace(neighbour);
+			}
+		}
+	}
+
+	cout << "Part 2: " << old_size - grid.size() << '\n';
+}
+
 } // namespace
 
 int
@@ -102,4 +142,5 @@ main()
 	auto grid = read_file("data/day04.txt");
 	part1(grid);
 	part2(grid);
+	part2_bfs(grid);
 }
-- 
cgit v1.3