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
|
#include <array>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
vector<tuple<char, int>>
read_file(string_view filename)
{
fstream input{ filename };
vector<tuple<char, int>> result;
char dir = 0;
int count = 0;
while ( input >> dir >> count ) {
result.emplace_back(dir, count);
}
return result;
}
int
distance(const tuple<int, int>& head, const tuple<int, int>& tail)
{
auto dist_x = abs(get<0>(head) - get<0>(tail));
auto dist_y = abs(get<1>(head) - get<1>(tail));
return max(dist_x, dist_y);
};
static map<char, tuple<int, int>> direction = {
{ 'R', { +1, 0 } },
{ 'L', { -1, 0 } },
{ 'U', { 0, +1 } },
{ 'D', { 0, -1 } }
};
void
part1(const vector<tuple<char, int>>& data)
{
tuple<int, int> head = { 0, 0 };
tuple<int, int> tail = head;
set<tuple<int, int>> positions;
for ( auto [dir, count]: data ) {
while ( count-- > 0 ) {
const auto [delta_x, delta_y] = direction[dir];
const auto old_head = head;
get<0>(head) += delta_x;
get<1>(head) += delta_y;
if ( distance(head, tail) > 1 ) {
tail = old_head;
}
positions.insert(tail);
}
}
cout << positions.size() << endl;
}
void
part2(const vector<tuple<char, int>>& data)
{
static const auto rope_size = 10;
array<tuple<int, int>, rope_size> rope;
set<tuple<int, int>> positions;
for ( auto [dir, count]: data ) {
while ( count-- > 0 ) {
auto [delta_x, delta_y] = direction[dir];
get<0>(rope[0]) += delta_x;
get<1>(rope[0]) += delta_y;
for ( size_t i = 1; i < rope.size(); ++i ) {
auto& head = rope.at(i - 1);
auto& tail = rope.at(i);
if ( distance(head, tail) > 1 ) {
delta_x = get<0>(head) - get<0>(tail);
delta_y = get<1>(head) - get<1>(tail);
if ( abs(delta_x) > 1 ) {
delta_x /= abs(delta_x);
}
if ( abs(delta_y) > 1 ) {
delta_y /= abs(delta_y);
}
get<0>(tail) += delta_x;
get<1>(tail) += delta_y;
}
}
positions.insert(rope[9]);
}
}
cout << positions.size() << endl;
}
int
main()
{
const auto data = read_file("data/day09.txt");
part1(data);
part2(data);
}
|
