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
|
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using pos_type = tuple<long, long>;
vector<pos_type>
read_file(string_view filename)
{
fstream input{ filename };
vector<pos_type> data;
long lhs = 0;
long rhs = 0;
char chr = 0;
while ( input >> lhs >> chr >> rhs ) {
data.emplace_back(lhs, rhs);
}
return data;
}
optional<long>
bfs(const vector<pos_type>& data, long size)
{
set<pos_type> stones{ data.begin(), data.end() };
set<pos_type> seen;
// x, y, distance
queue<tuple<pos_type, long>> queue;
queue.push({ { 0, 0 }, 0 });
while ( !queue.empty() ) {
const auto& [pos, distance] = queue.front();
queue.pop();
const auto [x, y] = pos;
if ( x == size && y == size ) {
return distance;
}
if ( x < 0 || y < 0 || x > size || y > size ) {
continue;
}
if ( stones.contains(pos) ) {
continue;
}
if ( seen.contains(pos) ) {
continue;
}
seen.insert(pos);
for ( const auto& [nx, ny]: vector<pos_type>{ { x - 1, y }, { x + 1, y }, { x, y - 1 }, { x, y + 1 } } ) {
queue.push({ { nx, ny }, distance + 1 });
}
}
return nullopt;
}
void
part1(const vector<pos_type>& data, long size)
{
if ( auto result = bfs(data, size) ) {
cout << *result << endl;
}
}
void
part2(const vector<pos_type>& data, long size)
{
size_t lhs = 0;
size_t rhs = data.size() - 1;
while ( lhs < rhs ) {
auto mid = lhs + (rhs - lhs) / 2;
if ( bfs({ data.begin(), data.begin() + ptrdiff_t(mid + 1) }, size) ) {
lhs = mid + 1;
}
else {
rhs = mid;
}
}
const auto& [x, y] = data[lhs];
cout << x << "," << y << endl;
}
int
main()
{
#if 0
const auto data = read_file("data/day18-sample1.txt");
const long size = 6;
part1({ data.begin(), data.begin() + 12 }, size);
part2(data, size);
#else
const auto data = read_file("data/day18.txt");
const long size = 70;
part1({ data.begin(), data.begin() + 1024 }, size);
part2(data, size);
#endif
}
|
