advent2024

main.cpp (4909B)

---

 #include <iostream>
 #include <filesystem>
 #include <fstream>
 #include <vector>
 #include <set>
 #include <cstring>
 #include <cstdio>
 #include <tuple>
 #include <algorithm>
 #include <expected>
 #include <ranges>
 #include <thread>
 
 enum class Dir {
     up,
     down,
     left,
     right
 };
 
 typedef std::vector<std::string> Data;
 typedef std::pair<int,int> Vec2; // x, y
 typedef std::tuple<int,int,Dir> Vec3;
 
 //@todo implement a generic map<width, height> class
 
 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;
 }
 
 std::expected<Vec3, std::string> find_guard(const Data &m) {
     for (int y=0; y<(int)m.size(); ++y) {
         for (int x=0; x<(int)m[y].size(); ++x) {
             if (m[y][x]=='^') return Vec3(x, y, Dir::up);
         }
     }
     return std::unexpected("no guard found");
 }
 
 [[ maybe_unused ]]
 static const char * str(Dir d) {
     switch (d) {
     case Dir::up: return "up";
     case Dir::down: return "down";
     case Dir::left: return "left";
     case Dir::right: return "right";
     }
     return "NULL";
 }
 
 std::expected<Vec3, std::string> get_next(const Data &m, const Vec3 &p) {
     Vec3 np = p;
     auto [x,y,d] = np;
     switch (d) {
     case Dir::up:
         if (y-1>=0) {
             if (m[y-1][x]=='#') {
                 d=Dir::right;
             } else {
                 y--;
             }
         } else {
             return std::unexpected("out");
         }
         break;
     case Dir::down:
         if (y+1<(int)m.size()) {
             if (m[y+1][x]=='#') {
                 d=Dir::left;
             } else {
                 y++;
             }
         } else {
             return std::unexpected("out");
         }
         break;
     case Dir::left:
         if (x-1>=0) {
             if (m[y][x-1]=='#') {
                 d=Dir::up;
             } else {
                 x--;
             }
         } else {
             return std::unexpected("out");
         }
         break;
     case Dir::right:
         if (x+1<(int)m.size()) {
             if (m[y][x+1]=='#') {
                 d=Dir::down;
             } else {
                 x++;
             }
         } else {
             return std::unexpected("out");
         }
         break;
     }
     return Vec3(x,y,d);
 }
 
 // works only on square input
 void traverse(const Data &m, std::vector<Vec3> &visited, const Vec3 &p, bool &loop) {
     visited.push_back(p);
     auto np = get_next(m, p);
     if (np.has_value()) {
         if (std::count(visited.begin(), visited.end(), np.value())>0) {
             loop = true;
         } else {
             traverse(m, visited, np.value(), loop);
         }
     }
 }
 
 [[maybe_unused]] void print_map(const Data &m) {
     std::cout << "---------------------" << std::endl;
     for (auto &s : m) {
         std::cout << s << std::endl;
     }
     std::cout << "---------------------" << std::endl;
 }
 
 Vec2 solve(const Data &input [[ maybe_unused ]]) {
     std::vector<Vec3> visited;
 
     if (auto g=find_guard(input); g.has_value()) {
         bool loop = false;
         traverse(input, visited, g.value(), loop);
     }
 
     std::set<Vec2> p1;
     int p2 = 0;
     for (auto it=visited.begin(); it!=visited.end(); ++it) {
         auto [x, y, d] = *it;
         Vec2 p(x, y);
         p1.insert(p);
         // p2 - put obstacles on every walked tile and traverse everything all over again
         std::vector<Vec3> visited1;
         std::copy(visited.begin(), it+1, std::back_inserter(visited1));
         // obstacle will be placed at the next tile
         Data input1;
         std::copy(input.begin(), input.end(), std::back_inserter(input1));
         auto it1 = it+1;
         if (it1!=visited.end()) {
             auto [x1, y1, d1] = *it1;
             bool on_path = std::count_if(visited1.begin(), visited1.end(), [&x1, &y1](const Vec3 &v1){
                 auto [x2,y2,d2] = v1;
                 return x1==x2 && y1==y2;
             })>0;
             if (input[y1][x1]=='#' || (x==x1&&y==y1) || on_path) {
                 continue;
             }
             input1[y1][x1] = '#';
             bool loop1 = false;
             traverse(input1, visited1, *it, loop1);
             if (loop1) p2++;
         }
     }
 
     return {(int)p1.size(), p2};
 }
 
 int main(int argc, char **argv) {
     const std::string fname = argc>1 ? argv[1] : "test1.txt";
     std::cout << "AoC 2024 day 06 " << 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;
 
     std::cout << std::jthread::hardware_concurrency() << " threads supported" << std::endl;
 
     return 0;
 }