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