Line data    Source code

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