From 4b7c6b8ca879af5cefda89dcefd9cffd2f35741a Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 12 Dec 2024 23:24:45 +0100
Subject: aoc 2024, day 12, part 2

---
 2024/src/day12.cpp | 93 ++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 69 insertions(+), 24 deletions(-)

(limited to '2024/src')

diff --git a/2024/src/day12.cpp b/2024/src/day12.cpp
index 6a23730..018797f 100644
--- a/2024/src/day12.cpp
+++ b/2024/src/day12.cpp
@@ -8,7 +8,9 @@
 #include <vector>
 using namespace std;
 
-using pos_type = tuple<size_t, size_t>;
+using pos_type   = tuple<size_t, size_t>;
+using area_type  = set<pos_type>;
+using areas_type = vector<area_type>;
 
 map<pos_type, char>
 read_file(string_view filename)
@@ -33,69 +35,112 @@ neighbors(pos_type pos)
 	return { { x - 1, y }, { x, y - 1 }, { x + 1, y }, { x, y + 1 } };
 }
 
-void
-part1(const map<pos_type, char>& data)
+areas_type
+areas(map<pos_type, char> data)
 {
-	auto data_copy = data;
-
-	auto flood_fill = [&](pos_type start) {
+	auto find_area = [&](pos_type start) {
 		set<pos_type>   area;
 		queue<pos_type> queue;
 		queue.push(start);
 
+		const auto digit = data.at(start);
+
 		while ( !queue.empty() ) {
 			auto pos = queue.front();
 			queue.pop();
 
-			if ( !data_copy.contains(pos) ) {
+			if ( !data.contains(pos) ) {
 				continue;
 			}
 
-			auto digit = data_copy.at(pos);
-
 			for ( const auto& neighbor: neighbors(pos) ) {
-				if ( !data_copy.contains(neighbor) ) {
+				if ( !data.contains(neighbor) ) {
 					continue;
 				}
-				if ( data_copy.at(neighbor) != digit ) {
+				if ( data.at(neighbor) != digit ) {
 					continue;
 				}
 				queue.push(neighbor);
 			}
 
 			area.insert(pos);
-			data_copy.erase(pos);
+			data.erase(pos);
 		}
 		return area;
 	};
 
-	auto count_edges = [](const set<pos_type>& area) -> size_t {
-		size_t sum = 0;
+	areas_type areas;
+	while ( !data.empty() ) {
+		auto area = find_area(data.begin()->first);
+		areas.push_back(area);
+	}
+	return areas;
+}
 
-		for ( const auto& pos: area ) {
-			for ( const auto& neighbor: neighbors(pos) ) {
-				if ( !area.contains(neighbor) ) {
-					++sum;
-				}
+size_t
+count_edges(const set<pos_type>& area)
+{
+	size_t sum = 0;
+	for ( const auto& pos: area ) {
+		for ( const auto& neighbor: neighbors(pos) ) {
+			if ( !area.contains(neighbor) ) {
+				++sum;
 			}
 		}
+	}
+	return sum;
+}
 
-		return sum;
-	};
+size_t
+count_common_sides(const set<pos_type>& area)
+{
+	size_t count = 0;
+	for ( const auto& [x, y]: area ) {
+		if ( area.contains({ x - 1, y }) ) {
+			for ( const auto y2: { y - 1, y + 1 } ) {
+				if ( !area.contains({ x, y2 }) && !area.contains({ x - 1, y2 }) ) {
+					++count;
+				}
+			}
+		}
+		if ( area.contains({ x, y - 1 }) ) {
+			for ( const auto x2: { x - 1, x + 1 } ) {
+				if ( !area.contains({ x2, y }) && !area.contains({ x2, y - 1 }) ) {
+					++count;
+				}
+			}
+		}
+	}
+	return count;
+}
 
+void
+part1(const map<pos_type, char>& data)
+{
 	size_t sum = 0;
-	while ( !data_copy.empty() ) {
-		auto area  = flood_fill(data_copy.begin()->first);
+	for ( const auto& area: areas(data) ) {
 		auto edges = count_edges(area);
-
 		sum += area.size() * edges;
 	}
 	cout << sum << endl;
 }
 
+void
+part2(const map<pos_type, char>& data)
+{
+	size_t sum = 0;
+	for ( const auto& area: areas(data) ) {
+		auto edges        = count_edges(area);
+		auto common_sides = count_common_sides(area);
+		sum += area.size() * (edges - common_sides);
+	}
+	cout << sum << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day12.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3