main.cpp (5937B)
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 <cmath> 10 #include <climits> 11 #include <thread> 12 #include <future> 13 #include "utils.hpp" 14 15 typedef std::vector<std::pair<int, int>> Data; 16 17 class Cpu { 18 public: 19 // instruction pointer 20 int ip = 0; 21 // registers 22 int64_t a = 0; 23 int64_t b = 0; 24 int64_t c = 0; 25 // combo operand 26 int64_t combo(int o) { 27 if (o>=0&&o<=3) return o; 28 if (o==4) return a; 29 if (o==5) return b; 30 if (o==6) return c; 31 std::printf("invalid combo operand %d\n", o); 32 return 0; 33 } 34 // opcodes 0-7 35 int adv(int64_t o) { a /= std::pow(2, combo(o)); return ++ip; } 36 int bxl(int64_t o) { b ^= o; return ++ip; }; 37 int bst(int64_t o) { b = combo(o) % 8; return ++ip; }; 38 int jnz(int64_t o) { if (a==0) ip++; else ip=o; return ip; }; 39 int bxc(int64_t o [[maybe_unused]]) { b ^= c; return ++ip; }; 40 int out(int64_t o, std::stringstream &ss) { ss << (combo(o)%8) << ","; return ++ip; }; 41 int bdv(int64_t o) { b = a/std::pow(2, combo(o)); return ++ip; }; 42 int cdv(int64_t o) { c = a/std::pow(2, combo(o)); return ++ip; }; 43 // main thing 44 int eval(int op, int64_t o, std::stringstream &ss); 45 std::string run(const Data &input); 46 void reset(); 47 void print() { std::printf("ip:%d,a:%ld,b:%ld,c:%ld\n", ip, a, b, c); } 48 }; 49 50 void Cpu::reset() { 51 a = 0; 52 b = 0; 53 c = 0; 54 ip = 0; 55 } 56 57 int Cpu::eval(int op, int64_t o, std::stringstream &ss) { 58 switch (op) { 59 case 0: return adv(o); 60 case 1: return bxl(o); 61 case 2: return bst(o); 62 case 3: return jnz(o); 63 case 4: return bxc(o); 64 case 5: return out(o, ss); 65 case 6: return bdv(o); 66 case 7: return cdv(o); 67 } 68 std::printf("invalid opcode\n"); 69 return -1; 70 } 71 72 std::string Cpu::run(const Data &input) { 73 std::stringstream ss; 74 while (ip>=0&&ip<(int)input.size()) ip=eval(input[ip].first, input[ip].second, ss); 75 std::string out = ss.str(); 76 out.pop_back(); // to remove the trailing comma 77 return out; 78 } 79 80 Data read_data(const std::string str) { 81 Data buf; 82 std::istringstream iss(str); 83 std::pair<int,int> instr; 84 int num = 0; 85 for (std::string sn; std::getline(iss, sn, ',');) { 86 if (num%2==0) { 87 instr.first = std::stoi(sn); 88 } else { 89 instr.second = std::stoi(sn); 90 buf.push_back(instr); 91 } 92 num++; 93 } 94 return buf; 95 } 96 97 std::tuple<Cpu, Data> read_file(const std::string &path) { 98 std::ifstream ifs(path, std::ios::binary); 99 if (!ifs.is_open()) { 100 throw std::runtime_error(path+":"+std::strerror(errno)); 101 } 102 Data buf; 103 Cpu cpu; 104 for (int l=0;;l++) { 105 std::string str; 106 std::getline(ifs, str); 107 if (!str.empty()) { 108 if (l==0) std::sscanf(str.c_str(), "Register A: %ld", &cpu.a); 109 if (l==1) std::sscanf(str.c_str(), "Register B: %ld", &cpu.b); 110 if (l==2) std::sscanf(str.c_str(), "Register C: %ld", &cpu.c); 111 if (l==4) { 112 char tmp[256] = {0}; 113 std::sscanf(str.c_str(), "Program: %[^\n]", tmp); 114 buf = read_data(tmp); 115 } 116 } 117 if (!ifs) break; 118 } 119 return std::make_pair(cpu, buf); 120 } 121 122 std::string part1(Cpu cpu [[ maybe_unused ]], Data input [[ maybe_unused ]]) { 123 return cpu.run(input); 124 } 125 126 int64_t part2(Cpu cpu, const Data input) { 127 for (int64_t i=0; i<INT64_MAX; ++i) { 128 cpu.reset(); 129 cpu.a = i; 130 Data derived = read_data(cpu.run(input)); 131 if (derived==input) return i; 132 } 133 return -1; 134 } 135 136 int64_t part2_threaded(Cpu cpu [[maybe_unused]], Data input [[ maybe_unused ]]) { 137 using namespace std::chrono_literals; 138 const int nproc = std::thread::hardware_concurrency(); 139 std::vector<std::tuple<int, std::jthread, std::future<bool>>> workers(nproc); 140 //workers.resize(nproc); 141 for (int i=0; i<INT_MAX-(int)workers.size(); i+=workers.size()) { 142 //printf("process batch %d\n", i); 143 for (int n=i%workers.size(); n<(int)workers.size(); ++n) { 144 //printf("start worker %d (%d)\n", n, i+n); 145 std::get<0>(workers[n]) = i+n; 146 std::promise<bool> pr; 147 std::get<2>(workers[n]) = pr.get_future(); 148 std::get<1>(workers[n]) = std::jthread([](const Data &input, int a, auto &&out) { 149 Cpu cpu; 150 cpu.a = a; 151 Data derived = read_data(cpu.run(input)); 152 if (derived==input) cpu.print(); 153 out.set_value(derived==input); 154 //std::this_thread::sleep_for(1s); 155 }, input, i+n, std::move(pr)); 156 } 157 for (auto &w:workers) { 158 auto &[a, th, out] = w; 159 th.join(); 160 //printf("worker (%d) finished\n", a); 161 if (out.get()) return a; 162 } 163 } 164 return -1; 165 } 166 167 int64_t part2_reverse(const Data &input) { 168 Cpu cpu; 169 std::vector<int> psbl; 170 for (int i=1; i<INT_MAX; ++i) { 171 cpu.reset(); 172 cpu.a = i; 173 std::string str = cpu.run(input); 174 //std::cout << "str:" << str << std::endl; 175 std::istringstream ss(str); 176 std::vector<int> vals; 177 for (std::string sn; std::getline(ss, sn, ',');) { 178 //std::cout << sn; 179 vals.push_back(std::stoi(sn)); 180 } 181 //std::printf("last val: %d\n", vals.back()); 182 if (input.back().second==vals.back()) psbl.push_back(i); 183 } 184 return psbl.size(); 185 } 186 187 int main(int argc, char **argv) { 188 Performance perf; 189 const std::string fname = argc>1 ? argv[1] : "test1.txt"; 190 std::cout << "AoC 2024 day 17 " << fname << std::endl; 191 auto [cpu, input] = read_file(fname); 192 std::cout << "part1: " << part1(cpu, input) << std::endl; 193 std::cout << "part2: " << part2_reverse(input) << std::endl; 194 195 return 0; 196 }