Day 12 2024, cleaned up part b

3 files changed, 332 insertions, 0 deletions

diff --git a/2024/12/Makefile b/2024/12/Makefile
new file mode 100644
index 0000000..500a766
--- /dev/null
+++ b/2024/12/Makefile
@@ -0,0 +1,24 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+        ${CC} -o a.out day12a.cpp
+
+b:
+        ${CC} -o b.out day12b.cpp
+
+clean:
+        rm -f a b
+
+atest: a
+        ./a.out
+
+btest: b
+        ./b.out
+
+arun: a
+        ./a.out < input
+
+brun: b
+        ./b.out < input
+
+.PHONY: a b clean atest btest arun brun
diff --git a/2024/12/day12a.cpp b/2024/12/day12a.cpp
new file mode 100644
index 0000000..b972fd2
--- /dev/null
+++ b/2024/12/day12a.cpp
@@ -0,0 +1,149 @@
+/*
+This code is a bit ugly, day12b.cpp contains a nicer implementation
+(the perimeter part is of course different).
+*/
+
+#include <iostream>
+#include <algorithm>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+enum class Direction { U, D, R, L };
+Direction all_directions[] = {
+        Direction::U, Direction::D, Direction::R, Direction::L,
+};
+
+pair<int, int> step(pair<int, int> p, Direction d) {
+        auto [i, j] = p;
+
+        switch (d) {
+        case Direction::U:
+                return make_pair(i-1, j);
+        case Direction::D:
+                return make_pair(i+1, j);
+        case Direction::R:
+                return make_pair(i, j+1);
+        case Direction::L:
+                return make_pair(i, j-1);
+        }
+
+        return make_pair(-999,-999);
+}
+
+class Board {
+public:
+        const char out_of_bound = '$';
+        int M, N;
+
+        Board(vector<string> &lines) {
+                N = lines.size();
+                M = 0;
+                for (string l : lines)
+                        M = max(M, (int)l.size());
+                region = new int[M * N];
+                cells = new char[M * N];
+                for (int i = 0; i < N; i++) {
+                        for (int j = 0; j < M; j++) {
+                                region[N*i + j] = -1;
+                                cells[N*i + j] = j < (int)lines[i].size() ?
+                                    lines[i][j] : out_of_bound;
+                        }
+                }
+                                
+        }
+
+        ~Board() {
+                delete []region;
+                delete []cells;
+        }
+
+        char operator[](pair<int, int> p) {
+                int c = coord(p);
+                return c == -1 ? out_of_bound : cells[c];
+        }
+
+        int& reg(pair<int, int> p) {
+                return region[coord(p)];
+        }
+
+private:
+        char *cells;
+        int *region;
+
+        int coord(pair<int, int> p) {
+                auto [i, j] = p;
+                return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j;
+        }
+};
+
+void fill(pair<int, int> p, char a, int r, Board &board) {
+        if (board[p] != a || board.reg(p) == r)
+                return;
+        board.reg(p) = r;
+
+        fill(step(p, Direction::U), a, r, board);
+        fill(step(p, Direction::D), a, r, board);
+        fill(step(p, Direction::R), a, r, board);
+        fill(step(p, Direction::L), a, r, board);
+}
+
+int cell_perim(Board &board, pair<int, int> p) {
+        int perim = 0;
+        if (board[step(p, Direction::U)] != board[p]) perim++;
+        if (board[step(p, Direction::D)] != board[p]) perim++;
+        if (board[step(p, Direction::R)] != board[p]) perim++;
+        if (board[step(p, Direction::L)] != board[p]) perim++;
+        return perim;
+}
+
+int measure_region(Board &board, int r) {
+        int area = 0;
+        int perim = 0;
+        pair<int, int> p;
+        for (p.first = 0; p.first < board.N; p.first++) {
+                for (p.second = 0; p.second < board.M; p.second++) {
+                        if (board.reg(p) == r) {
+                                area++;
+                                perim += cell_perim(board, p);
+                        }
+                }
+        }
+
+        return area * perim;
+}
+
+int scan(Board &board, int maxr) {
+        int tot = 0;
+        for (int r = 0; r < maxr; r++)
+                tot += measure_region(board, r);
+
+        return tot;
+}
+
+int main() {
+        string line;
+        vector<string> lines;
+        while (getline(cin, line))
+                lines.push_back(line);
+
+        Board board(lines);
+
+        pair<int, int> p;
+        int r = 0;
+        for (p.first = 0; p.first < board.N; p.first++) {
+                for (p.second = 0; p.second < board.M; p.second++) {
+                        if (board.reg(p) == -1) {
+                                fill(p, board[p], r, board);
+                                r++;
+                        }
+                }
+        }
+
+        auto tot = scan(board, r);
+
+        cout << tot << endl;
+
+        return 0;
+}
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;
+}