109 lines
2.6 KiB
C++
109 lines
2.6 KiB
C++
|
#include "../../include/aoc.hpp"
|
||
|
|
#include <bits/stdc++.h>
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
const int ml = 25;
|
||
|
|
|
||
|
|
unordered_map<char, icoord> npad = {
|
||
|
|
{'7', {0, 0}}, {'8', {0, 1}}, {'9', {0, 2}}, {'4', {1, 0}},
|
||
|
|
{'5', {1, 1}}, {'6', {1, 2}}, {'1', {2, 0}}, {'2', {2, 1}},
|
||
|
|
{'3', {2, 2}}, {'0', {3, 1}}, {'A', {3, 2}},
|
||
|
|
};
|
||
|
|
|
||
|
|
unordered_map<char, icoord> dpad = {
|
||
|
|
{'^', {0, 1}}, {'A', {0, 2}}, {'<', {1, 0}}, {'v', {1, 1}}, {'>', {1, 2}},
|
||
|
|
};
|
||
|
|
|
||
|
|
unordered_map<icoord, char> dirs = {
|
||
|
|
{{-1, 0}, '^'},
|
||
|
|
{{0, 1}, '>'},
|
||
|
|
{{1, 0}, 'v'},
|
||
|
|
{{0, -1}, '<'},
|
||
|
|
};
|
||
|
|
|
||
|
|
inline size_t hc(icoord a, icoord b, int level) {
|
||
|
|
return (a.x) | (a.y << 4) | (b.x << 8) | (b.y << 12) | (level << 16);
|
||
|
|
}
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
ios::sync_with_stdio(0);
|
||
|
|
cin.tie(0);
|
||
|
|
|
||
|
|
unordered_set<icoord> npads, dpads;
|
||
|
|
for (auto &p : npad) {
|
||
|
|
npads.insert(p.second);
|
||
|
|
}
|
||
|
|
for (auto &p : dpad) {
|
||
|
|
dpads.insert(p.second);
|
||
|
|
}
|
||
|
|
|
||
|
|
unordered_map<size_t, ll> mm;
|
||
|
|
for (icoord start : dpads) {
|
||
|
|
for (icoord end : dpads) {
|
||
|
|
auto d = start - end;
|
||
|
|
mm[hc(start, end, 0)] = abs(d.x) + abs(d.y);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
for (int level = 1; level <= ml; level++) {
|
||
|
|
auto &pads = (level == ml) ? npads : dpads;
|
||
|
|
for (auto start : pads) {
|
||
|
|
mm[hc(start, start, level)] = 0;
|
||
|
|
for (auto end : pads) {
|
||
|
|
if (end == start) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
ll best = -1;
|
||
|
|
icoord d = end - start;
|
||
|
|
auto xc = dpad[(d.x > 0) ? 'v' : '^'];
|
||
|
|
auto yc = dpad[(d.y > 0) ? '>' : '<'];
|
||
|
|
if (d.x == 0) {
|
||
|
|
best = abs(d.y);
|
||
|
|
best += mm[hc(dpad['A'], yc, level - 1)];
|
||
|
|
best += mm[hc(yc, dpad['A'], level - 1)];
|
||
|
|
} else if (d.y == 0) {
|
||
|
|
best = abs(d.x);
|
||
|
|
best += mm[hc(dpad['A'], xc, level - 1)];
|
||
|
|
best += mm[hc(xc, dpad['A'], level - 1)];
|
||
|
|
} else {
|
||
|
|
for (int i = 0; i < 2; i++) {
|
||
|
|
icoord mid;
|
||
|
|
ll score = abs(d.x) + abs(d.y);
|
||
|
|
if (i == 0) {
|
||
|
|
mid = icoord(start.x, end.y);
|
||
|
|
score += mm[hc(dpad['A'], yc, level - 1)];
|
||
|
|
score += mm[hc(yc, xc, level - 1)];
|
||
|
|
score += mm[hc(xc, dpad['A'], level - 1)];
|
||
|
|
} else {
|
||
|
|
mid = icoord(end.x, start.y);
|
||
|
|
score += mm[hc(dpad['A'], xc, level - 1)];
|
||
|
|
score += mm[hc(xc, yc, level - 1)];
|
||
|
|
score += mm[hc(yc, dpad['A'], level - 1)];
|
||
|
|
}
|
||
|
|
if (pads.contains(mid) &&
|
||
|
|
(best == -1 || score < best)) {
|
||
|
|
best = score;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
mm[hc(start, end, level)] = best;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
ll tcount = 0;
|
||
|
|
string line;
|
||
|
|
while (getline(cin, line)) {
|
||
|
|
ll count = 0;
|
||
|
|
auto pos = npad['A'];
|
||
|
|
for (char c : line) {
|
||
|
|
auto newpos = npad[c];
|
||
|
|
count += mm[hc(pos, newpos, ml)] + 1;
|
||
|
|
pos = newpos;
|
||
|
|
}
|
||
|
|
tcount += count * stoi(line.substr(0, 3));
|
||
|
|
}
|
||
|
|
|
||
|
|
cout << tcount << '\n';
|
||
|
|
}
|