diff options
Diffstat (limited to '2021/day24/day24.cpp')
-rw-r--r-- | 2021/day24/day24.cpp | 491 |
1 files changed, 491 insertions, 0 deletions
diff --git a/2021/day24/day24.cpp b/2021/day24/day24.cpp new file mode 100644 index 0000000..1121018 --- /dev/null +++ b/2021/day24/day24.cpp @@ -0,0 +1,491 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <map> +#include <set> + +#include "gtest/gtest.h" + +class Alu { + private: + long v[4]; + + public: + Alu() { + v[0] = 0; v[1] = 0; v[2] = 0; v[3] = 0; + } + + std::string show () { + return "(" + + std::to_string(v[0]) + ", " + + std::to_string(v[1]) + ", " + + std::to_string(v[2]) + ", " + + std::to_string(v[3]) + + ")"; + } + + int operator[](const int& i) const { return v[i]; } + + void inp (int i, int val) { v[i] = val; } + void add (int i, int val) { v[i] = v[i]+val; } + void mul (int i, int val) { v[i] = v[i]*val; } + void div (int i, int val) { v[i] = v[i]/val; } + void mod (int i, int val) { v[i] = v[i]%val; } + void eql (int i, int val) { v[i] = v[i]==val ? 1 : 0; } + void op (int o, int i, int j, bool imm) { + int val = imm ? j : v[j]; + if (o==0) inp(i, val); + else if (o==1) add(i, val); + else if (o==2) mul(i, val); + else if (o==3) div(i, val); + else if (o==4) mod(i, val); + else if (o==5) eql(i, val); + } +}; + +TEST (alu, exisits) { + Alu alu; +} + +TEST (alu, variables) { + Alu alu; + ASSERT_EQ(0, alu[0]); + ASSERT_EQ(0, alu[1]); + ASSERT_EQ(0, alu[2]); + ASSERT_EQ(0, alu[3]); +} + +TEST (alu, inp) { + Alu alu; + alu.inp(2, 5); + ASSERT_EQ(5, alu[2]); +} + +TEST (alu, add) { + Alu alu; + alu.inp(2, 5); alu.inp(1, 6); + alu.add(1, alu[2]); + ASSERT_EQ(11, alu[1]); +} + +TEST (alu, mul) { + Alu alu; + alu.inp(0, 5); alu.inp(3, 6); + alu.mul(3, alu[0]); + ASSERT_EQ(30, alu[3]); +} + +TEST (alu, div) { + Alu alu; + alu.inp(0, 31); alu.inp(1, 6); + alu.div(0, alu[1]); + ASSERT_EQ(5, alu[0]); + alu.inp(0, -31); alu.inp(1, 6); + alu.div(0, alu[1]); + ASSERT_EQ(-5, alu[0]); +} + +TEST (alu, mod) { + Alu alu; + alu.inp(0, 32); alu.inp(1, 6); + alu.mod(0, alu[1]); + ASSERT_EQ(2, alu[0]); +} + +TEST (alu, eql) { + Alu alu; + alu.inp(0, 32); alu.inp(1, 43); + alu.eql(0, alu[1]); + ASSERT_EQ(0, alu[0]); + alu.inp(0, 5); alu.inp(1, 5); + alu.eql(0, alu[1]); + ASSERT_EQ(1, alu[0]); +} + +TEST (alu, op) { + Alu alu; + alu.op(0, 0, 10, true); alu.op(0, 1, 7, true); + alu.op(5, 0, 1, false); + ASSERT_EQ(0, alu[0]); +} + + +class Rule { + public: + Rule () { } + Rule (std::string raw) { parse(raw); } + int op, i, j; + bool imm; + + void parse (std::string raw) { + auto rop = raw.substr(0, 3); + if (rop == "inp") op = 0; + else if (rop == "add") op = 1; + else if (rop == "mul") op = 2; + else if (rop == "div") op = 3; + else if (rop == "mod") op = 4; + else if (rop == "eql") op = 5; + + auto par = raw.substr(4); + i = par[0] -'w'; + if (op > 0) { + if (par[2] == 'w' || par[2] == 'x' || + par[2] == 'y' || par[2] == 'z') { + imm = false; + j = par[2] -'w'; + } + else { + imm = true; + j = std::stoi( par.substr(2) ); + } + } + } +}; + +class State { + public: + State (): alu(), pc(0) { } + State (std::vector<int> in): alu(), input(in), pc(0) { } + State (std::string raw): alu(), pc(0) { parse(raw); } + + Alu alu; + std::vector<int> input; + int pc; + + void parse (std::string raw) { + for (char c : raw) { + input.push_back(std::stoi(std::string { c })); + } + } + + void rule (const Rule &rule) { + if (rule.op == 0) { + alu.op(rule.op, rule.i, input[pc], true); + pc++; + } else + alu.op(rule.op, rule.i, rule.j, rule.imm); + } +}; + +TEST (rule, translate_one) { + std::string raw { "inp x" }; + Rule r { raw }; + ASSERT_EQ(0, r.op); + ASSERT_EQ(1, r.i); +} + +TEST (rule, translate_two) { + std::string raw { "mod w x" }; + Rule r { raw }; + ASSERT_EQ(4, r.op); + ASSERT_EQ(0, r.i); + ASSERT_EQ(1, r.j); +} + +TEST (rule, translate_immediate) { + std::string raw { "add z 20" }; + Rule r { raw }; + ASSERT_EQ(1, r.op); + ASSERT_EQ(3, r.i); + ASSERT_EQ(20, r.j); +} + + +class Program { + public: + Program(std::string raw, State s): state(s) { parse(raw); } + Program(std::vector<Rule> r, State s): rules(r), state(s) { } + + State state; + std::vector<Rule> rules; + + void parse (std::string raw) { + while (raw.size() > 0) { + auto newline = raw.find("\n"); + if (newline == std::string::npos) { + rules.push_back(Rule { raw }); + break; + } else { + rules.push_back(Rule { raw.substr(0, newline) }); + raw = raw.substr(newline+1); + } + } + } + + void run () { + for (Rule &rule : rules) { + state.rule(rule); + } + } +}; + +TEST (program, exists) { + State p; +} + +TEST (program, from_input) { + std::vector<int> input { 1, 2, 2, 4 }; + State p { input }; +} + +TEST (program, apply_rule) { + std::vector<int> input { 1 }; + State p { input }; + p.rule(Rule { "inp x" }); + ASSERT_EQ(1, p.alu[1]); +} + +TEST (program, apply_negate) { + std::vector<int> input { 6 }; + State p { input }; + p.rule(Rule { "inp x" }); + p.rule(Rule { "mul x -1" }); + ASSERT_EQ(-6, p.alu[1]); +} + +TEST (program, apply_triple) { + Program p { + { + Rule { "inp z" }, + Rule { "inp x" }, + Rule { "mul z 3" }, + Rule { "eql z x" } + }, + State { std::string { "26" } } + }; + p.run(); + ASSERT_EQ(1, p.state.alu[3]); +} + +TEST (program, bits) { + std::string raw; + std::getline(std::ifstream("test0.txt"), raw, '\0'); + Program p { raw, State { std::vector<int>{ 15 }} }; + p.run(); + ASSERT_EQ(1, p.state.alu[0]); + ASSERT_EQ(1, p.state.alu[1]); + ASSERT_EQ(1, p.state.alu[2]); + ASSERT_EQ(1, p.state.alu[3]); +} + +class Set { + public: + Set () { } + Set (const Set &s): v(s.v) { } + Set (int min, int max) { + for (int i=min; i<max+1; i++) v.push_back(i); + } + + std::vector<int> v; + + std::string show () { + std::string rep = "(Set, ["; + for (int i=0; i<v.size(); i++) { + rep += std::to_string(v[i]); + if (i < v.size()-1) rep += ", "; + } + rep += "])"; + return rep; + } + + Set add (int n) const { + Set s; + for (int i=0; i<v.size(); i++) + s.v.push_back(v[i] + n); + return s; + }; + + Set sub (int n) const { return add(-n); }; + + Set intersect (const Set &oth) const { + Set s; + for (int i=0; i<v.size(); i++) { + if (std::find( + std::begin(oth.v), std::end(oth.v), v[i] + ) != std::end(oth.v)) + { + s.v.push_back(v[i]); + } + } + return s; + } + + Set diff (const Set &oth) const { + Set s; + for (int i=0; i<v.size(); i++) { + if (std::find( + std::begin(oth.v), std::end(oth.v), v[i] + ) == std::end(oth.v)) + { + s.v.push_back(v[i]); + } + } + return s; + } +}; + +TEST (set, exists) { + Set set; +} + +TEST (set, range) { + Set set(1, 9); + ASSERT_EQ(1, set.v[0]); + ASSERT_EQ(7, set.v[6]); + ASSERT_EQ(9, set.v[8]); +} + +TEST (set, add) { + Set base(1, 9); + Set set { base.add(3) }; + ASSERT_EQ(4, set.v[0]); + ASSERT_EQ(10, set.v[6]); + ASSERT_EQ(12, set.v[8]); +} + +TEST (set, sub) { + Set base(1, 9); + Set set { base.sub(3) }; + ASSERT_EQ(-2, set.v[0]); + ASSERT_EQ(4, set.v[6]); + ASSERT_EQ(6, set.v[8]); +} + +TEST (set, intersect) { + Set a(1, 9); + Set b(4, 12); + Set set { a.intersect(b) }; + ASSERT_EQ(6, set.v.size()); +} + +TEST (set, diff) { + Set a(1, 9); + Set b(4, 12); + Set set { a.diff(b) }; + ASSERT_EQ(3, set.v.size()); +} + + +int fairy[14] { 1,1,1,1,26,26,1,1,26,26,1,26,26,26 }; +int magic[14] { 13,12,12,10,-11,-13,15,10,-2,-6,14,0,-15,-4 }; +int witch[14] { 8,13,8,10,12,1,13,5,10,3,2,2,12,7 }; + +std::vector<Set> good_ids ( + std::vector<Set> ins, std::vector<Set> z_prev, int n) +{ + if (z_prev.size() > 5) { return {}; } + if (n == 14) { + if (z_prev.size() <= 0) return ins; + else return {}; + } + std::vector<Set> z { z_prev }; + + Set in(1, 9); + Set x; + if (z.size() > 0) { + x = z[z.size()-1].add(magic[n]); + if (fairy[n] == 26) z.erase(z.end()-1); + } + Set other = in.diff(x); + Set nop = in.diff(other); + + for (int i=0; i<n; i++) std::cout << " "; + std::cout << n << " " << z.size(); + std::cout << ", " << nop.show() << std::endl; + + std::vector<Set> ins_nop = ins; + if (other.v.size() > 0) { + std::vector<Set> ins_oth = ins; ins_oth.push_back(other); + std::vector<Set> z_n = z; z_n.push_back(other.add(witch[n])); + ins = good_ids(ins_oth, z_n, n+1); + } + if (nop.v.size() > 0) { + ins_nop.push_back(nop); + std::vector<Set> ins_f = good_ids(ins_nop, z, n+1); + if (ins.size() == 0) { + ins = ins_f; + } + } + return ins; +} + +TEST (ranges, view) { + auto ids = good_ids({}, {}, 0); + for (auto s : ids) { + std::cout << s.show() << std::endl; + } + ASSERT_NE(0, ids.size()); +} + +long min_temp = 999999999999; + +std::vector<int> look_rec ( + std::vector<Set> &s, Program &p, std::vector<int> res, int n, bool big) +{ + if (n == 14) { + Program test { p.rules, State { res } }; + test.run(); + //if (std::abs(test.state.alu[3]) <= 15) { + //if (std::abs(test.state.alu[3]) <= 455) { + if (std::abs(test.state.alu[3]) <= min_temp) { + min_temp = std::abs(test.state.alu[3]); + for (int i=0; i<n; i++) std::cout << res[i]; + std::cout << " " << test.state.alu[3]; + std::cout << std::endl; + } + if (test.state.alu[3] == 0) return res; + else return {}; + } + for (int i=s[n].v.size()-1; i>=0; i--) { + std::vector<int> r { res }; + int num = s[n].v[i]; + if (!big) num = s[n].v[s[n].v.size()-1-i]; + r.push_back(num); + auto f = look_rec(s, p, r, n+1, big); + if (f.size() > 0) return f; + } + return {}; +} + + +std::vector<int> look (Program p, bool big) { + auto ids = good_ids({}, {}, 0); + if (big) { + ids[0].v.erase(ids[0].v.end()-1); + ids[0].v.erase(ids[0].v.end()-1); + ids[0].v.erase(ids[0].v.end()-1); + ids[0].v.erase(ids[0].v.end()-1); + } else { + ids[0].v = { 1 }; + //ids[1].v = { 1 }; + //ids[2].v = { 1 }; + ids[3].v = { 2 }; + //ids[4].v = { 1 }; + + ids[10].v = { 1 }; + ids[11].v = { 3 }; + ids[12].v = { 1 }; + ids[13].v = { 5 }; + } + return look_rec(ids, p, {}, 0, big); +} + + +int main (int argc, char *argv[]) { + if (argc > 1 && std::string { argv[1] } == "-t") { + testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); + } + std::string raw; + std::getline(std::ifstream("day24_input.txt"), raw, '\0'); + + auto id = 0; + Program p { raw, State { } }; + if (argc > 1 && std::string { argv[1] } == "big") { + look(p, true); + } + if (argc > 1 && std::string { argv[1] } == "small") { + look(p, false); + } + return 0; +} |