commit cbc677f8e10ebdb7017d10d5cddcc76dd010bf7e
parent e819cc8bb54f51d1be2e65984da7bbbef204e79f
Author: bsandro <email@bsandro.tech>
Date: Thu, 19 Dec 2024 21:40:57 +0200
Day 17 p2 fruitful attempts
Diffstat:
2 files changed, 115 insertions(+), 37 deletions(-)
diff --git a/day17/main.cpp b/day17/main.cpp
@@ -7,6 +7,9 @@
#include <tuple>
#include <algorithm>
#include <cmath>
+#include <climits>
+#include <thread>
+#include <future>
#include "utils.hpp"
typedef std::vector<std::pair<int, int>> Data;
@@ -16,11 +19,11 @@ public:
// instruction pointer
int ip = 0;
// registers
- int a = 0;
- int b = 0;
- int c = 0;
+ int64_t a = 0;
+ int64_t b = 0;
+ int64_t c = 0;
// combo operand
- int combo(int o) {
+ int64_t combo(int o) {
if (o>=0&&o<=3) return o;
if (o==4) return a;
if (o==5) return b;
@@ -29,21 +32,29 @@ public:
return 0;
}
// opcodes 0-7
- int adv(int o) { a /= std::pow(2, combo(o)); return ++ip; }
- int bxl(int o) { b ^= o; return ++ip; };
- int bst(int o) { b = combo(o) % 8; return ++ip; };
- int jnz(int o) { if (a==0) ip++; else ip=o; return ip; };
- int bxc(int o [[maybe_unused]]) { b ^= c; return ++ip; };
- int out(int o, std::stringstream &ss) { ss << (combo(o)%8) << ","; return ++ip; };
- int bdv(int o) { b = a/std::pow(2, combo(o)); return ++ip; };
- int cdv(int o) { c = a/std::pow(2, combo(o)); return ++ip; };
+ int adv(int64_t o) { a /= std::pow(2, combo(o)); return ++ip; }
+ int bxl(int64_t o) { b ^= o; return ++ip; };
+ int bst(int64_t o) { b = combo(o) % 8; return ++ip; };
+ int jnz(int64_t o) { if (a==0) ip++; else ip=o; return ip; };
+ int bxc(int64_t o [[maybe_unused]]) { b ^= c; return ++ip; };
+ int out(int64_t o, std::stringstream &ss) { ss << (combo(o)%8) << ","; return ++ip; };
+ int bdv(int64_t o) { b = a/std::pow(2, combo(o)); return ++ip; };
+ int cdv(int64_t o) { c = a/std::pow(2, combo(o)); return ++ip; };
// main thing
- int eval(int op, int o, std::stringstream &ss);
+ int eval(int op, int64_t o, std::stringstream &ss);
std::string run(const Data &input);
- void print() { std::printf("ip:%d,a:%d,b:%d,c:%d\n", ip, a, b, c); }
+ void reset();
+ void print() { std::printf("ip:%d,a:%ld,b:%ld,c:%ld\n", ip, a, b, c); }
};
-int Cpu::eval(int op, int o, std::stringstream &ss) {
+void Cpu::reset() {
+ a = 0;
+ b = 0;
+ c = 0;
+ ip = 0;
+}
+
+int Cpu::eval(int op, int64_t o, std::stringstream &ss) {
switch (op) {
case 0: return adv(o);
case 1: return bxl(o);
@@ -61,7 +72,26 @@ int Cpu::eval(int op, int o, std::stringstream &ss) {
std::string Cpu::run(const Data &input) {
std::stringstream ss;
while (ip>=0&&ip<(int)input.size()) ip=eval(input[ip].first, input[ip].second, ss);
- return ss.str();
+ std::string out = ss.str();
+ out.pop_back(); // to remove the trailing comma
+ return out;
+}
+
+Data read_data(const std::string str) {
+ Data buf;
+ std::istringstream iss(str);
+ std::pair<int,int> instr;
+ int num = 0;
+ for (std::string sn; std::getline(iss, sn, ',');) {
+ if (num%2==0) {
+ instr.first = std::stoi(sn);
+ } else {
+ instr.second = std::stoi(sn);
+ buf.push_back(instr);
+ }
+ num++;
+ }
+ return buf;
}
std::tuple<Cpu, Data> read_file(const std::string &path) {
@@ -75,24 +105,13 @@ std::tuple<Cpu, Data> read_file(const std::string &path) {
std::string str;
std::getline(ifs, str);
if (!str.empty()) {
- if (l==0) std::sscanf(str.c_str(), "Register A: %d", &cpu.a);
- if (l==1) std::sscanf(str.c_str(), "Register B: %d", &cpu.b);
- if (l==2) std::sscanf(str.c_str(), "Register C: %d", &cpu.c);
+ if (l==0) std::sscanf(str.c_str(), "Register A: %ld", &cpu.a);
+ if (l==1) std::sscanf(str.c_str(), "Register B: %ld", &cpu.b);
+ if (l==2) std::sscanf(str.c_str(), "Register C: %ld", &cpu.c);
if (l==4) {
char tmp[256] = {0};
std::sscanf(str.c_str(), "Program: %[^\n]", tmp);
- std::istringstream iss(tmp);
- std::pair<int,int> instr;
- int num = 0;
- for (std::string sn; std::getline(iss, sn, ',');) {
- if (num%2==0) {
- instr.first = std::stoi(sn);
- } else {
- instr.second = std::stoi(sn);
- buf.push_back(instr);
- }
- num++;
- }
+ buf = read_data(tmp);
}
}
if (!ifs) break;
@@ -101,14 +120,68 @@ std::tuple<Cpu, Data> read_file(const std::string &path) {
}
std::string part1(Cpu cpu [[ maybe_unused ]], Data input [[ maybe_unused ]]) {
- //cpu.print();
- //for (auto [opcode, operand] : input) std::printf("[%d,%d]", opcode, operand);
-
return cpu.run(input);
}
-int64_t part2(Data &input [[ maybe_unused ]]) {
- return 0;
+int64_t part2(Cpu cpu, const Data input) {
+ for (int64_t i=0; i<INT64_MAX; ++i) {
+ cpu.reset();
+ cpu.a = i;
+ Data derived = read_data(cpu.run(input));
+ if (derived==input) return i;
+ }
+ return -1;
+}
+
+int64_t part2_threaded(Cpu cpu [[maybe_unused]], Data input [[ maybe_unused ]]) {
+ using namespace std::chrono_literals;
+ const int nproc = std::thread::hardware_concurrency();
+ std::vector<std::tuple<int, std::jthread, std::future<bool>>> workers(nproc);
+ //workers.resize(nproc);
+ for (int i=0; i<INT_MAX-(int)workers.size(); i+=workers.size()) {
+ //printf("process batch %d\n", i);
+ for (int n=i%workers.size(); n<(int)workers.size(); ++n) {
+ //printf("start worker %d (%d)\n", n, i+n);
+ std::get<0>(workers[n]) = i+n;
+ std::promise<bool> pr;
+ std::get<2>(workers[n]) = pr.get_future();
+ std::get<1>(workers[n]) = std::jthread([](const Data &input, int a, auto &&out) {
+ Cpu cpu;
+ cpu.a = a;
+ Data derived = read_data(cpu.run(input));
+ if (derived==input) cpu.print();
+ out.set_value(derived==input);
+ //std::this_thread::sleep_for(1s);
+ }, input, i+n, std::move(pr));
+ }
+ for (auto &w:workers) {
+ auto &[a, th, out] = w;
+ th.join();
+ //printf("worker (%d) finished\n", a);
+ if (out.get()) return a;
+ }
+ }
+ return -1;
+}
+
+int64_t part2_reverse(const Data &input) {
+ Cpu cpu;
+ std::vector<int> psbl;
+ for (int i=1; i<INT_MAX; ++i) {
+ cpu.reset();
+ cpu.a = i;
+ std::string str = cpu.run(input);
+ //std::cout << "str:" << str << std::endl;
+ std::istringstream ss(str);
+ std::vector<int> vals;
+ for (std::string sn; std::getline(ss, sn, ',');) {
+ //std::cout << sn;
+ vals.push_back(std::stoi(sn));
+ }
+ //std::printf("last val: %d\n", vals.back());
+ if (input.back().second==vals.back()) psbl.push_back(i);
+ }
+ return psbl.size();
}
int main(int argc, char **argv) {
@@ -117,7 +190,7 @@ int main(int argc, char **argv) {
std::cout << "AoC 2024 day 17 " << fname << std::endl;
auto [cpu, input] = read_file(fname);
std::cout << "part1: " << part1(cpu, input) << std::endl;
- std::cout << "part2: " << part2(input) << std::endl;
+ std::cout << "part2: " << part2_reverse(input) << std::endl;
return 0;
}
diff --git a/day17/test2.txt b/day17/test2.txt
@@ -0,0 +1,5 @@
+Register A: 2024
+Register B: 0
+Register C: 0
+
+Program: 0,3,5,4,3,0
