Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Parsing.h"
       4              : #include "Views.h"
       5              : 
       6              : #include <re2/re2.h>
       7              : 
       8              : #include <algorithm>
       9              : #include <cstddef>
      10              : #include <ranges>
      11              : #include <string_view>
      12              : 
      13              : using namespace std::literals;
      14              : 
      15              : namespace {
      16              : 
      17              : class Computer {
      18              : public:
      19              :   Computer(uint64_t const a, uint64_t const b, uint64_t const c,
      20              :            std::vector<uint64_t> const &program)
      21            2 :       : _a(a), _b(b), _c(c), _program(program) {}
      22              : 
      23          155 :   [[nodiscard]] auto const &output() const { return _output; }
      24           74 :   [[nodiscard]] auto const &program() const { return _program; }
      25              : 
      26            1 :   std::vector<uint64_t> const &run() { return run(_a); }
      27              : 
      28          154 :   std::vector<uint64_t> const &run(uint64_t const a) {
      29          154 :     _a = a;
      30          154 :     _ip = 0;
      31          154 :     _output.clear();
      32        11818 :     while (_ip < _program.size())
      33        11664 :       step();
      34              : 
      35          154 :     return output();
      36          154 :   }
      37              : 
      38              : private:
      39        11664 :   uint64_t op() {
      40        11664 :     ASSUME(_ip < _program.size());
      41        11664 :     return _program[_ip];
      42        11664 :   }
      43              : 
      44        11664 :   void step() {
      45        11664 :     switch (op()) {
      46         1458 :     case 0: // adv
      47         1458 :       _a >>= comboOperand();
      48         1458 :       _ip += 2;
      49         1458 :       break;
      50         2916 :     case 1: // bxl
      51         2916 :       _b ^= literalOperand();
      52         2916 :       _ip += 2;
      53         2916 :       break;
      54         1458 :     case 2: // bst
      55         1458 :       _b = comboOperand() % 8u;
      56         1458 :       _ip += 2;
      57         1458 :       break;
      58         1458 :     case 3: // jnz
      59         1458 :       if (_a == 0)
      60          154 :         _ip += 2;
      61         1304 :       else
      62         1304 :         _ip = literalOperand();
      63         1458 :       break;
      64         1458 :     case 4: // bxc
      65         1458 :       _b ^= _c;
      66         1458 :       _ip += 2;
      67         1458 :       break;
      68         1458 :     case 5: // out
      69         1458 :       _output.push_back(comboOperand() % 8u);
      70         1458 :       _ip += 2;
      71         1458 :       break;
      72            0 :     case 6: // bdv
      73            0 :       _b = _a >> comboOperand();
      74            0 :       _ip += 2;
      75            0 :       break;
      76         1458 :     case 7: // cdv
      77         1458 :       _c = _a >> comboOperand();
      78         1458 :       _ip += 2;
      79         1458 :       break;
      80            0 :     default:
      81            0 :       UNREACHABLE(op());
      82        11664 :     }
      83        11664 :   }
      84              : 
      85         4220 :   uint64_t literalOperand() {
      86         4220 :     ASSUME(_ip + 1u < _program.size());
      87         4220 :     return _program[_ip + 1u];
      88         4220 :   }
      89              : 
      90         5832 :   uint64_t comboOperand() {
      91         5832 :     ASSUME(_ip + 1u < _program.size());
      92         5832 :     uint64_t const val = _program[_ip + 1u];
      93         5832 :     switch (val) {
      94            0 :     case 0:
      95            0 :     case 1:
      96            0 :     case 2:
      97         1458 :     case 3:
      98         1458 :       return val;
      99         1458 :     case 4:
     100         1458 :       return _a;
     101         2916 :     case 5:
     102         2916 :       return _b;
     103            0 :     case 6:
     104            0 :       return _c;
     105            0 :     default:
     106            0 :       UNREACHABLE(val);
     107         5832 :     }
     108         5832 :   }
     109              : 
     110              :   uint64_t _a = 0;
     111              :   uint64_t _b = 0;
     112              :   uint64_t _c = 0;
     113              :   uint64_t _ip = 0;
     114              :   std::vector<uint64_t> _program;
     115              :   std::vector<uint64_t> _output;
     116              : };
     117              : 
     118            2 : Computer parse(std::string_view const input) {
     119            2 :   RE2 regex =
     120            2 :       R"(Register A: (\d+)\nRegister B: (\d+)\nRegister C: (\d+)\n\nProgram: ((?:\d+,)*\d+))"sv;
     121              : 
     122            2 :   uint64_t a = 0;
     123            2 :   uint64_t b = 0;
     124            2 :   uint64_t c = 0;
     125            2 :   std::string_view programStr;
     126              : 
     127            2 :   RE2::FullMatch(input, regex, &a, &b, &c, &programStr);
     128              : 
     129            2 :   return {a, b, c, parseIntegerRange<uint64_t>(programStr)};
     130            2 : }
     131              : 
     132              : } // namespace
     133              : 
     134            1 : template <> std::string solvePart1<2024, 17>(std::string_view const input) {
     135            1 :   Computer c = parse(input);
     136            1 :   c.run();
     137              : 
     138            1 :   return c.output() | views::toStringAndJoinWith(",") | std::ranges::to<std::string>();
     139            1 : }
     140              : 
     141            1 : template <> std::string solvePart2<2024, 17>(std::string_view const input) {
     142            1 :   Computer c = parse(input);
     143              : 
     144            1 :   uint64_t a = 0;
     145           37 :   for (auto it = c.program().rbegin(); it != c.program().rend();) {
     146           36 :     uint64_t i = a & 0b111;
     147          163 :     for (; i < 8u; ++i, ++a) {
     148          153 :       if (c.run(a).front() == *it) {
     149           26 :         break;
     150           26 :       }
     151          153 :     }
     152           36 :     if (i < 8u) {
     153           26 :       ++it;
     154           26 :       if (it != c.program().rend())
     155           25 :         a <<= 3u;
     156           26 :     } else {
     157           10 :       ASSUME(it != c.program().rbegin());
     158           10 :       --it;
     159           10 :       a >>= 3u;
     160           10 :     }
     161           36 :   }
     162              : 
     163            1 :   return std::to_string(a);
     164            1 : }