Line data Source code
1 : #include "PuzzleImpl.h"
2 :
3 : #include "AsciiMap.h"
4 : #include "Grid2d.h"
5 : #include "LinewiseInput.h"
6 :
7 : #include <libassert/assert.hpp>
8 :
9 : #include <algorithm>
10 : #include <ranges>
11 : #include <set>
12 : #include <string>
13 : #include <string_view>
14 : #include <tuple>
15 :
16 : using namespace std::literals;
17 :
18 : using Coord = Grid2d<char>::Coord;
19 :
20 : namespace {
21 :
22 0 : constexpr AsciiMap<Vec2<int>> makeMovementMap() {
23 0 : AsciiMap<Vec2<int>> map{{0, 0}};
24 0 : map['^'] = {0, 1};
25 0 : map['v'] = {0, -1};
26 0 : map['<'] = {-1, 0};
27 0 : map['>'] = {1, 0};
28 0 : return map;
29 0 : };
30 :
31 : constexpr AsciiMap<Vec2<int>> movementMap = makeMovementMap();
32 :
33 2 : auto parse(std::string_view const input) {
34 2 : auto const r = std::ranges::search(input, "\n\n"sv);
35 2 : std::string_view const gridStr{input.begin(), r.begin()};
36 2 : std::string_view const gridMovement{r.end(), input.end()};
37 :
38 2 : return std::make_tuple(LinewiseInput(gridStr).makeCharGrid2d(),
39 80074 : gridMovement | std::views::filter([](char const c) { return c != '\n'; }) |
40 40000 : std::views::transform([&](char const c) { return movementMap[c]; }) |
41 2 : std::ranges::to<std::vector<Vec2<int>>>());
42 2 : }
43 :
44 30017 : void moveSimple(Grid2d<char> &map, Coord &robotPos, Vec2<int> const &move) {
45 30017 : Coord pos = robotPos;
46 68952 : while (map[pos] != '#' && map[pos] != '.')
47 38935 : pos += move;
48 :
49 30017 : if (map[pos] == '#')
50 2926 : return;
51 :
52 30017 : ASSUME(map[pos] == '.');
53 :
54 61019 : for (; pos != robotPos; pos -= move)
55 33928 : std::swap(map[pos], map[pos - move]);
56 :
57 27091 : robotPos += move;
58 27091 : }
59 :
60 : class VerticalMover {
61 : public:
62 1 : VerticalMover(Grid2d<char> &map) : _map(&map), _columnStart(map.xSize()) {
63 1 : _curActiveColumns.reserve(map.xSize());
64 1 : }
65 :
66 9983 : Coord operator()(Coord robotPos, Vec2<int> const move) {
67 9983 : ASSUME(move.y() != 0);
68 9983 : Grid2d<char> &map = *_map;
69 :
70 9983 : std::ranges::fill(_columnStart, -1);
71 9983 : std::set<int> activeColumns;
72 9983 : activeColumns.insert(robotPos.x());
73 9983 : _columnStart[robotPos.x()] = robotPos.y();
74 9983 : int y = robotPos.y();
75 :
76 9983 : _pendingShifts.clear();
77 :
78 21978 : while (!activeColumns.empty()) {
79 13424 : int nextY = y + move.y();
80 13424 : _curActiveColumns.assign(activeColumns.begin(), activeColumns.end());
81 16625 : for (int const x : _curActiveColumns) {
82 16625 : switch (map[x, nextY]) {
83 1429 : case '#':
84 1429 : return robotPos;
85 10279 : case '.':
86 10279 : ASSUME(_columnStart[x] != -1);
87 10279 : _pendingShifts.emplace_back(Coord{x, _columnStart[x]}, Coord{x, nextY});
88 10279 : _columnStart[x] = -1;
89 10279 : activeColumns.erase(x);
90 10279 : break;
91 2457 : case '[':
92 2457 : if (activeColumns.insert(x + 1).second) {
93 1314 : ASSUME(_columnStart[x + 1] == -1);
94 1314 : _columnStart[x + 1] = nextY;
95 1314 : }
96 2457 : break;
97 2460 : case ']':
98 2460 : if (activeColumns.insert(x - 1).second) {
99 1317 : ASSUME(_columnStart[x - 1] == -1);
100 1317 : _columnStart[x - 1] = nextY;
101 1317 : }
102 2460 : break;
103 0 : default:
104 0 : UNREACHABLE(map[x, nextY]);
105 16625 : }
106 16625 : }
107 11995 : y = nextY;
108 11995 : }
109 :
110 8554 : for (auto const &c : _pendingShifts)
111 22308 : for (auto pos = c.second; pos != c.first; pos -= move)
112 12456 : std::swap(map[pos], map[pos - move]);
113 :
114 8554 : return robotPos + move;
115 9983 : }
116 :
117 : private:
118 : Grid2d<char> *_map;
119 : std::vector<int> _columnStart;
120 : std::vector<std::pair<Coord, Coord>> _pendingShifts;
121 : std::vector<int> _curActiveColumns;
122 : };
123 :
124 1 : Grid2d<char> widenMap(Grid2d<char> const &map) {
125 1 : Grid2d<char> widenedMap(map.xSize() * 2, map.ySize());
126 :
127 51 : for (int y = 0; y < map.ySize(); ++y)
128 2550 : for (int x = 0; x < map.xSize(); ++x)
129 2500 : switch (map[x, y]) {
130 1 : case '@':
131 1 : widenedMap[x * 2, y] = '@';
132 1 : widenedMap[x * 2 + 1, y] = '.';
133 1 : break;
134 594 : case 'O':
135 594 : widenedMap[x * 2, y] = '[';
136 594 : widenedMap[x * 2 + 1, y] = ']';
137 594 : break;
138 1905 : default:
139 1905 : widenedMap[x * 2, y] = map[x, y];
140 1905 : widenedMap[x * 2 + 1, y] = map[x, y];
141 2500 : }
142 1 : return widenedMap;
143 1 : }
144 :
145 : } // namespace
146 :
147 1 : template <> std::string solvePart1<2024, 15>(std::string_view const input) {
148 1 : auto [map, moves] = parse(input);
149 :
150 1 : auto robotPos = map.find('@');
151 :
152 1 : for (auto m : moves)
153 20000 : moveSimple(map, robotPos, m);
154 :
155 1 : return std::to_string(std::ranges::fold_left(
156 594 : map.flipY().findAll('O') | std::views::transform([&](auto c) { return c.y() * 100 + c.x(); }),
157 1 : int64_t(0), std::plus{}));
158 1 : }
159 :
160 1 : template <> std::string solvePart2<2024, 15>(std::string_view const input) {
161 1 : auto [map, moves] = parse(input);
162 :
163 1 : map = widenMap(map);
164 :
165 1 : auto robotPos = map.find('@');
166 :
167 1 : VerticalMover verticalMover(map);
168 :
169 20000 : for (auto move : moves) {
170 20000 : if (move.y() == 0)
171 10017 : moveSimple(map, robotPos, move);
172 9983 : else
173 9983 : robotPos = verticalMover(robotPos, move);
174 20000 : }
175 :
176 1 : return std::to_string(std::ranges::fold_left(
177 594 : map.flipY().findAll('[') | std::views::transform([&](auto c) { return c.y() * 100 + c.x(); }),
178 1 : int64_t(0), std::plus{}));
179 1 : }
|
