advent2024

main.cpp (5450B)

---

 #include <iostream>
 #include <filesystem>
 #include <fstream>
 #include <vector>
 #include <cstring>
 #include <cstdio>
 #include <tuple>
 #include <algorithm>
 #include <expected>
 #include <set>
 #include "utils.hpp"
 
 typedef std::vector<std::string> Data;
 typedef std::pair<int, int> Vec2;
 
 static const std::vector<Vec2> sDirs = {Vec2(0, -1), Vec2(1, 0), Vec2(0, 1), Vec2(-1, 0)};
 
 
 class Plot : public std::set<Vec2> {
 public:
     bool has(const Vec2 &p) const {
         return this->count(p)>0;
         //std::count(this->begin(), this->end(), p)>0;
     }
 
     bool addNeighbors(const Data &input, char c) {
         const int sz = input.size();
         bool inserted = false;
         Plot cp(*this);
         for (const Vec2 &p : cp) {
             for (const Vec2 &dir:sDirs) {
                 Vec2 pd(p.first+dir.first, p.second+dir.second);
                 if (pd.first>=0&&pd.first<sz&&pd.second>=0&&pd.second<sz) {
                     if (input[pd.second][pd.first]==c&&!cp.has(pd)) {
                         this->insert(pd);
                         inserted = true;
                     }
                 }
             }
         }
         return inserted;
     }
 
     int64_t area() const { return this->size(); }
 
     int64_t perimeter() const {
         int64_t per = 0;
         for (const auto &p : *this) {
             int64_t cnt = 4;
             for (const Vec2 &dir:sDirs) {
                 Vec2 pd(p.first+dir.first, p.second+dir.second);
                 if (this->has(pd)) {
                     cnt--;
                     //std::printf("[%d,%d] has neighbor [%d,%d]\n", p.first, p.second, pd.first, pd.second);
                 }
             }
             //std::printf("(%ld)\n", cnt);
             per+=cnt;
         }
         return per;
     }
 
     int64_t sides() const {
         int64_t cnt = 0;
         std::vector<Vec2> n,e,s,w;
         for (const auto &p : *this) {
             if (!this->has(Vec2(p.first+1, p.second))) e.push_back(p);
             if (!this->has(Vec2(p.first-1, p.second))) w.push_back(p);
             if (!this->has(Vec2(p.first, p.second+1))) s.push_back(p);
             if (!this->has(Vec2(p.first, p.second-1))) n.push_back(p);
         }
         std::sort(n.begin(), n.end(), [](auto &p1, auto &p2){ return p1.second<p2.second/* && p1.first<p2.first*/; });
         std::sort(s.begin(), s.end(), [](auto &p1, auto &p2){ return p1.second<p2.second; });
         std::sort(e.begin(), e.end(), [](auto &p1, auto &p2){ return p1.first<p2.first; });
         std::sort(w.begin(), w.end(), [](auto &p1, auto &p2){ return p1.first<p2.first; });
 
         std::printf("east:");
         for (auto &p:e) {
             std::printf("[%d,%d]", p.first, p.second);
         }
         std::printf("\n");
 
         int v=-1;
         int prev=-1;
         for (auto &p : n) {
             if (p.second!=v || std::abs(prev-p.first)>1) { cnt++; }
             v=p.second;
             prev=p.first;
         }
         v=-1;
         prev=-1;
         for (auto &p : s) {
             if (p.second!=v || std::abs(prev-p.first)>1) cnt++;
             v=p.second;
             prev=p.first;
         }
         v=-1;
         prev=-1;
         for (auto &p : e) {
             if (p.first!=v || std::abs(prev-p.second)>1) cnt++;
             v=p.first;
             prev=p.second;
         }
         std::printf("north+south+east count:%ld\n", cnt);
         v=-1;
         prev=-1;
         for (auto &p : w) {
             if (p.first!=v || std::abs(prev-p.second)>1) cnt++;
             v=p.first;
             prev=p.second;
         }
         return cnt;
     }
 
     void print() const {
         for (auto &p : *this) {
             std::printf("[%d,%d]", p.first, p.second);
         }
     }
 };
 // 1046941 too high
 // 918855 too high
 template<typename T>
 T read_file(const std::string &path) {
     std::ifstream ifs(path, std::ios::binary);
     if (!ifs.is_open()) {
         throw std::runtime_error(path+":"+std::strerror(errno));
     }
     T buf;
     while (1) {
         std::string str;
         std::getline(ifs, str);
         if (!str.empty()) buf.push_back(str);
         if (!ifs) break;
     }
     return buf;
 }
 
 Plot findPlot(const Data &input [[ maybe_unused ]], Vec2 start [[ maybe_unused ]]) {
     Plot plot;
     char c = input[start.second][start.first];
     plot.insert(start);
     while (plot.addNeighbors(input, c)) {}
     return plot;
 }
 
 std::pair<int64_t, int64_t> solve(Data &input [[ maybe_unused ]]) {
     int64_t p1sum = 0;
     int64_t p2sum = 0;
     // square maps only!
     Plot processed;
     for (int y=0; y<(int)input.size(); ++y) {
         for (int x=0; x<(int)input[y].size(); ++x) {
             if (!processed.has(Vec2(x, y))) {
                 Plot p = findPlot(input, Vec2(x,y));
                 processed.insert(p.begin(), p.end());
                 std::printf("\n-------------\nfound plot (%c):\n", input[y][x]);
                 p.print();
                 std::printf("\nsides: %ld\n", p.sides());
                 p1sum += p.area() * p.perimeter();
                 p2sum += p.area() * p.sides();
             }
         }
     }
 
     return std::make_pair(p1sum, p2sum);
 }
 
 int main(int argc, char **argv) {
     Performance perf;
     const std::string fname = argc>1 ? argv[1] : "test1.txt";
     std::cout << "AoC 2024 day 12 " << fname << std::endl;
     Data input = read_file<Data>(fname);
     auto [p1, p2] = solve(input);
     std::cout << "part1: " << p1 << std::endl;
     std::cout << "part2: " << p2 << std::endl;
 
     return 0;
 }