day21a-debuggable.cpp (3070B)
1 #include <algorithm> 2 #include <cstdint> 3 #include <iostream> 4 #include <limits> 5 #include <map> 6 #include <queue> 7 #include <ranges> 8 #include <set> 9 #include <sstream> 10 #include <string> 11 #include <string_view> 12 #include <vector> 13 using namespace std; 14 15 map<char, pair<int, int>> m_num = { 16 {'7', {0,0}}, {'8', {0,1}}, {'9', {0,2}}, 17 {'4', {1,0}}, {'5', {1,1}}, {'6', {1,2}}, 18 {'1', {2,0}}, {'2', {2,1}}, {'3', {2,2}}, 19 {'x', {3,0}}, {'0', {3,1}}, {'A', {3,2}}, 20 }; 21 22 map<char, pair<int, int>> m_dir = { 23 {'x', {0,0}}, {'^', {0,1}}, {'A', {0,2}}, 24 {'<', {1,0}}, {'v', {1,1}}, {'>', {1,2}}, 25 }; 26 27 map<pair<int, int>, char> rev_num; 28 map<pair<int, int>, char> rev_dir; 29 30 map<pair<char, char>, vector<string>> p; 31 32 vector<pair<pair<int, int>, char>> directions = { 33 {{1,0}, 'v'}, {{-1,0}, '^'}, {{0,1}, '>'}, {{0,-1}, '<'} 34 }; 35 36 int distance(int cx, int cy, int dx, int dy) { 37 return abs(cx-dx) + abs(cy-dy); 38 } 39 40 vector<string> paths(char c, char d, 41 map<char, pair<int, int>>& m, map<pair<int, int>, char>& rev) { 42 if (p[make_pair(c, d)].size() != 0) return p[make_pair(c, d)]; 43 if (c == d) return {""}; 44 if (c == 'x') return {}; 45 46 vector<string> v; 47 auto [cx, cy] = m[c]; 48 auto [dx, dy] = m[d]; 49 for (auto [dir, dirc] : directions) { 50 pair i = make_pair(cx+dir.first, cy+dir.second); 51 if (distance(cx, cy, dx, dy) < distance(i.first, i.second, dx, dy)) 52 continue; 53 auto next = paths(rev[i], d, m, rev); 54 for (auto n : next) 55 v.push_back(dirc+n); 56 } 57 58 return p[make_pair(c, d)] = v; 59 } 60 61 string pushes_human(char c, char d) { 62 auto p = paths(c, d, m_dir, rev_dir); 63 auto shortest = numeric_limits<size_t>::max(); 64 string ret; 65 for (auto path : p) { 66 if (path.size() + 1 < shortest) { 67 ret = path + 'A'; 68 shortest = path.size() + 1; 69 } 70 } 71 return ret; 72 } 73 74 string pushes_dir1(char c, char d) { 75 auto p = paths(c, d, m_dir, rev_dir); 76 auto shortest = numeric_limits<size_t>::max(); 77 string ret; 78 for (auto path : p) { 79 path = 'A' + path + 'A'; 80 string pushes = ""; 81 for (unsigned i = 0; i < path.size()-1; i++) 82 pushes += pushes_human(path[i], path[i+1]); 83 if (pushes.size() < shortest) { 84 ret = pushes; 85 shortest = pushes.size(); 86 } 87 } 88 return ret; 89 } 90 91 string pushes_numpad(char c, char d) { 92 auto p = paths(c, d, m_num, rev_num); 93 auto shortest = numeric_limits<size_t>::max(); 94 string ret; 95 for (auto path : p) { 96 path = 'A' + path + 'A'; 97 string pushes = ""; 98 for (unsigned i = 0; i < path.size()-1; i++) 99 pushes += pushes_dir1(path[i], path[i+1]); 100 if (pushes.size() < shortest) { 101 ret = pushes; 102 shortest = pushes.size(); 103 } 104 } 105 return ret; 106 } 107 108 int64_t numeric(const string& code) { 109 return (code[0]-'0')*100 + (code[1]-'0')*10 + (code[2]-'0'); 110 } 111 112 int main() { 113 for (auto [k, v] : m_num) rev_num[v] = k; 114 for (auto [k, v] : m_dir) rev_dir[v] = k; 115 116 string line; 117 int64_t tot = 0; 118 while (getline(cin, line)) { 119 string ppp; 120 int64_t num = numeric(line); 121 line = 'A' + line; 122 for (unsigned i = 0; i < line.size()-1; i++) 123 ppp += pushes_numpad(line[i], line[i+1]); 124 cout << ppp << endl; 125 tot += ppp.size() * num; 126 } 127 cout << tot << endl; 128 return 0; 129 }