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-alt.cpp | 197 +++++++++++++++++++++++++++++++++++++++++ 2024/src/day24.cpp | 234 ++++++++++++++++++++++++++++++++++++++++++++++++- 2024/src/day25.cpp | 87 ++++++++++++++++++ 3 files changed, 515 insertions(+), 3 deletions(-) create mode 100644 2024/src/day24-alt.cpp create mode 100644 2024/src/day25.cpp (limited to '2024/src') diff --git a/2024/src/day24-alt.cpp b/2024/src/day24-alt.cpp new file mode 100644 index 0000000..df6d333 --- /dev/null +++ b/2024/src/day24-alt.cpp @@ -0,0 +1,197 @@ +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +vector +split(string_view line, string_view delimiter) +{ + size_t pos_start = 0; + size_t pos_end = 0; + + vector res; + + while ( (pos_end = line.find(delimiter, pos_start)) != std::string::npos ) { + auto token = line.substr(pos_start, pos_end - pos_start); + pos_start = pos_end + delimiter.length(); + + res.emplace_back(token); + } + + res.emplace_back(line.substr(pos_start)); + return res; +} + +template +string +join(const Container& container, const string& delimiter) +{ + ostringstream oss; + auto it = container.begin(); + if ( it != container.end() ) { + oss << *it; + ++it; + } + while ( it != container.end() ) { + oss << delimiter << *it; + ++it; + } + return oss.str(); +} + +tuple, map>> +read_file(string_view filename) +{ + fstream input{ filename }; + const auto parts = split(string{ istreambuf_iterator{ input }, {} }, "\n\n"); + + map inputs; + + // register => { reg1 operator reg2 } + map> deps; + + stringstream spart1{ parts[0] }; + for ( string line; getline(spart1, line); ) { + const auto foo = split(line, ": "); + inputs[foo[0]] = stoul(foo[1]); + } + + stringstream spart2{ parts[1] }; + for ( string line; getline(spart2, line); ) { + const auto foo = split(line, " "); + deps[foo[4]] = { foo[0], foo[1], foo[2] }; + } + + return { inputs, deps }; +} + +void +part1(const tuple, map>>& data) +{ + auto inputs = get<0>(data); + const auto& deps = get<1>(data); + + function eval = [&](const string& input) -> unsigned long { + 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) ^ eval(rhs); + } + else if ( op == "AND" ) { + value = eval(lhs) & eval(rhs); + } + else if ( op == "OR" ) { + value = eval(lhs) | eval(rhs); + } + else { + cerr << "Das darf nicht passieren! Input: " << input << endl; + } + + inputs[input] = value; + + return value; + }; + + unsigned long value = 0; + for ( const auto& [first, second]: deps ) { + if ( first.starts_with("z") ) { + if ( eval(first) != 0 ) { + auto bit = stoul(first.substr(1)); + value |= 1UL << bit; + } + } + } + cout << value << endl; +} + +void +debug(const tuple, map>>& data) +{ + const auto& deps = get<1>(data); + + function eval = [&](const string& input, size_t depth) { + if ( !deps.contains(input) ) { + return; + } + + if ( depth == 3 ) { + return; + } + + const auto& [lhs, op, rhs] = deps.at(input); + + const string indent(depth * 2, ' '); + + cout << indent << op << " (" << input << ")\n" + << indent << " - " << lhs << "\n" + << indent << " - " << rhs << endl; + + eval(lhs, depth + 1); + eval(rhs, depth + 1); + }; + + eval("z02", 0); + eval("z16", 0); + eval("z17", 0); +} + +void +part2(const tuple, map>>& data) +{ + auto deps = get<1>(data); + + set wrong; + for ( const auto& [res, formula]: deps ) { + const auto& [op1, op, op2] = formula; + + if ( res.starts_with('z') && op != "XOR" && res != "z45" ) { + wrong.insert(res); + } + + static const set starts{ 'x', 'y', 'z' }; + + if ( op == "XOR" && !starts.contains(res[0]) && !starts.contains(op1[0]) && !starts.contains(op2[0]) ) { + wrong.insert(res); + } + + if ( op == "AND" && op1 != "x00" && op2 != "x00" ) { + for ( const auto& [subres, subformula]: deps ) { + const auto& [subop1, subop, subop2] = subformula; + if ( (res == subop1 || res == subop2) and subop != "OR" ) { + wrong.insert(res); + } + } + } + + if ( op == "XOR" ) { + for ( const auto& [subres, subformula]: deps ) { + const auto& [subop1, subop, subop2] = subformula; + if ( (res == subop1 || res == subop2) and subop == "OR" ) { + wrong.insert(res); + } + } + } + } + + cout << join(wrong, ",") << endl; +} + +int +main() +{ + const auto data = read_file("data/day24.txt"); + // debug(data); + part1(data); + part2(data); +} 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); } diff --git a/2024/src/day25.cpp b/2024/src/day25.cpp new file mode 100644 index 0000000..6d43ddf --- /dev/null +++ b/2024/src/day25.cpp @@ -0,0 +1,87 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +using pattern_type = vector; + +vector +split(string_view line, string_view delimiter) +{ + size_t pos_start = 0; + size_t pos_end = 0; + + vector res; + + while ( (pos_end = line.find(delimiter, pos_start)) != std::string::npos ) { + auto token = line.substr(pos_start, pos_end - pos_start); + pos_start = pos_end + delimiter.length(); + + res.emplace_back(token); + } + + res.emplace_back(line.substr(pos_start)); + return res; +} + +tuple, vector> +read_file(string_view filename) +{ + fstream input{ filename }; + const auto patterns{ split(string{ istreambuf_iterator{ input }, {} }, "\n\n") }; + + vector keys; + vector locks; + + for ( const auto& pattern: patterns ) { + const pattern_type& lines = split(pattern, "\n"); + + if ( lines[0] == "#####" && lines[6] == "....." ) { + locks.push_back(lines); + } + else if ( lines[0] == "....." && lines[6] == "#####" ) { + keys.push_back(lines); + } + } + + return { keys, locks }; +} + +bool +fits(const pattern_type& key, const pattern_type& lock) +{ + for ( size_t row = 0; row != key.size(); ++row ) { + for ( size_t col = 0; col != key[row].size(); ++col ) { + if ( key[row][col] == '#' && lock[row][col] == '#' ) { + return false; + } + } + } + return true; +} + +void +part1(const tuple, vector>& data) +{ + const auto [keys, locks] = data; + + long count = 0; + for ( const auto& key: keys ) { + for ( const auto& lock: locks ) { + if ( fits(key, lock) ) { + ++count; + } + } + } + cout << count << endl; +} + +int +main() +{ + const auto data = read_file("data/day25.txt"); + part1(data); +} -- cgit v1.3