From 9098c9d0d9922f54b3ad9414151604402b8e9c44 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Thu, 2 Jan 2025 14:08:05 +0100 Subject: aoc 2024, day 24, part 2 and day 25 --- 2024/src/day24.cpp | 234 ++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 231 insertions(+), 3 deletions(-) (limited to '2024/src/day24.cpp') diff --git a/2024/src/day24.cpp b/2024/src/day24.cpp index bf439c7..3f252a1 100644 --- a/2024/src/day24.cpp +++ b/2024/src/day24.cpp @@ -1,3 +1,4 @@ +#include #include #include #include @@ -7,6 +8,8 @@ #include using namespace std; +static const auto MAX_BITS = 45UL; + vector split(string_view line, string_view delimiter) { @@ -26,6 +29,23 @@ split(string_view line, string_view delimiter) return res; } +template +string +join(const Container& container, const string& delimiter) +{ + ostringstream oss; + auto iter = container.begin(); + if ( iter != container.end() ) { + oss << *iter; + ++iter; + } + while ( iter != container.end() ) { + oss << delimiter << *iter; + ++iter; + } + return oss.str(); +} + tuple, map>> read_file(string_view filename) { @@ -76,9 +96,6 @@ part1(const tuple, map, map tmp{}; + snprintf(tmp.data(), tmp.size(), "%c%02lu", chr, num); // NOLINT + return tmp.data(); +} + +class RippleCarryAdder { +public: + explicit RippleCarryAdder(const tuple, map>>& data) + : inputs_(get<0>(data)) + , deps_(get<1>(data)) + { + } + + RippleCarryAdder(const map>& deps, unsigned long x_value, unsigned long y_value) + : deps_(deps) + { + build_inputs(x_value, y_value); + } + + void swap_wire(const string& lhs, const string& rhs) + { + swap(deps_.at(lhs), deps_.at(rhs)); + } + + bool eval_z(unsigned long x_value, unsigned long y_value) + { + build_inputs(x_value, y_value); + + bool overflow = false; + for ( auto bit = 0UL; bit != MAX_BITS + 1; ++bit ) { + static const int MAX_RECURSION_DEPTH = 99; + eval(make_wire('z', bit), MAX_RECURSION_DEPTH, overflow); + } + return !overflow; + } + + [[nodiscard]] vector test(unsigned long x_value, unsigned long y_value) const + { + const auto z_value = x_value + y_value; + + vector failed_bits; + auto bit = 0UL; + for ( ; bit != MAX_BITS + 1; ++bit ) { + const auto z_bit = (z_value & (1UL << bit)) != 0 ? 1UL : 0UL; + const auto wire = make_wire('z', bit); + if ( inputs_.at(wire) != z_bit ) { + failed_bits.push_back(wire); + } + } + return failed_bits; + }; + + void print(unsigned long x_value, unsigned long y_value, ostream& out) const + { + const auto z_value = x_value + y_value; + + out << " x: " << bitset{ x_value } << '\n' + << "+ y: " << bitset{ y_value } << '\n' + << "= z: " << bitset{ z_value } << '\n'; + + out << "===: "; + for ( auto bit = MAX_BITS + 1; bit-- > 0; ) { + const auto wire = make_wire('z', bit); + if ( inputs_.contains(wire) ) { + out << inputs_.at(wire); + } + else { + out << '_'; + } + } + out << endl; + }; + + void collect(const string& input, set& possible_fails) const + { + collect(input, 2, possible_fails); + } + +private: + void build_inputs(unsigned long x_value, unsigned long y_value) + { + inputs_.clear(); + + for ( auto bit = 0UL; bit != MAX_BITS; ++bit ) { + inputs_.emplace(make_wire('x', bit), (x_value & (1UL << bit)) != 0 ? 1 : 0); + inputs_.emplace(make_wire('y', bit), (y_value & (1UL << bit)) != 0 ? 1 : 0); + } + } + + unsigned long eval(const string& input, size_t depth, bool& overflow) + { + if ( depth == 0 ) { + overflow = true; + return 0; + } + + if ( inputs_.contains(input) ) { + return inputs_.at(input); + } + + const auto& [lhs, op, rhs] = deps_.at(input); + + unsigned long value = 0; + + if ( op == "XOR" ) { + value = eval(lhs, depth - 1, overflow) ^ eval(rhs, depth - 1, overflow); + } + else if ( op == "AND" ) { + value = eval(lhs, depth - 1, overflow) & eval(rhs, depth - 1, overflow); + } + else if ( op == "OR" ) { + value = eval(lhs, depth - 1, overflow) | eval(rhs, depth - 1, overflow); + } + + inputs_[input] = value; + + return value; + } + + void collect(const string& input, size_t depth, set& possible_fails) const + { + if ( !deps_.contains(input) ) { + return; + } + + possible_fails.insert(input); + + if ( depth == 0 ) { + return; + } + + const auto& [lhs, op, rhs] = deps_.at(input); + + collect(lhs, depth - 1, possible_fails); + collect(rhs, depth - 1, possible_fails); + }; + + map inputs_; + + // register => { reg1 operator reg2 } + map> deps_; +}; + +void +part2(const tuple, map>>& data) +{ + RippleCarryAdder rca(data); + + set solution; + + for ( auto bit = 0UL; bit != MAX_BITS; ++bit ) { + const auto x_value = 1UL << bit; // (1UL << (bit+1)) - 1; + const auto y_value = 0UL << bit; + + if ( !rca.eval_z(x_value, y_value) ) { + return; + } + + const auto failed_bits = rca.test(x_value, y_value); + if ( !failed_bits.empty() ) { + set candidates; + for ( const auto& wire: failed_bits ) { + rca.collect(wire, candidates); + } + + const vector foo{ candidates.begin(), candidates.end() }; + + for ( auto i = foo.begin(); i != foo.end(); ++i ) { + for ( auto j = i + 1; j != foo.end(); ++j ) { + auto do_test = [&](unsigned long lhs, unsigned long rhs) -> bool { + RippleCarryAdder rca_tester{ data }; + + rca_tester.swap_wire(*i, *j); + + if ( !rca_tester.eval_z(lhs, rhs) ) { + return false; + } + return rca_tester.test(lhs, rhs).empty(); + }; + + if ( do_test(x_value, y_value) ) { + const auto x_value2 = 7UL << (bit - 1); + const auto y_value2 = 3UL << (bit - 1); + + if ( do_test(x_value2, y_value2) ) { + const auto x_value3 = 1UL << bit; + const auto y_value3 = 1UL << bit; + + if ( do_test(x_value3, y_value3) ) { + const auto x_value4 = 5UL << (bit - 1); + const auto y_value4 = 3UL << (bit - 1); + + if ( do_test(x_value4, y_value4) ) { + solution.insert(*i); + solution.insert(*j); + } + } + } + } + } + } + } + } + cout << join(solution, ",") << endl; +} + int main() { const auto data = read_file("data/day24.txt"); part1(data); + part2(data); } -- cgit v1.3