From 5a17843904394e73f5ae7001dd5f22b7491f6bb9 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 14 Dec 2024 13:39:07 +0100
Subject: aoc 2024, day 14, flood fill :)

---
 2024/src/day14.cpp | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)

(limited to '2024')

diff --git a/2024/src/day14.cpp b/2024/src/day14.cpp
index 97e5fab..aa014e6 100644
--- a/2024/src/day14.cpp
+++ b/2024/src/day14.cpp
@@ -1,6 +1,8 @@
+#include <cstddef>
 #include <fstream>
 #include <iostream>
 #include <map>
+#include <queue>
 #include <regex>
 #include <set>
 #include <tuple>
@@ -166,6 +168,66 @@ part2_alternative(vector<tuple<pos_type, velo_type>> robots, long width, long he
 	}
 }
 
+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 } };
+}
+
+size_t
+flood_fill(const vector<tuple<pos_type, velo_type>>& robots)
+{
+	set<pos_type> positions;
+	for ( const auto& [pos, velo]: robots ) {
+		positions.insert(pos);
+	}
+
+	size_t max_seen = 0;
+	for ( const auto& start: positions ) {
+		set<pos_type> seen;
+
+		queue<pos_type> queue;
+		queue.push(start);
+
+		while ( !queue.empty() ) {
+			auto pos = queue.front();
+			queue.pop();
+
+			if ( seen.contains(pos) ) {
+				continue;
+			}
+
+			seen.insert(pos);
+
+			for ( const auto& neighbor: neighbors(pos) ) {
+				if ( positions.contains(neighbor) ) {
+					queue.push(neighbor);
+				}
+			}
+		}
+		max_seen = max(max_seen, seen.size());
+	}
+
+	return max_seen;
+}
+
+void
+part2_flood_fill(vector<tuple<pos_type, velo_type>> robots, long width, long height)
+{
+	size_t max_count    = 0;
+	long   second_found = 0;
+	for ( long second = 0; second != 100000; ++second ) {
+		auto count = flood_fill(robots);
+		if ( count > max_count ) {
+			max_count    = count;
+			second_found = second;
+		}
+		move(robots, width, height);
+	}
+	cout << second_found << endl;
+}
+
 int
 main()
 {
@@ -177,5 +239,6 @@ main()
 	part1(robots, 101, 103);
 	part2(robots, 101, 103);
 	part2_alternative(robots, 101, 103);
+	part2_flood_fill(robots, 101, 103);
 #endif
 }
-- 
cgit v1.3