main.cpp (4335B)
1 #include <iostream> 2 #include <filesystem> 3 #include <fstream> 4 #include <vector> 5 #include <cstring> 6 #include <cstdio> 7 #include <tuple> 8 #include <algorithm> 9 #include <expected> 10 #include <set> 11 #include "utils.hpp" 12 13 typedef std::vector<std::string> Data; 14 typedef std::pair<int, int> Vec2; 15 16 static const std::vector<Vec2> sDirs = {Vec2(0, -1), Vec2(1, 0), Vec2(0, 1), Vec2(-1, 0)}; 17 18 class Plot : public std::set<Vec2> { 19 public: 20 bool has(const Vec2 &p) const { 21 return this->count(p)>0; 22 } 23 24 bool addNeighbors(const Data &input, char c) { 25 const int sz = input.size(); 26 bool inserted = false; 27 Plot cp(*this); 28 for (const Vec2 &p : cp) { 29 for (const Vec2 &dir:sDirs) { 30 Vec2 pd(p.first+dir.first, p.second+dir.second); 31 if (pd.first>=0&&pd.first<sz&&pd.second>=0&&pd.second<sz) { 32 if (input[pd.second][pd.first]==c&&!cp.has(pd)) { 33 this->insert(pd); 34 inserted = true; 35 } 36 } 37 } 38 } 39 return inserted; 40 } 41 42 int64_t area() const { return this->size(); } 43 44 int64_t perimeter() const { 45 int64_t per = 0; 46 for (const auto &p : *this) { 47 int64_t cnt = 4; 48 for (const Vec2 &dir:sDirs) { 49 Vec2 pd(p.first+dir.first, p.second+dir.second); 50 if (this->has(pd)) { 51 cnt--; 52 } 53 } 54 per+=cnt; 55 } 56 return per; 57 } 58 59 int64_t sides() const { 60 int64_t cnt = 0; 61 for (const auto &p : *this) { 62 if (!this->has(Vec2(p.first+1, p.second))&&!this->has(Vec2(p.first, p.second-1))) cnt++; 63 if (!this->has(Vec2(p.first+1, p.second))&&!this->has(Vec2(p.first, p.second+1))) cnt++; 64 if (!this->has(Vec2(p.first-1, p.second))&&!this->has(Vec2(p.first, p.second+1))) cnt++; 65 if (!this->has(Vec2(p.first-1, p.second))&&!this->has(Vec2(p.first, p.second-1))) cnt++; 66 67 if (!this->has(Vec2(p.first+1, p.second-1))&&this->has(Vec2(p.first+1, p.second))&&this->has(Vec2(p.first, p.second-1))) cnt++; 68 if (!this->has(Vec2(p.first+1, p.second+1))&&this->has(Vec2(p.first+1, p.second))&&this->has(Vec2(p.first, p.second+1))) cnt++; 69 if (!this->has(Vec2(p.first-1, p.second+1))&&this->has(Vec2(p.first-1, p.second))&&this->has(Vec2(p.first, p.second+1))) cnt++; 70 if (!this->has(Vec2(p.first-1, p.second-1))&&this->has(Vec2(p.first-1, p.second))&&this->has(Vec2(p.first, p.second-1))) cnt++; 71 } 72 return cnt; 73 } 74 75 void print() const { 76 for (auto &p : *this) { 77 std::printf("[%d,%d]", p.first, p.second); 78 } 79 } 80 }; 81 82 template<typename T> 83 T read_file(const std::string &path) { 84 std::ifstream ifs(path, std::ios::binary); 85 if (!ifs.is_open()) { 86 throw std::runtime_error(path+":"+std::strerror(errno)); 87 } 88 T buf; 89 while (1) { 90 std::string str; 91 std::getline(ifs, str); 92 if (!str.empty()) buf.push_back(str); 93 if (!ifs) break; 94 } 95 return buf; 96 } 97 98 Plot findPlot(const Data &input [[ maybe_unused ]], Vec2 start [[ maybe_unused ]]) { 99 Plot plot; 100 char c = input[start.second][start.first]; 101 plot.insert(start); 102 while (plot.addNeighbors(input, c)) {} 103 return plot; 104 } 105 106 std::pair<int64_t, int64_t> solve(Data &input [[ maybe_unused ]]) { 107 int64_t p1sum = 0; 108 int64_t p2sum = 0; 109 // square maps only! 110 Plot processed; 111 for (int y=0; y<(int)input.size(); ++y) { 112 for (int x=0; x<(int)input[y].size(); ++x) { 113 if (!processed.has(Vec2(x, y))) { 114 Plot p = findPlot(input, Vec2(x,y)); 115 processed.insert(p.begin(), p.end()); 116 p1sum += p.area() * p.perimeter(); 117 p2sum += p.area() * p.sides(); 118 } 119 } 120 } 121 122 return std::make_pair(p1sum, p2sum); 123 } 124 125 int main(int argc, char **argv) { 126 Performance perf; 127 const std::string fname = argc>1 ? argv[1] : "test1.txt"; 128 std::cout << "AoC 2024 day 12 " << fname << std::endl; 129 Data input = read_file<Data>(fname); 130 auto [p1, p2] = solve(input); 131 std::cout << "part1: " << p1 << std::endl; 132 std::cout << "part2: " << p2 << std::endl; 133 134 return 0; 135 }