From ec95deb6f565d7994876932834489e7a22e19e11 Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 13 Dec 2024 10:28:14 +0100
Subject: Day 12 2024, cleaned up part b

---
 2024/12/day12b.cpp | 159 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 159 insertions(+)
 create mode 100644 2024/12/day12b.cpp

(limited to '2024/12/day12b.cpp')

diff --git a/2024/12/day12b.cpp b/2024/12/day12b.cpp
new file mode 100644
index 0000000..4078fa7
--- /dev/null
+++ b/2024/12/day12b.cpp
@@ -0,0 +1,159 @@
+#include <iostream>
+#include <cstdint>
+#include <algorithm>
+#include <string>
+#include <string_view>
+#include <vector>
+#include <set>
+using namespace std;
+
+class Direction {
+public:
+	const int U, R;
+
+	Direction(const int i, const int j) : U{ i }, R{ j } {}
+
+	Direction turnright() const {
+		return turn(-1, 0);
+	}
+
+	Direction turnleft() const {
+		return turn(1, 0);
+	}
+
+	bool operator<(const Direction& d) const { // For set<Direction>
+		return this->U < d.U || (this->U == d.U && this->R < d.R);
+	}
+private:
+	Direction turn(int64_t sin, int64_t cos) const {
+		return Direction(cos * U - sin * R, sin * U + cos * R);
+	}
+};
+
+class Position {
+public:
+	int64_t i, j;
+
+	Position(int64_t a, int64_t b) : i{a}, j{b} {}
+
+	Position step(const Direction d) const {
+		return Position(i+d.U, j+d.R);
+	}
+};
+
+const Direction all_directions[] = {
+	Direction(1, 0), Direction(-1, 0), Direction(0, 1), Direction(0, -1)
+};
+
+class Board {
+public:
+	int64_t N, M;
+	vector<int64_t> region_area;
+
+	Board(const vector<string>& lines) :
+	N{static_cast<int64_t>(lines.size())},
+	M{static_cast<int64_t>(lines[0].size())},
+	region_area(M*N), cells(M*N), region(M*N), visited(M*N)
+	{
+		for (int64_t i = 0; i < N; i++) {
+			for (int64_t j = 0; j < M; j++) {
+				region[N*i+j] = -1;
+				cells[N*i+j] = lines[i][j];
+			}
+		}
+	}
+
+	char& operator[](const Position p) {
+		if (const auto c = coord(p); c == -1)
+			return out_of_bound;
+		else
+			return cells[c];
+	}
+
+	int64_t& reg(const Position p) {
+		if (const auto c = coord(p); c == -1)
+			return out_of_region;
+		else
+			return region[c];
+	}
+
+	void fill(const Position p, const int64_t r) {
+		reg(p) = r;
+		region_area[r]++;
+		for (const auto d : all_directions)
+			if (auto q = p.step(d);
+			    (*this)[q] == (*this)[p] && reg(q) != r)
+				fill(q, r);
+	}
+
+	int64_t compute_perim(int64_t r) {
+		int count = 0;
+		for (Position p(0, 0); p.i < N; p.i++)
+			for (p.j = 0; p.j < M; p.j++)
+				for (Direction d : all_directions)
+					if (reg(p) == r && reg(p.step(d)) != r)
+						  count += walk(p, d);
+
+		return count;
+	}
+
+private:
+	char out_of_bound = '$';
+	int64_t out_of_region = -1;
+
+	vector<char> cells;
+	vector<int64_t> region;
+	vector<set<Direction>> visited;
+
+	int64_t coord(const Position p) const {
+		auto [i, j] = p;
+		return i >= N || i < 0 || j >= M || j < 0 ? -1 : N * i + j;
+	}
+
+	bool is_visited(const Position p, const Direction d) const {
+		if (auto c = coord(p); c == -1)
+			return false;
+		else
+			return visited[c].count(d) > 0;
+	}
+
+	void set_visited(const Position p, const Direction d) {
+		if (auto c = coord(p); c != -1)
+			visited[c].insert(d);
+	}
+
+	int64_t walk(const Position p, const Direction d) {
+		const auto r = reg(p);
+		for (auto q = p; reg(q) == r && reg(q.step(d)) != r;
+		    q = q.step(d.turnleft())) {
+			if (is_visited(q, d))
+				return 0;
+			set_visited(q, d);
+		}
+
+		return 1;
+	}
+};
+
+int main() {
+	string line;
+	vector<string> lines;
+	while (getline(cin, line))
+		lines.push_back(line);
+
+	Board board(lines);
+
+	int64_t r = 0;
+	for (Position p(0, 0); p.i < board.N; p.i++)
+		for (p.j = 0; p.j < board.M; p.j++)
+			if (board.reg(p) == -1)
+				board.fill(p, r++);
+
+	int64_t tot = 0;
+	for (int64_t i = 0; i < r; i++)
+		tot += board.region_area[i] * board.compute_perim(i);
+
+	cout << tot << endl;
+
+	return 0;
+}
-- 
cgit v1.3