main.cpp (4001B)
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 <map> 10 #include <thread> 11 #include <future> 12 #include "utils.hpp" 13 14 typedef std::vector<uint64_t> Data; 15 16 template<typename T> 17 T read_file(const std::string &path) { 18 std::ifstream ifs(path, std::ios::binary); 19 if (!ifs.is_open()) { 20 throw std::runtime_error(path+":"+std::strerror(errno)); 21 } 22 T buf; 23 for (std::string str; std::getline(ifs, str, ' ');) { 24 if (!str.empty()) buf.push_back(std::stoi(str)); 25 } 26 return buf; 27 } 28 29 typedef std::tuple<int, uint64_t, uint64_t> Memo; 30 typedef std::map<uint64_t, Memo> Cache; 31 typedef std::map<std::pair<uint64_t, int>, uint64_t> GenCache; 32 33 uint64_t calc(uint64_t stone, int num, Cache &cache, GenCache &genCache) { 34 if (num<=0) return 1; 35 if (genCache.contains(std::make_pair(stone, num))) { 36 return genCache[std::make_pair(stone, num)]; 37 } 38 if (cache.contains(stone)) { 39 auto [blinks, s1, s2] = cache[stone]; 40 if (blinks>num) return 1; 41 else if (s1==0) return 1; 42 uint64_t res = calc(s1, num-blinks, cache, genCache)+calc(s2, num-blinks, cache, genCache); 43 genCache[std::make_pair(stone, num)] = res; 44 return res; 45 } 46 47 uint64_t derived = stone; 48 for (int i=1; i<=num; ++i) { 49 std::string s = std::to_string(derived); 50 if (derived==0) { 51 derived = 1; 52 } else if (s.size()%2==0) { 53 uint64_t n1 = std::stoi(s.substr(0, s.size()/2)); 54 uint64_t n2 = std::stoi(s.substr(s.size()/2, s.size())); 55 cache[stone] = std::make_tuple(i, n1, n2); 56 return calc(n1, num-i, cache, genCache)+calc(n2, num-i, cache, genCache); 57 } else { 58 derived *= 2024; 59 } 60 } 61 genCache[std::make_pair(stone, num)] = 1; 62 return 1; 63 } 64 65 uint64_t blink3(Data &stones, int num) { 66 Cache cache; 67 GenCache genCache; 68 uint64_t result = 0; 69 for (uint64_t s:stones) { 70 result += calc(s, num, cache, genCache); 71 } 72 return result; 73 } 74 75 void blink(Data &stones, int num) { 76 for (int i=0; i<num; ++i) { 77 for (auto it=stones.begin(); it!=stones.end(); ++it) { 78 std::string s = std::to_string(*it); 79 if (*it==0) { 80 *it = 1; 81 } else if (s.size()%2==0) { 82 uint64_t n1 = std::stoi(s.substr(0, s.size()/2)); 83 uint64_t n2 = std::stoi(s.substr(s.size()/2, s.size())); 84 *it = n2; 85 it = stones.insert(it, n1); 86 it++; 87 } else { 88 *it *= 2024; 89 } 90 } 91 } 92 } 93 94 void blink2(uint64_t start, int num, std::promise<uint64_t> &&result) { 95 Data stones; 96 stones.push_back(start); 97 blink(stones, num); 98 result.set_value(stones.size()); 99 } 100 101 [[ maybe_unused ]] void printStones(const Data &stones) { 102 for (auto n:stones) { 103 std::cout << "[" << n << "]"; 104 } 105 std::cout << std::endl; 106 } 107 108 int64_t part1(Data input [[ maybe_unused ]]) { 109 uint64_t sum = 0; 110 std::vector<std::pair<std::jthread, std::future<uint64_t>>> workers; 111 for (uint64_t num:input) { 112 std::pair<std::jthread, std::future<uint64_t>> p; 113 std::promise<uint64_t> pr; 114 p.second = pr.get_future(); 115 p.first = std::jthread(blink2, num, 25, std::move(pr)); 116 workers.push_back(std::move(p)); 117 } 118 for (auto &p:workers) { 119 p.first.join(); 120 sum += p.second.get(); 121 } 122 return sum; 123 } 124 125 int64_t part2(Data input [[ maybe_unused ]]) { 126 return blink3(input, 75); 127 } 128 129 int main(int argc, char **argv) { 130 Performance perf; 131 const std::string fname = argc>1 ? argv[1] : "test1.txt"; 132 std::cout << "AoC 2024 day 11 " << fname << std::endl; 133 Data input = read_file<Data>(fname); 134 std::cout << "part1: " << part1(input) << std::endl; 135 std::cout << "part2: " << part2(input) << std::endl; 136 137 return 0; 138 }