1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
#include <fstream>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <string>
#include <tuple>
using namespace std;
using pos_type = tuple<size_t, size_t>;
using walls_type = set<pos_type>;
// pos, direction, score
using index_type = tuple<pos_type, size_t, int>;
struct index_compare {
bool operator()(const index_type& lhs, const index_type& rhs)
{
// compare score
return get<2>(lhs) > get<2>(rhs);
}
};
using index_pq = priority_queue<index_type, vector<index_type>, index_compare>;
static const array<pos_type, 4> dirs = {
pos_type{ -1, 0 },
pos_type{ 0, 1 },
pos_type{ 1, 0 },
pos_type{ 0, -1 }
};
tuple<walls_type, pos_type, pos_type>
read_file(string_view filename)
{
fstream input{ filename };
walls_type walls;
pos_type start;
pos_type finish;
size_t yPos = 0;
for ( string line; getline(input, line); ) {
for ( size_t xPos = 0; xPos != line.size(); ++xPos ) {
auto chr = line.at(xPos);
if ( chr == '#' ) {
walls.emplace(xPos, yPos);
}
else if ( chr == 'S' ) {
start = { xPos, yPos };
}
else if ( chr == 'E' ) {
finish = { xPos, yPos };
}
}
++yPos;
}
return { walls, start, finish };
}
void
print(const walls_type& walls, pos_type start, pos_type finish)
{
size_t width = 0;
size_t height = 0;
for ( const auto& [x, y]: walls ) {
width = max(width, x + 1);
height = max(height, y + 1);
}
for ( size_t yPos = 0; yPos != height; ++yPos ) {
for ( size_t xPos = 0; xPos != width; ++xPos ) {
const pos_type pos{ xPos, yPos };
if ( pos == start ) {
cout << 'S';
}
else if ( pos == finish ) {
cout << 'E';
}
else if ( walls.contains(pos) ) {
cout << '#';
}
else {
cout << '.';
}
}
cout << '\n';
}
cout << endl;
}
int
part1(const tuple<walls_type, pos_type, pos_type>& data)
{
const auto& [walls, start, finish] = data;
// pos, direction
set<tuple<pos_type, size_t>> seen;
index_pq queue;
queue.push({ start, 2, 0 });
while ( !queue.empty() ) {
const auto [pos, dir, score] = queue.top();
queue.pop();
if ( pos == finish ) {
return score;
}
if ( seen.contains({ pos, dir }) ) {
continue;
}
seen.insert({ pos, dir });
const auto delta = dirs.at(dir);
const pos_type next = { get<0>(pos) + get<0>(delta),
get<1>(pos) + get<1>(delta) };
if ( !walls.contains(next) ) {
queue.push({ next, dir, score + 1 });
}
queue.push({ pos, (dir + 1) % 4, score + 1000 });
queue.push({ pos, (dir + 3) % 4, score + 1000 });
}
return -1;
}
map<tuple<pos_type, size_t>, int>
walk(const tuple<walls_type, pos_type, pos_type>& data, const vector<index_type>& starts, size_t offset)
{
const auto& [walls, start, finish] = data;
set<tuple<pos_type, size_t>> seen;
map<tuple<pos_type, size_t>, int> scores;
index_pq queue{ starts.begin(), starts.end() };
while ( !queue.empty() ) {
const auto [pos, dir, score] = queue.top();
queue.pop();
if ( !scores.contains({ pos, dir }) ) {
scores[{ pos, dir }] = score;
}
if ( seen.contains({ pos, dir }) ) {
continue;
}
seen.insert({ pos, dir });
const auto delta = dirs.at((dir + offset) % 4);
const pos_type next = { get<0>(pos) + get<0>(delta),
get<1>(pos) + get<1>(delta) };
if ( !walls.contains(next) ) {
queue.push({ next, dir, score + 1 });
}
queue.push({ pos, (dir + 1) % 4, score + 1000 });
queue.push({ pos, (dir + 3) % 4, score + 1000 });
}
return scores;
}
size_t
part2(const tuple<walls_type, pos_type, pos_type>& data, int best)
{
const auto& [walls, start, finish] = data;
auto scores_forwards = walk({ walls, start, finish }, { { start, 2, 0 } }, 0);
auto scores_backwards = walk({ walls, finish, start }, { { finish, 0, 0 }, { finish, 1, 0 }, { finish, 2, 0 }, { finish, 3, 0 } }, 2);
set<pos_type> match;
for ( const auto& [pos_dir, score]: scores_forwards ) {
if ( scores_backwards.contains(pos_dir) && scores_backwards.at(pos_dir) + score == best ) {
const auto [pos, dir] = pos_dir;
match.insert(pos);
}
}
return match.size();
}
int
main()
{
auto data = read_file("data/day16.txt");
auto score = part1(data);
cout << score << endl;
cout << part2(data, score) << endl;
}
|
