Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <vector>
       3                 :             : #include <unordered_map>
       4                 :             : #include <fstream>
       5                 :             : #include <numeric>
       6                 :             : #include <algorithm>
       7                 :             : #include <array>
       8                 :             : #include <string>
       9                 :             : #include <cstdint>
      10                 :             : #include <ranges>
      11                 :             : 
      12                 :             : using namespace std;
      13                 :             : 
      14                 :             : unordered_map<char, array<int8_t, 2>> positions = {{'7', {0, 0}}, {'8', {0, 1}}, {'9', {0, 2}},
      15                 :             :                                                    {'4', {1, 0}}, {'5', {1, 1}}, {'6', {1, 2}},
      16                 :             :                                                    {'1', {2, 0}}, {'2', {2, 1}}, {'3', {2, 2}},
      17                 :             :                                                    {'0', {3, 1}}, {'A', {3, 2}}, {'^', {0, 1}},
      18                 :             :                                                    {'a', {0, 2}}, {'<', {1, 0}}, {'v', {1, 1}}, {'>', {1, 2}}};
      19                 :             : unordered_map<char, array<int8_t, 2>> directions = {{'^', {-1, 0}}, {'v', {1, 0}}, {'<', {0, -1}}, {'>', {0, 1}}};
      20                 :             : unordered_map<string, uint64_t> cache;
      21                 :             : constexpr uint_fast8_t limit = 25;
      22                 :             : 
      23                 :        1788 : uint64_t solve(string path, char depth = 0) {
      24                 :        1788 :   auto key = path + depth;
      25                 :        1788 :   uint64_t& result = cache[key];
      26         [ +  + ]:        1788 :   if (result) {
      27                 :        1348 :     return result;
      28                 :             :   }
      29                 :             : 
      30         [ +  + ]:         440 :   auto curr = positions[depth ? 'a' : 'A'];
      31         [ +  + ]:         440 :   auto avoid = depth ? array<int8_t, 2>{0, 0} : array<int8_t, 2>{3, 0};
      32                 :         440 :   result = 0;
      33                 :             : 
      34         [ +  + ]:        1741 :   for (char c : path) {
      35                 :        1301 :     auto next = positions[c];
      36                 :             :         
      37   [ +  +  +  + ]:        3903 :     string movePath = string(abs(next[0] - curr[0]), (next[0] < curr[0] ? '^' : 'v')) + string(abs(next[1] - curr[1]), (next[1] < curr[1] ? '<' : '>'));
      38                 :        1301 :     ranges::sort(movePath);
      39                 :             : 
      40                 :        1301 :     uint64_t minLen = UINT64_MAX;
      41                 :             :     do {
      42                 :        2153 :       auto temp = curr;
      43         [ +  + ]:        5979 :       if (ranges::all_of(movePath, [&temp, &avoid](char step) { temp[0] += directions[step][0], temp[1] += directions[step][1]; return temp != avoid; })) {
      44   [ +  +  +  + ]:        1853 :         minLen = min(minLen, (depth == limit ? movePath.size() + 1 : solve(movePath + 'a', depth + 1)));
      45                 :             :       }
      46         [ +  + ]:        2153 :     } while (ranges::next_permutation(movePath).found);
      47                 :             : 
      48                 :        1301 :     result += minLen;
      49                 :        1301 :     curr = next;
      50                 :        1301 :   }
      51                 :         440 :   return result;
      52                 :        1788 : }
      53                 :             : 
      54                 :           2 : int main() {
      55                 :           2 :   ifstream fin("input.txt");
      56         [ +  + ]:           2 :   if (!fin) {
      57                 :           1 :     cerr << "Error: Could not open input file.\n";
      58                 :           1 :     return 1;
      59                 :             :   }
      60                 :           1 :   vector<pair<string, int>> input;
      61         [ +  + ]:           6 :   for (string line; getline(fin, line); input.emplace_back(std::move(line), stoi(line)));
      62                 :             : 
      63                 :           6 :   cout << transform_reduce(input.begin(), input.end(), 0ULL, plus<>(), [](const auto& p) { return solve(p.first) * p.second; }) << endl;
      64         [ +  + ]:           3 : }