From ec95deb6f565d7994876932834489e7a22e19e11 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 13 Dec 2024 10:28:14 +0100 Subject: Day 12 2024, cleaned up part b --- 2024/12/Makefile | 24 ++++++++ 2024/12/day12a.cpp | 149 +++++++++++++++++++++++++++++++++++++++++++++++++ 2024/12/day12b.cpp | 159 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 332 insertions(+) create mode 100644 2024/12/Makefile create mode 100644 2024/12/day12a.cpp create mode 100644 2024/12/day12b.cpp (limited to '2024') 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 +#include +#include +#include +#include +using namespace std; + +enum class Direction { U, D, R, L }; +Direction all_directions[] = { + Direction::U, Direction::D, Direction::R, Direction::L, +}; + +pair step(pair 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 &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 p) { + int c = coord(p); + return c == -1 ? out_of_bound : cells[c]; + } + + int& reg(pair p) { + return region[coord(p)]; + } + +private: + char *cells; + int *region; + + int coord(pair p) { + auto [i, j] = p; + return i >= N || i < 0 || j >= M || j < 0 ? -1 : N*i + j; + } +}; + +void fill(pair 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 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 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 lines; + while (getline(cin, line)) + lines.push_back(line); + + Board board(lines); + + pair 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 +#include +#include +#include +#include +#include +#include +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 + 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 region_area; + + Board(const vector& lines) : + N{static_cast(lines.size())}, + M{static_cast(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 cells; + vector region; + vector> 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 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