main.cpp (2533B)
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 <set> 10 #include "utils.hpp" 11 12 typedef std::pair<int, int> Vec2; 13 typedef std::vector<std::string> Data; 14 15 template<typename T> 16 T read_file(const std::string &path) { 17 std::ifstream ifs(path, std::ios::binary); 18 if (!ifs.is_open()) { 19 throw std::runtime_error(path+":"+std::strerror(errno)); 20 } 21 T buf; 22 while (1) { 23 std::string str; 24 std::getline(ifs, str); 25 if (!str.empty()) buf.push_back(str); 26 if (!ifs) break; 27 } 28 return buf; 29 } 30 31 std::vector<Vec2> findTrailheads(const Data &input) { 32 std::vector<Vec2> out; 33 for (int y=0; y<(int)input.size(); ++y) { 34 for (int x=0; x<(int)input[y].size(); ++x) { 35 if (input[y][x]=='0') { 36 out.push_back(Vec2(x, y)); 37 } 38 } 39 } 40 return out; 41 } 42 43 // works only with square maps 44 void findTrail(const Data &input, const Vec2 &start, std::set<Vec2> &nines, int &rating) { 45 static const std::vector<Vec2> dirs = {Vec2(0, -1), Vec2(1, 0), Vec2(0, 1), Vec2(-1, 0)}; 46 static const int sz = input.size(); 47 for (auto &d:dirs) { 48 Vec2 p(start.first+d.first, start.second+d.second); // boundaries 49 if (p.first>=0&&p.first<sz&&p.second>=0&&p.second<sz) { 50 char h1 = input[start.second][start.first]; 51 char h2 = input[p.second][p.first]; 52 if (h2-h1==1) { 53 if (h2=='9') { 54 rating++; 55 nines.insert(p); 56 } else { 57 findTrail(input, p, nines, rating); 58 } 59 } 60 } 61 } 62 } 63 64 std::pair<int64_t, int64_t> solve(Data &input [[ maybe_unused ]]) { 65 std::vector<Vec2> trailheads = findTrailheads(input); 66 int count = 0; 67 int rating = 0; 68 for (auto &t:trailheads) { 69 std::set<Vec2> nines; 70 int localRating = 0; 71 findTrail(input, t, nines, localRating); 72 count += nines.size(); 73 rating += localRating; 74 } 75 76 return std::make_pair(count, rating); 77 } 78 79 int main(int argc, char **argv) { 80 Performance perf; 81 const std::string fname = argc>1 ? argv[1] : "test1.txt"; 82 std::cout << "AoC 2024 day 10 " << fname << std::endl; 83 Data input = read_file<Data>(fname); 84 auto [score, rating] = solve(input); 85 std::cout << "part1: " << score << std::endl; 86 std::cout << "part2: " << rating << std::endl; 87 88 return 0; 89 }