aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--2017/src/day01.cpp44
-rw-r--r--2017/src/day02.cpp71
-rw-r--r--2017/src/day03.cpp94
-rw-r--r--2017/src/day04.cpp78
-rw-r--r--2017/src/day05.cpp57
-rw-r--r--2017/src/day06.cpp82
-rw-r--r--2017/src/day07.cpp145
-rw-r--r--2017/src/day08.cpp118
-rw-r--r--2017/src/day09.cpp75
-rw-r--r--2017/src/day10.cpp124
-rw-r--r--2017/src/day11.cpp104
-rw-r--r--2017/src/day12.cpp115
-rw-r--r--2017/src/day13.cpp77
-rw-r--r--2017/src/day14.cpp146
-rw-r--r--2017/src/day15.cpp73
-rw-r--r--2017/src/day16.cpp174
-rw-r--r--2017/src/day17.cpp47
-rw-r--r--2017/src/day18.cpp266
-rw-r--r--2017/src/day19.cpp97
-rw-r--r--2017/src/day20.cpp162
20 files changed, 2148 insertions, 1 deletions
diff --git a/2017/src/day01.cpp b/2017/src/day01.cpp
index 4a3fd99..f8297e7 100644
--- a/2017/src/day01.cpp
+++ b/2017/src/day01.cpp
@@ -1,9 +1,51 @@
1#include <filesystem>
2#include <fstream>
1#include <iostream> 3#include <iostream>
4#include <string>
2 5
3using namespace std; 6using namespace std;
4 7
8namespace {
9
10string
11read_line(const filesystem::path& filename)
12{
13 ifstream file{ filename };
14 string line;
15 getline(file, line);
16 return line;
17}
18
19long
20calculate(string_view captcha, size_t offset)
21{
22 long sum = 0;
23 for ( size_t i = 0; i != captcha.size(); ++i ) {
24 if ( captcha[i] == captcha[(i + offset) % captcha.size()] ) {
25 sum += captcha[i] - '0';
26 }
27 }
28 return sum;
29}
30
31void
32part1(string_view captcha)
33{
34 cout << "Part1: " << calculate(captcha, 1) << '\n';
35}
36
37void
38part2(string_view captcha)
39{
40 cout << "Part2: " << calculate(captcha, captcha.size() / 2) << '\n';
41}
42
43} // namespace
44
5int 45int
6main() 46main()
7{ 47{
8 cout << "Hallo Welt" << '\n'; 48 auto captcha = read_line("data/day01.txt");
49 part1(captcha);
50 part2(captcha);
9} 51}
diff --git a/2017/src/day02.cpp b/2017/src/day02.cpp
new file mode 100644
index 0000000..5f965bd
--- /dev/null
+++ b/2017/src/day02.cpp
@@ -0,0 +1,71 @@
1#include <algorithm>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <sstream>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13vector<vector<int>>
14read_file(const filesystem::path& filename)
15{
16 ifstream file{ filename };
17 vector<vector<int>> grid;
18
19 for ( string line; getline(file, line); ) {
20 stringstream strm{ line };
21
22 vector<int> row;
23
24 for ( int value{}; strm >> value; ) {
25 row.emplace_back(value);
26 }
27
28 grid.emplace_back(row);
29 }
30
31 return grid;
32}
33
34void
35part1(const vector<vector<int>>& grid)
36{
37 int checksum = 0;
38 for ( const auto& row: grid ) {
39 auto [min, max] = ranges::minmax_element(row);
40 checksum += *max - *min;
41 }
42 cout << "Part1: " << checksum << '\n';
43}
44
45void
46part2(const vector<vector<int>>& grid)
47{
48 int checksum = 0;
49 for ( auto row: grid ) {
50 ranges::sort(row, ranges::greater());
51
52 for ( auto it = row.begin(); it != row.end(); ++it ) {
53 for ( auto it2 = next(it); it2 != row.end(); ++it2 ) {
54 if ( *it % *it2 == 0 ) {
55 checksum += *it / *it2;
56 }
57 }
58 }
59 }
60 cout << "Part2: " << checksum << '\n';
61}
62
63} // namespace
64
65int
66main()
67{
68 auto grid = read_file("data/day02.txt");
69 part1(grid);
70 part2(grid);
71}
diff --git a/2017/src/day03.cpp b/2017/src/day03.cpp
new file mode 100644
index 0000000..417cef3
--- /dev/null
+++ b/2017/src/day03.cpp
@@ -0,0 +1,94 @@
1#include <algorithm>
2#include <array>
3#include <cmath>
4#include <iostream>
5#include <map>
6
7using namespace std;
8
9namespace {
10
11void
12part1(int value)
13{
14 auto ring = static_cast<int>(ceil((sqrt(value) - 1) / 2));
15 auto side_len = (2 * ring) + 1;
16 auto max_value = side_len * side_len;
17
18 array<int, 4> centers = {
19 max_value - ring - (2 * ring * 0),
20 max_value - ring - (2 * ring * 1),
21 max_value - ring - (2 * ring * 2),
22 max_value - ring - (2 * ring * 3)
23 };
24
25 auto* itr = ranges::min_element(centers, {}, [value](int rhs) { return abs(value - rhs); });
26
27 auto dist_to_center = abs(value - *itr);
28
29 cout << "Part1: " << ring + dist_to_center << '\n';
30}
31
32void
33part2(int value)
34{
35 static const array<tuple<int, int>, 4> dirs{
36 make_tuple(1, 0), // right
37 make_tuple(0, -1), // up
38 make_tuple(-1, 0), // left
39 make_tuple(0, 1), // down
40 };
41
42 static const array<int, 3> offsets = { -1, 0, 1 };
43
44 map<tuple<int, int>, int> grid; // (x,y) => value
45
46 int x = 0;
47 int y = 0;
48 int steps = 1;
49
50 grid[{ x, y }] = 1;
51
52 while ( true ) {
53 for ( const auto [dx, dy]: dirs ) {
54 for ( int _ = 0; _ != steps; ++_ ) {
55 x += dx;
56 y += dy;
57
58 int sum = 0;
59 for ( const auto off_x: offsets ) {
60 for ( const auto off_y: offsets ) {
61 if ( off_x == 0 && off_y == 0 ) {
62 continue;
63 }
64
65 const auto pos = make_tuple(x + off_x, y + off_y);
66 if ( grid.contains(pos) ) {
67 sum += grid.at(pos);
68 }
69 }
70 }
71
72 if ( sum > value ) {
73 cout << "Part2: " << sum << '\n';
74 return;
75 }
76
77 grid[{ x, y }] = sum;
78 }
79 if ( dx == 0 ) {
80 ++steps;
81 }
82 }
83 }
84}
85
86} // namespace
87
88int
89main()
90{
91 static const auto puzzle = 265149;
92 part1(puzzle);
93 part2(puzzle);
94}
diff --git a/2017/src/day04.cpp b/2017/src/day04.cpp
new file mode 100644
index 0000000..01e89b2
--- /dev/null
+++ b/2017/src/day04.cpp
@@ -0,0 +1,78 @@
1#include <algorithm>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <set>
6#include <sstream>
7#include <string>
8
9using namespace std;
10
11namespace {
12
13vector<string>
14read_lines(const filesystem::path& filename)
15{
16 ifstream file{ filename };
17 vector<string> lines;
18
19 for ( string line; getline(file, line); ) {
20 lines.emplace_back(line);
21 }
22
23 return lines;
24}
25
26vector<string>
27split(const string& line)
28{
29 stringstream strm{ line };
30 vector<string> words;
31
32 for ( string word; strm >> word; ) {
33 words.emplace_back(word);
34 }
35
36 return words;
37}
38
39void
40part1(const vector<string>& lines)
41{
42 auto num = ranges::count_if(lines, [](const string& line) {
43 auto words = split(line);
44 set<string> set{ words.begin(), words.end() };
45
46 return set.size() == words.size();
47 });
48
49 cout << "Part1: " << num << '\n';
50}
51
52void
53part2(const vector<string>& lines)
54{
55 auto num = ranges::count_if(lines, [](const string& line) {
56 auto words = split(line);
57 set<string> set;
58
59 for ( auto word: words ) {
60 ranges::sort(word);
61 set.insert(word);
62 }
63
64 return set.size() == words.size();
65 });
66
67 cout << "Part2: " << num << '\n';
68}
69
70} // namespace
71
72int
73main()
74{
75 auto lines = read_lines("data/day04.txt");
76 part1(lines);
77 part2(lines);
78}
diff --git a/2017/src/day05.cpp b/2017/src/day05.cpp
new file mode 100644
index 0000000..93656b6
--- /dev/null
+++ b/2017/src/day05.cpp
@@ -0,0 +1,57 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4
5using namespace std;
6
7namespace {
8
9vector<int>
10read_lines(const filesystem::path& filename)
11{
12 ifstream file{ filename };
13 vector<int> lines;
14
15 for ( int value{}; file >> value; ) {
16 lines.emplace_back(value);
17 }
18
19 return lines;
20}
21
22void
23part1(vector<int> values)
24{
25 int steps = 0;
26 for ( size_t ip = 0; ip < values.size(); ) {
27 auto offset = values[ip]++;
28 ip += static_cast<size_t>(offset);
29 ++steps;
30 }
31
32 cout << "Part1: " << steps << '\n';
33}
34
35void
36part2(vector<int> values)
37{
38 int steps = 0;
39 for ( size_t ip = 0; ip < values.size(); ) {
40 auto offset = values[ip];
41 values[ip] += (offset >= 3) ? -1 : 1;
42 ip += static_cast<size_t>(offset);
43 ++steps;
44 }
45
46 cout << "Part2: " << steps << '\n';
47}
48
49} // namespace
50
51int
52main()
53{
54 auto values = read_lines("data/day05.txt");
55 part1(values);
56 part2(values);
57}
diff --git a/2017/src/day06.cpp b/2017/src/day06.cpp
new file mode 100644
index 0000000..596ca2c
--- /dev/null
+++ b/2017/src/day06.cpp
@@ -0,0 +1,82 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <set>
6#include <vector>
7
8using namespace std;
9
10namespace {
11
12vector<int>
13read_lines(const filesystem::path& filename)
14{
15 ifstream file{ filename };
16 vector<int> lines;
17
18 for ( int value{}; file >> value; ) {
19 lines.emplace_back(value);
20 }
21
22 return lines;
23}
24
25void
26distribute(vector<int>& values)
27{
28 auto iter = ranges::max_element(values);
29 auto max_value = *iter;
30
31 *iter = 0;
32
33 while ( max_value-- > 0 ) {
34 ++iter;
35 if ( iter == values.end() ) {
36 iter = values.begin();
37 }
38 *iter += 1;
39 }
40}
41
42void
43part1(vector<int> values)
44{
45 set<vector<int>> seen;
46 for ( int step = 0;; ++step ) {
47 if ( seen.contains(values) ) {
48 cout << "Part1: " << step << '\n';
49 return;
50 }
51
52 seen.insert(values);
53
54 distribute(values);
55 }
56}
57
58void
59part2(vector<int> values)
60{
61 map<vector<int>, int> seen;
62 for ( int step = 0;; ++step ) {
63 if ( seen.contains(values) ) {
64 cout << "Part2: " << step - seen.at(values) << '\n';
65 return;
66 }
67
68 seen.emplace(values, step);
69
70 distribute(values);
71 }
72}
73
74} // namespace
75
76int
77main()
78{
79 auto values = read_lines("data/day06.txt");
80 part1(values);
81 part2(values);
82}
diff --git a/2017/src/day07.cpp b/2017/src/day07.cpp
new file mode 100644
index 0000000..899375d
--- /dev/null
+++ b/2017/src/day07.cpp
@@ -0,0 +1,145 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <numeric>
6#include <vector>
7
8using namespace std;
9
10namespace {
11
12struct Node {
13 int weight;
14 optional<string> parent;
15 vector<string> children;
16};
17
18vector<string>
19split(const string& line, const string& delimiters)
20{
21 vector<string> result;
22
23 size_t start = 0;
24 size_t end = 0;
25
26 while ( (end = line.find_first_of(delimiters, start)) != string::npos ) {
27 if ( end != start ) {
28 result.emplace_back(line.substr(start, end - start));
29 }
30
31 start = end + 1;
32 }
33
34 if ( start != line.size() ) {
35 result.emplace_back(line.substr(start));
36 }
37
38 return result;
39}
40
41map<string, Node>
42read_file(const filesystem::path& filename)
43{
44 ifstream file{ filename };
45
46 map<string, Node> data; // name -> (weight, parent)
47
48 for ( string line; getline(file, line); ) {
49 const auto parts = split(line, " ()->,");
50 const auto& parent = parts.at(0);
51
52 data[parent].weight = stoi(parts.at(1));
53
54 for ( size_t idx = 2; idx != parts.size(); ++idx ) {
55 const auto& child = parts.at(idx);
56 data[child].parent = parent;
57 data[parent].children.emplace_back(child);
58 }
59 }
60
61 return data;
62}
63
64string
65root_node(const map<string, Node>& data)
66{
67 for ( const auto& [name, node]: data ) {
68 if ( !node.parent ) {
69 return name;
70 }
71 }
72 throw runtime_error("no root found");
73}
74
75void
76part1(const map<string, Node>& data)
77{
78 cout << "Part1: " << root_node(data) << '\n';
79}
80
81int
82calculate_weight(const map<string, Node>& data, const string& name) // NOLINT
83{
84 const auto& node = data.at(name);
85
86 if ( node.children.empty() ) {
87 return node.weight;
88 }
89
90 int total_weight = node.weight;
91
92 map<string, int> child_weights;
93 for ( const auto& child: node.children ) {
94 auto child_weight = calculate_weight(data, child);
95 child_weights.emplace(child, child_weight);
96 total_weight += child_weight;
97 }
98
99 map<int, vector<string>> grouped;
100 for ( const auto& [child, weight]: child_weights ) {
101 grouped[weight].emplace_back(child);
102 }
103
104 if ( grouped.size() != 1 ) {
105 int wrong_weight{};
106 int correct_weight{};
107 string wrong_name;
108
109 for ( const auto& [weight, names]: grouped ) {
110 if ( names.size() == 1 ) {
111 wrong_weight = weight;
112 wrong_name = names.front();
113 }
114 else {
115 correct_weight = weight;
116 }
117 }
118
119 const auto& wrong_node = data.at(wrong_name);
120 auto diff = wrong_weight - correct_weight;
121
122 cout << "Part2: " << wrong_node.weight - diff << '\n';
123
124 exit(0);
125 }
126
127 return total_weight;
128}
129
130void
131part2(const map<string, Node>& data)
132{
133 auto node = root_node(data);
134 calculate_weight(data, node);
135}
136
137} // namespace
138
139int
140main()
141{
142 auto data = read_file("data/day07.txt");
143 part1(data);
144 part2(data);
145}
diff --git a/2017/src/day08.cpp b/2017/src/day08.cpp
new file mode 100644
index 0000000..64c1ea0
--- /dev/null
+++ b/2017/src/day08.cpp
@@ -0,0 +1,118 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <sstream>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13vector<string>
14split(const string& line, char sep = ' ')
15{
16 stringstream strm{ line };
17 vector<string> parts;
18
19 for ( string part; getline(strm, part, sep); ) {
20 parts.emplace_back(part);
21 }
22
23 return parts;
24}
25
26vector<vector<string>>
27read_file(const filesystem::path& filename)
28{
29 ifstream file{ filename };
30 vector<vector<string>> data;
31
32 for ( string line; getline(file, line); ) {
33 auto parts = split(line);
34 data.emplace_back(parts);
35 }
36
37 return data;
38}
39
40void
41compute(const vector<vector<string>>& data, map<string, int>& memory, int& max_value)
42{
43 auto match = [](int lhs, string_view rel, int rhs) {
44 if ( rel == "==" ) {
45 return lhs == rhs;
46 }
47 else if ( rel == "!=" ) {
48 return lhs != rhs;
49 }
50 else if ( rel == "<" ) {
51 return lhs < rhs;
52 }
53 else if ( rel == "<=" ) {
54 return lhs <= rhs;
55 }
56 else if ( rel == ">" ) {
57 return lhs > rhs;
58 }
59 else if ( rel == ">=" ) {
60 return lhs >= rhs;
61 }
62
63 throw runtime_error("unknown relation operator: "s + string(rel));
64 };
65
66 auto execute = [&](const string& reg, string_view opcode, int value) {
67 if ( opcode == "inc" ) {
68 memory[reg] += value;
69 }
70 else if ( opcode == "dec" ) {
71 memory[reg] -= value;
72 }
73 else {
74 throw runtime_error("unknown opcode: "s + string(opcode));
75 }
76 };
77
78 for ( const auto& instr: data ) {
79 const auto& reg = instr.at(0);
80 const auto& opcode = instr.at(1);
81 const auto value = stoi(instr.at(2));
82 const auto lhs = memory[instr.at(4)];
83 const auto& rel = instr.at(5);
84 const auto rhs = stoi(instr.at(6));
85
86 if ( match(lhs, rel, rhs) ) {
87 execute(reg, opcode, value);
88 max_value = max(max_value, memory[reg]);
89 }
90 }
91}
92
93void
94solve(const vector<vector<string>>& data)
95{
96 map<string, int> memory;
97 auto max_value = numeric_limits<int>::min();
98
99 compute(data, memory, max_value);
100
101 auto itr = ranges::max_element(memory, [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; });
102 cout << "Part1: " << itr->second << '\n';
103 cout << "Part2: " << max_value << '\n';
104}
105
106} // namespace
107
108int
109main()
110{
111 auto data = read_file("data/day08.txt");
112 try {
113 solve(data);
114 }
115 catch ( exception& e ) {
116 cerr << "Fehler: " << e.what() << '\n';
117 }
118}
diff --git a/2017/src/day09.cpp b/2017/src/day09.cpp
new file mode 100644
index 0000000..60b0d3b
--- /dev/null
+++ b/2017/src/day09.cpp
@@ -0,0 +1,75 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <iterator>
5#include <string>
6
7using namespace std;
8
9namespace {
10
11string
12remove_garbage(string_view line, int& removed)
13{
14 string result;
15
16 removed = 0;
17 for ( size_t pos = 0; pos < line.size(); ) {
18 if ( line.at(pos) == '<' ) {
19 ++pos;
20 while ( pos < line.size() && line.at(pos) != '>' ) {
21 if ( line.at(pos) == '!' ) {
22 pos += 2;
23 }
24 else {
25 ++pos;
26 ++removed;
27 }
28 }
29 ++pos;
30 }
31 else {
32 result += line.at(pos);
33 ++pos;
34 }
35 }
36
37 return result;
38}
39
40string
41read_file(const filesystem::path& filename)
42{
43 ifstream file{ filename };
44 return { istreambuf_iterator<char>{ file }, {} };
45}
46
47void
48solve(string_view data)
49{
50 int score = 0;
51 int depth = 0;
52 int removed = 0;
53
54 for ( const auto chr: remove_garbage(data, removed) ) {
55 if ( chr == '{' ) {
56 ++depth;
57 }
58 else if ( chr == '}' ) {
59 score += depth;
60 --depth;
61 }
62 }
63
64 cout << "Part1: " << score << '\n';
65 cout << "Part2: " << removed << '\n';
66}
67
68} // namespace
69
70int
71main()
72{
73 auto data = read_file("data/day09.txt");
74 solve(data);
75}
diff --git a/2017/src/day10.cpp b/2017/src/day10.cpp
new file mode 100644
index 0000000..d300a06
--- /dev/null
+++ b/2017/src/day10.cpp
@@ -0,0 +1,124 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <numeric>
5#include <sstream>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13string
14read_file(const filesystem::path& filename)
15{
16 ifstream file{ filename };
17 string line;
18 getline(file, line);
19 return line;
20}
21
22vector<size_t>
23split(const string& line)
24{
25 stringstream strm{ line };
26 vector<size_t> data;
27
28 for ( string word; getline(strm, word, ','); ) {
29 data.emplace_back(stoul(word));
30 }
31
32 return data;
33}
34
35vector<unsigned>
36gen_data(size_t len)
37{
38 vector<unsigned> data(len);
39 iota(data.begin(), data.end(), 0UL);
40 return data;
41}
42
43void
44reverse(vector<unsigned>& data, size_t start, size_t len)
45{
46 auto end = start + len;
47
48 while ( start < end ) {
49 swap(data.at(start++ % data.size()), data.at(--end % data.size()));
50 }
51}
52
53void
54hash(vector<unsigned>& data, const vector<size_t>& lengths)
55{
56 size_t pos = 0;
57 for ( size_t skip = 0; skip != lengths.size(); ++skip ) {
58 reverse(data, pos, lengths.at(skip));
59 pos += lengths.at(skip) + skip;
60 }
61}
62
63void
64part1(size_t len, const string& line)
65{
66 auto data = gen_data(len);
67 auto lengths = split(line);
68
69 hash(data, lengths);
70
71 cout << "Part1: " << data.at(0) * data.at(1) << '\n';
72}
73
74void
75hash64(vector<unsigned>& data, const vector<size_t>& lengths)
76{
77 size_t pos = 0;
78 size_t skip = 0;
79 for ( size_t i = 0; i != 64; ++i ) {
80 for ( auto length: lengths ) {
81 reverse(data, pos, length);
82 pos += length + skip;
83 ++skip;
84 }
85 }
86}
87
88void
89part2(string line)
90{
91 line += char(17);
92 line += char(31);
93 line += char(73);
94 line += char(47);
95 line += char(23);
96
97 vector<size_t> lengths;
98 for ( const auto byte: line ) {
99 lengths.emplace_back(static_cast<unsigned char>(byte));
100 }
101
102 auto data = gen_data(256);
103 hash64(data, lengths);
104
105 cout << "Part2: ";
106 for ( size_t i = 0; i != 256; i += 16 ) {
107 size_t value = 0;
108 for ( size_t j = 0; j != 16; ++j ) {
109 value ^= data.at(i + j);
110 }
111 cout << setw(2) << setfill('0') << hex << (value & 0xFF);
112 }
113 cout << '\n';
114}
115
116} // namespace
117
118int
119main()
120{
121 auto line = read_file("data/day10.txt");
122 part1(256, line);
123 part2(line);
124}
diff --git a/2017/src/day11.cpp b/2017/src/day11.cpp
new file mode 100644
index 0000000..ea945c1
--- /dev/null
+++ b/2017/src/day11.cpp
@@ -0,0 +1,104 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <sstream>
6#include <string>
7#include <vector>
8
9// see: https://www.redblobgames.com/grids/hexagons/
10
11using namespace std;
12
13namespace {
14
15string
16read_file(const filesystem::path& filename)
17{
18 ifstream file{ filename };
19 string line;
20 getline(file, line);
21 return line;
22}
23
24vector<string>
25split(const string& line)
26{
27 stringstream strm{ line };
28 vector<string> data;
29
30 for ( string word; getline(strm, word, ','); ) {
31 data.emplace_back(word);
32 }
33
34 return data;
35}
36
37void
38part1(const vector<string>& steps)
39{
40 // string => (q, s, r)
41 map<string, tuple<int, int, int>> dirs{
42 { "n", { 0, 1, -1 } },
43 { "nw", { -1, 1, 0 } },
44 { "sw", { -1, 0, 1 } },
45 { "s", { 0, -1, 1 } },
46 { "se", { 1, -1, 0 } },
47 { "ne", { 1, 0, -1 } }
48 };
49
50 tuple<int, int, int> current = { 0, 0, 0 };
51 for ( const auto& step: steps ) {
52 const auto [dq, ds, dr] = dirs.at(step);
53
54 get<0>(current) += dq;
55 get<1>(current) += ds;
56 get<2>(current) += dr;
57 }
58
59 auto dist = (abs(get<0>(current)) + abs(get<1>(current)) + abs(get<2>(current))) / 2;
60
61 cout << "Part1: " << dist << '\n';
62}
63
64void
65part2(const vector<string>& steps)
66{
67 // string => (q, s, r)
68 map<string, tuple<int, int, int>> dirs{
69 { "n", { 0, 1, -1 } },
70 { "nw", { -1, 1, 0 } },
71 { "sw", { -1, 0, 1 } },
72 { "s", { 0, -1, 1 } },
73 { "se", { 1, -1, 0 } },
74 { "ne", { 1, 0, -1 } }
75 };
76
77 int max_dist = 0;
78
79 tuple<int, int, int> current = { 0, 0, 0 };
80 for ( const auto& step: steps ) {
81 const auto [dq, ds, dr] = dirs.at(step);
82
83 get<0>(current) += dq;
84 get<1>(current) += ds;
85 get<2>(current) += dr;
86
87 auto dist = (abs(get<0>(current)) + abs(get<1>(current)) + abs(get<2>(current))) / 2;
88
89 max_dist = max(max_dist, dist);
90 }
91
92 cout << "Part2: " << max_dist << '\n';
93}
94
95} // namespace
96
97int
98main()
99{
100 auto line = read_file("data/day11.txt");
101 auto steps = split(line);
102 part1(steps);
103 part2(steps);
104}
diff --git a/2017/src/day12.cpp b/2017/src/day12.cpp
new file mode 100644
index 0000000..66bf186
--- /dev/null
+++ b/2017/src/day12.cpp
@@ -0,0 +1,115 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <queue>
6#include <set>
7#include <string>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14using graph_type = map<int, set<int>>;
15
16vector<int>
17split_to_int(const string& line, const string& delimiters)
18{
19 vector<int> result;
20
21 size_t start = 0;
22 size_t end = 0;
23
24 while ( (end = line.find_first_of(delimiters, start)) != string::npos ) {
25 if ( end != start ) {
26 result.emplace_back(stoi(line.substr(start, end - start)));
27 }
28
29 start = end + 1;
30 }
31
32 if ( start != line.size() ) {
33 result.emplace_back(stoi(line.substr(start)));
34 }
35
36 return result;
37}
38
39graph_type
40read_lines(const filesystem::path& filename)
41{
42 ifstream file{ filename };
43 graph_type result;
44
45 for ( string line; getline(file, line); ) {
46 auto parts = split_to_int(line, "<-> ,");
47
48 for ( size_t i = 1; i < parts.size(); ++i ) {
49 result[parts[0]].insert(parts[i]);
50 result[parts[i]].insert(parts[0]);
51 }
52 }
53
54 return result;
55}
56
57void
58bfs_mark(const graph_type& graph, int start, set<int>& seen)
59{
60 queue<int> queue;
61
62 queue.emplace(start);
63 seen.emplace(start);
64
65 while ( !queue.empty() ) {
66 int prg = queue.front();
67 queue.pop();
68
69 for ( auto link: graph.at(prg) ) {
70 if ( !seen.contains(link) ) {
71 queue.emplace(link);
72 seen.emplace(link);
73 }
74 }
75 }
76}
77
78void
79part1(const graph_type& graph)
80{
81 set<int> seen;
82
83 bfs_mark(graph, 0, seen);
84
85 cout << "Part1: " << seen.size() << '\n';
86}
87
88void
89part2(const graph_type& graph)
90{
91 set<int> seen;
92
93 int count = 0;
94
95 for ( const auto& [i, _]: graph ) {
96 if ( seen.contains(i) ) {
97 continue;
98 }
99
100 ++count;
101
102 bfs_mark(graph, i, seen);
103 }
104 cout << "Part2: " << count << '\n';
105}
106
107} // namespace
108
109int
110main()
111{
112 auto data = read_lines("data/day12.txt");
113 part1(data);
114 part2(data);
115}
diff --git a/2017/src/day13.cpp b/2017/src/day13.cpp
new file mode 100644
index 0000000..759f302
--- /dev/null
+++ b/2017/src/day13.cpp
@@ -0,0 +1,77 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <tuple>
5#include <vector>
6
7using namespace std;
8
9namespace {
10
11vector<tuple<unsigned long, unsigned long>>
12read_file(const filesystem::path& filename)
13{
14 ifstream file{ filename };
15 unsigned long depth = 0;
16 unsigned long range = 0;
17 char colon = 0;
18
19 vector<tuple<unsigned long, unsigned long>> data;
20
21 while ( file >> depth >> colon >> range ) {
22 data.emplace_back(depth, range);
23 }
24
25 return data;
26}
27
28template<typename T>
29T
30get_pos(T depth, T range, T time)
31{
32 const auto period = 2 * (range - 1);
33 const auto remainder = (depth + time) % period;
34 return remainder < range ? remainder : period - remainder;
35}
36
37void
38part1(const vector<tuple<unsigned long, unsigned long>>& data)
39{
40 unsigned long sum = 0;
41 for ( const auto [depth, range]: data ) {
42 if ( get_pos(depth, range, 0UL) == 0 ) {
43 sum += depth * range;
44 }
45 }
46 cout << "Part1: " << sum << '\n';
47}
48
49void
50part2(const vector<tuple<unsigned long, unsigned long>>& data)
51{
52 for ( unsigned long delay = 0;; ++delay ) {
53 bool pass = true;
54
55 for ( const auto [depth, range]: data ) {
56 if ( get_pos(depth, range, delay) == 0 ) {
57 pass = false;
58 break;
59 }
60 }
61
62 if ( pass ) {
63 cout << "Part2: " << delay << '\n';
64 return;
65 }
66 }
67}
68
69} // namespace
70
71int
72main()
73{
74 auto data = read_file("data/day13.txt");
75 part1(data);
76 part2(data);
77}
diff --git a/2017/src/day14.cpp b/2017/src/day14.cpp
new file mode 100644
index 0000000..d226d46
--- /dev/null
+++ b/2017/src/day14.cpp
@@ -0,0 +1,146 @@
1#include <array>
2#include <iostream>
3#include <numeric>
4#include <queue>
5#include <set>
6#include <string>
7#include <vector>
8
9using namespace std;
10
11namespace {
12
13vector<unsigned>
14gen_data(size_t len)
15{
16 vector<unsigned> data(len);
17 iota(data.begin(), data.end(), 0UL);
18 return data;
19}
20
21void
22reverse(vector<unsigned>& data, size_t start, size_t len)
23{
24 auto end = start + len;
25
26 while ( start < end ) {
27 swap(data.at(start++ % data.size()), data.at(--end % data.size()));
28 }
29}
30
31void
32hash64(vector<unsigned>& data, const vector<size_t>& lengths)
33{
34 size_t pos = 0;
35 size_t skip = 0;
36 for ( size_t i = 0; i != 64; ++i ) {
37 for ( auto length: lengths ) {
38 reverse(data, pos, length);
39 pos += length + skip;
40 ++skip;
41 }
42 }
43}
44
45vector<uint8_t>
46knothash(string line)
47{
48 line += char(17);
49 line += char(31);
50 line += char(73);
51 line += char(47);
52 line += char(23);
53
54 vector<size_t> lengths;
55 for ( const auto byte: line ) {
56 lengths.emplace_back(static_cast<unsigned char>(byte));
57 }
58
59 auto data = gen_data(256);
60 hash64(data, lengths);
61
62 vector<uint8_t> result;
63 for ( size_t i = 0; i != 256; i += 16 ) {
64 size_t value = 0;
65 for ( size_t j = 0; j != 16; ++j ) {
66 value ^= data.at(i + j);
67 }
68 result.emplace_back(value & 0xFF);
69 }
70 return result;
71}
72
73void
74part1(const string& line)
75{
76 int count = 0;
77 for ( int i = 0; i != 128; ++i ) {
78 auto result = knothash(line + "-"s + to_string(i));
79
80 for ( const auto value: result ) {
81 count += popcount(value);
82 }
83 }
84 cout << "Part1: " << count << '\n';
85}
86
87void
88part2(const string& line)
89{
90 set<tuple<size_t, size_t>> grid;
91
92 for ( size_t y = 0; y != 128; ++y ) {
93 auto result = knothash(line + "-"s + to_string(y));
94
95 for ( size_t x = 0; x != 128; ++x ) {
96 auto value = result.at(x / 8);
97 auto mask = 1u << (7 - (x % 8));
98
99 if ( (value & mask) != 0 ) {
100 grid.emplace(x, y);
101 }
102 }
103 }
104
105 int count = 0;
106
107 for ( size_t x = 0; x != 128; ++x ) {
108 for ( size_t y = 0; y != 128; ++y ) {
109 if ( !grid.contains({ x, y }) ) {
110 continue;
111 }
112
113 ++count;
114
115 queue<tuple<size_t, size_t>> queue;
116 queue.emplace(x, y);
117
118 while ( !queue.empty() ) {
119 auto pos = queue.front();
120 queue.pop();
121
122 grid.erase(pos);
123
124 static array<tuple<size_t, size_t>, 4> dirs{ make_tuple(-1, 0), make_tuple(1, 0), make_tuple(0, -1), make_tuple(0, 1) };
125
126 for ( const auto [dx, dy]: dirs ) {
127 const auto new_pos = make_tuple(dx + get<0>(pos), dy + get<1>(pos));
128 if ( grid.contains(new_pos) ) {
129 queue.emplace(new_pos);
130 }
131 }
132 }
133 }
134 }
135 cout << "Part2: " << count << '\n';
136}
137
138} // namespace
139
140int
141main()
142{
143 const string input = "ffayrhll";
144 part1(input);
145 part2(input);
146}
diff --git a/2017/src/day15.cpp b/2017/src/day15.cpp
new file mode 100644
index 0000000..270528b
--- /dev/null
+++ b/2017/src/day15.cpp
@@ -0,0 +1,73 @@
1#include <iostream>
2
3using namespace std;
4
5namespace {
6
7struct Generator {
8 Generator(unsigned long factor, unsigned long prev)
9 : factor{ factor }
10 , prev{ prev }
11 {
12 }
13
14 unsigned long next()
15 {
16 prev *= factor;
17 prev %= 2147483647;
18 return prev;
19 }
20
21 unsigned long factor;
22 unsigned long prev;
23};
24
25void
26part1(unsigned long start_a, unsigned long start_b)
27{
28 Generator GenA(16807, start_a);
29 Generator GenB(48271, start_b);
30
31 int count = 0;
32 for ( int i = 0; i != 40000000; ++i ) {
33 if ( (GenA.next() & 0xFFFF) == (GenB.next() & 0xFFFF) ) {
34 ++count;
35 }
36 }
37 cout << "Part1: " << count << '\n';
38}
39
40void
41part2(unsigned long start_a, unsigned long start_b)
42{
43 Generator GenA(16807, start_a);
44 Generator GenB(48271, start_b);
45
46 int count = 0;
47 for ( int i = 0; i != 5000000; ++i ) {
48 auto value_a = GenA.next();
49 while ( value_a % 4 != 0 ) {
50 value_a = GenA.next();
51 }
52 auto value_b = GenB.next();
53 while ( value_b % 8 != 0 ) {
54 value_b = GenB.next();
55 }
56 if ( (value_a & 0xFFFF) == (value_b & 0xFFFF) ) {
57 ++count;
58 }
59 }
60 cout << "Part2: " << count << '\n';
61}
62
63} // namespace
64
65int
66main()
67{
68 static const unsigned long start_a = 618;
69 static const unsigned long start_b = 814;
70
71 part1(start_a, start_b);
72 part2(start_a, start_b);
73}
diff --git a/2017/src/day16.cpp b/2017/src/day16.cpp
new file mode 100644
index 0000000..ea048bb
--- /dev/null
+++ b/2017/src/day16.cpp
@@ -0,0 +1,174 @@
1#include <algorithm>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <sstream>
7#include <string>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14vector<string>
15read_line(const filesystem::path& filename)
16{
17 ifstream file{ filename };
18 vector<string> result;
19
20 for ( string line; getline(file, line, ','); ) {
21 result.emplace_back(line);
22 }
23 return result;
24}
25
26vector<string>
27split(const string& line, char sep = '/')
28{
29 stringstream strm{ line };
30 vector<string> result;
31
32 for ( string line; getline(strm, line, sep); ) {
33 result.emplace_back(line);
34 }
35 return result;
36}
37
38void
39spin(string& line, size_t n)
40{
41 ranges::reverse(line);
42 reverse(line.begin(), line.begin() + static_cast<string::difference_type>(n));
43 reverse(line.begin() + static_cast<string::difference_type>(n), line.end());
44}
45
46void
47exchange(string& line, size_t a, size_t b)
48{
49 swap(line.at(a), line.at(b));
50}
51
52void
53partner(string& line, char a, char b)
54{
55 auto iter_a = ranges::find(line, a);
56 auto iter_b = ranges::find(line, b);
57 iter_swap(iter_a, iter_b);
58}
59
60void
61dance(const vector<string>& instructions, string& line)
62{
63 for ( const auto& instr: instructions ) {
64 auto values = split(instr.substr(1));
65
66 switch ( instr.at(0) ) {
67 case 's':
68 spin(line, stoul(values.at(0)));
69 break;
70 case 'x':
71 exchange(line, stoul(values.at(0)), stoul(values.at(1)));
72 break;
73 case 'p':
74 partner(line, values.at(0).at(0), values.at(1).at(0));
75 break;
76 default:
77 throw runtime_error("inknown command");
78 }
79 }
80}
81
82void
83part1(const vector<string>& instructions, string line)
84{
85 dance(instructions, line);
86 cout << "Part1: " << line << '\n';
87}
88
89#if defined(WASTE_TIME)
90void
91part2_bf(const vector<string>& instructions, string line)
92{
93 for ( long round = 0; round != 1'000'000'000; ++round ) {
94 dance(instructions, line);
95 }
96
97 cout << "Part2-BF: " << line << '\n';
98}
99#endif
100
101void
102part2(const vector<string>& instructions, string line)
103{
104 map<string, size_t> seen;
105 vector<string> history;
106
107 size_t cycle_start = 0;
108 size_t cycle_length = 0;
109
110 for ( size_t round = 0;; ++round ) {
111 if ( seen.contains(line) ) {
112 cycle_start = seen.at(line);
113 cycle_length = round - cycle_start;
114 break;
115 }
116
117 seen[line] = round;
118 history.emplace_back(line);
119
120 dance(instructions, line);
121 }
122
123 const size_t total_rounds = 1'000'000'000L;
124 const size_t remaining = (total_rounds - cycle_start) % cycle_length;
125
126 cout << "Part2: " << history.at(cycle_start + remaining) << '\n';
127}
128
129void
130part2_alt(const vector<string>& instructions, const string& line)
131{
132 auto slow = line;
133 dance(instructions, slow);
134
135 auto fast = line;
136 dance(instructions, fast);
137 dance(instructions, fast);
138
139 // find cycle
140 while ( slow != fast ) {
141 dance(instructions, slow);
142 dance(instructions, fast);
143 dance(instructions, fast);
144 }
145
146 // find cycle length
147 size_t cycle_length = 1;
148 dance(instructions, slow);
149 while ( slow != fast ) {
150 dance(instructions, slow);
151 ++cycle_length;
152 }
153
154 // process remaining rounds
155 const size_t total_rounds = 1'000'000'000L;
156 for ( auto remaining = total_rounds % cycle_length; remaining-- > 0; ) {
157 dance(instructions, slow);
158 }
159
160 cout << "Part2-Alt: " << slow << '\n';
161}
162
163} // namespace
164
165int
166main()
167{
168 auto instructions = read_line("data/day16.txt");
169 auto line = "abcdefghijklmnop"s;
170
171 part1(instructions, line);
172 part2(instructions, line);
173 part2_alt(instructions, line);
174}
diff --git a/2017/src/day17.cpp b/2017/src/day17.cpp
new file mode 100644
index 0000000..6cf498b
--- /dev/null
+++ b/2017/src/day17.cpp
@@ -0,0 +1,47 @@
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6namespace {
7
8void
9part1(size_t steps, size_t iterations)
10{
11 vector<size_t> buffer{ 0 };
12 size_t pos = 0;
13
14 for ( size_t i = 1; i <= iterations; ++i ) {
15 pos = (pos + steps) % i + 1;
16 buffer.insert(buffer.begin() + static_cast<vector<size_t>::difference_type>(pos), i);
17 }
18
19 cout << "Part1: " << buffer[(pos + 1) % buffer.size()] << '\n';
20}
21
22void
23part2(size_t steps, size_t iterations)
24{
25 size_t pos = 0;
26 size_t value = 0;
27
28 for ( size_t i = 1; i <= iterations; ++i ) {
29 pos = (pos + steps) % i;
30 if ( pos == 0 ) {
31 value = i;
32 }
33 pos = (pos + 1) % (i + 1);
34 }
35
36 cout << "Part2: " << value << '\n';
37}
38
39} // namespace
40
41int
42main()
43{
44 const auto input = 371;
45 part1(input, 2017);
46 part2(input, 50'000'000);
47}
diff --git a/2017/src/day18.cpp b/2017/src/day18.cpp
new file mode 100644
index 0000000..bfdd7e3
--- /dev/null
+++ b/2017/src/day18.cpp
@@ -0,0 +1,266 @@
1#include <charconv>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <queue>
7#include <sstream>
8#include <string>
9#include <vector>
10
11using namespace std;
12
13namespace {
14
15template<typename T>
16struct CPU {
17 [[nodiscard]]
18 T get(const string& ref)
19 {
20 T value{};
21 auto [ptr, ec] = from_chars(ref.data(), ref.data() + ref.size(), value);
22
23 if ( ec == errc() ) {
24 return value;
25 }
26
27 return memory[ref];
28 }
29
30 void set(const string& ref, T value)
31 {
32 memory[ref] = value;
33 }
34
35 void add(const string& ref, T value)
36 {
37 memory[ref] += value;
38 }
39
40 void mul(const string& ref, T value)
41 {
42 memory[ref] *= value;
43 }
44
45 void mod(const string& ref, T value)
46 {
47 memory[ref] %= value;
48 }
49
50 T execute(const vector<vector<string>>& code)
51 {
52 long played_sound{};
53
54 for ( size_t ip = 0; ip < code.size(); ++ip ) {
55 const auto& line = code.at(ip);
56 const auto& opcode = line.at(0);
57
58 if ( opcode == "snd" ) {
59 played_sound = get(line.at(1));
60 }
61 else if ( opcode == "rcv" ) {
62 auto value = get(line.at(1));
63 if ( value != 0 ) {
64 return played_sound;
65 }
66 }
67 else if ( opcode == "set" ) {
68 set(line.at(1), get(line.at(2)));
69 }
70 else if ( opcode == "add" ) {
71 add(line.at(1), get(line.at(2)));
72 }
73 else if ( opcode == "mul" ) {
74 mul(line.at(1), get(line.at(2)));
75 }
76 else if ( opcode == "mod" ) {
77 mod(line.at(1), get(line.at(2)));
78 }
79 else if ( opcode == "jgz" ) {
80 auto value = get(line.at(1));
81 if ( value > 0 ) {
82 auto offset = get(line.at(2));
83 ip += static_cast<size_t>(offset - 1);
84 }
85 }
86 else {
87 cerr << "unknown opcode: " << opcode << '\n';
88 return -1;
89 }
90 }
91 return -1;
92 }
93
94 map<string, T> memory;
95};
96
97template<typename T>
98struct CPU2 {
99 CPU2(queue<T>& in, queue<T>& out)
100 : in{ in }
101 , out{ out }
102 {
103 }
104
105 [[nodiscard]]
106 T get(const string& ref)
107 {
108 T value{};
109 auto [ptr, ec] = from_chars(ref.data(), ref.data() + ref.size(), value);
110
111 if ( ec == errc() ) {
112 return value;
113 }
114
115 return memory[ref];
116 }
117
118 void set(const string& ref, T value)
119 {
120 memory[ref] = value;
121 }
122
123 void add(const string& ref, T value)
124 {
125 memory[ref] += value;
126 }
127
128 void mul(const string& ref, T value)
129 {
130 memory[ref] *= value;
131 }
132
133 void mod(const string& ref, T value)
134 {
135 memory[ref] %= value;
136 }
137
138 bool step(const vector<vector<string>>& code)
139 {
140 if ( ip >= code.size() ) {
141 return false;
142 }
143
144 const auto& line = code.at(ip);
145 const auto& opcode = line.at(0);
146
147 if ( opcode == "snd" ) {
148 out.push(get(line.at(1)));
149 ++send_count;
150 }
151 else if ( opcode == "rcv" ) {
152 if ( in.empty() ) {
153 waiting = true;
154 return true;
155 }
156 else {
157 auto value = in.front();
158 in.pop();
159 set(line.at(1), value);
160 waiting = false;
161 }
162 }
163 else if ( opcode == "set" ) {
164 set(line.at(1), get(line.at(2)));
165 }
166 else if ( opcode == "add" ) {
167 add(line.at(1), get(line.at(2)));
168 }
169 else if ( opcode == "mul" ) {
170 mul(line.at(1), get(line.at(2)));
171 }
172 else if ( opcode == "mod" ) {
173 mod(line.at(1), get(line.at(2)));
174 }
175 else if ( opcode == "jgz" ) {
176 auto value = get(line.at(1));
177 if ( value > 0 ) {
178 auto offset = get(line.at(2));
179 ip += static_cast<size_t>(offset);
180 return true;
181 }
182 }
183 else {
184 cerr << "unknown opcode: " << opcode << '\n';
185 return false;
186 }
187
188 ++ip;
189
190 return true;
191 }
192
193 size_t ip{};
194 queue<T>& in;
195 queue<T>& out;
196 bool waiting{ false };
197 T send_count{};
198 map<string, T> memory;
199};
200
201vector<string>
202split(const string& line)
203{
204 stringstream strm{ line };
205 vector<string> data;
206
207 for ( string line; strm >> line; ) {
208 data.emplace_back(line);
209 }
210
211 return data;
212}
213
214vector<vector<string>>
215read_file(const filesystem::path& filename)
216{
217 ifstream file{ filename };
218 vector<vector<string>> data;
219
220 for ( string line; getline(file, line); ) {
221 const auto parts = split(line);
222 data.emplace_back(parts);
223 }
224
225 return data;
226}
227
228void
229part1(const vector<vector<string>>& code)
230{
231 CPU<long> cpu{};
232
233 cout << "Part1: " << cpu.execute(code) << '\n';
234}
235
236void
237part2(const vector<vector<string>>& code)
238{
239 queue<long> queue1;
240 queue<long> queue2;
241 CPU2<long> cpu1{ queue1, queue2 };
242 CPU2<long> cpu2{ queue2, queue1 };
243
244 cpu1.set("p", 0);
245 cpu2.set("p", 1);
246
247 for ( ;; ) {
248 auto cpu1_running = cpu1.step(code);
249 auto cpu2_running = cpu2.step(code);
250
251 if ( (cpu1.waiting || !cpu1_running) && (cpu2.waiting || !cpu2_running) ) {
252 break;
253 }
254 }
255 cout << "Part2: " << cpu2.send_count << '\n';
256}
257
258} // namespace
259
260int
261main()
262{
263 auto instr = read_file("data/day18.txt");
264 part1(instr);
265 part2(instr);
266}
diff --git a/2017/src/day19.cpp b/2017/src/day19.cpp
new file mode 100644
index 0000000..470bb4f
--- /dev/null
+++ b/2017/src/day19.cpp
@@ -0,0 +1,97 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <string>
6#include <tuple>
7
8using namespace std;
9
10namespace {
11
12using dir_type = tuple<size_t, size_t>;
13using pos_type = tuple<size_t, size_t>;
14using puzzle_type = map<pos_type, char>;
15
16puzzle_type
17read_file(const filesystem::path& filename)
18{
19 ifstream file{ filename };
20 puzzle_type data;
21
22 size_t row = 0;
23 for ( string line; getline(file, line); ) {
24 for ( size_t col = 0; col != line.size(); ++col ) {
25 if ( line.at(col) != ' ' ) {
26 data.emplace(pos_type{ col, row }, line.at(col));
27 }
28 }
29 ++row;
30 }
31
32 return data;
33}
34
35pos_type
36find_start(const puzzle_type& puzzle)
37{
38 for ( size_t col = 0;; ++col ) {
39 const pos_type pos{ col, 0 };
40 if ( puzzle.contains(pos) && puzzle.at(pos) == '|' ) {
41 return pos;
42 }
43 }
44}
45
46void
47solve(const puzzle_type& puzzle)
48{
49 string result;
50 size_t steps = 0;
51
52 pos_type pos = find_start(puzzle);
53 dir_type dir{ 0, 1 };
54
55 while ( puzzle.contains(pos) ) {
56 auto chr = puzzle.at(pos);
57
58 if ( chr >= 'A' && chr <= 'Z' ) {
59 result += chr;
60 }
61 else if ( chr == '+' ) {
62 auto [dx, dy] = dir;
63 auto left = dir_type{ -dy, dx };
64 auto right = dir_type{ dy, -dx };
65
66 pos_type next_left = { get<0>(pos) + get<0>(left), get<1>(pos) + get<1>(left) };
67 pos_type next_right = { get<0>(pos) + get<0>(right), get<1>(pos) + get<1>(right) };
68
69 if ( puzzle.contains(next_left) ) {
70 dir = left;
71 }
72 else if ( puzzle.contains(next_right) ) {
73 dir = right;
74 }
75 else {
76 cerr << "Error!\n";
77 return;
78 }
79 }
80
81 get<0>(pos) += get<0>(dir);
82 get<1>(pos) += get<1>(dir);
83 ++steps;
84 }
85
86 cout << "Part1: " << result << '\n';
87 cout << "Part2: " << steps << '\n';
88}
89
90} // namespace
91
92int
93main()
94{
95 auto puzzle = read_file("data/day19.txt");
96 solve(puzzle);
97}
diff --git a/2017/src/day20.cpp b/2017/src/day20.cpp
new file mode 100644
index 0000000..fd09535
--- /dev/null
+++ b/2017/src/day20.cpp
@@ -0,0 +1,162 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <string>
6#include <vector>
7
8using namespace std;
9
10namespace {
11
12using point_type = tuple<long, long, long>;
13using particle_type = tuple<point_type, point_type, point_type>;
14
15#if 0
16ostream&
17operator<<(ostream& strm, const point_type& point)
18{
19 const auto [x, y, z] = point;
20 strm << '<' << x << ',' << y << ',' << z << '>';
21 return strm;
22}
23
24ostream&
25operator<<(ostream& strm, const particle_type& particle)
26{
27 const auto [pos, velo, accel] = particle;
28 strm << "p=" << pos << ", v=" << velo << ", a=" << accel;
29 return strm;
30}
31#endif
32
33vector<long>
34split(const string& line, const string& delimiters)
35{
36 vector<long> result;
37
38 size_t start = 0;
39 size_t end = 0;
40
41 while ( (end = line.find_first_of(delimiters, start)) != string::npos ) {
42 if ( end != start ) {
43 result.emplace_back(stol(line.substr(start, end - start)));
44 }
45
46 start = end + 1;
47 }
48
49 if ( start != line.size() ) {
50 result.emplace_back(stol(line.substr(start)));
51 }
52
53 return result;
54}
55
56vector<particle_type>
57read_file(const filesystem::path& filename)
58{
59 ifstream file{ filename };
60 vector<particle_type> data;
61
62 for ( string line; getline(file, line); ) {
63 auto parts = split(line, "p=<>,va ");
64
65 point_type position{ parts.at(0), parts.at(1), parts.at(2) };
66 point_type velocity{ parts.at(3), parts.at(4), parts.at(5) };
67 point_type acceleration{ parts.at(6), parts.at(7), parts.at(8) };
68
69 data.emplace_back(position, velocity, acceleration);
70 }
71
72 return data;
73}
74
75point_type
76add(const point_type& lhs, const point_type& rhs)
77{
78 return { get<0>(lhs) + get<0>(rhs), get<1>(lhs) + get<1>(rhs), get<2>(lhs) + get<2>(rhs) };
79}
80
81void
82update(particle_type& particle)
83{
84 auto [pos, vel, acc] = particle;
85
86 vel = add(vel, acc);
87 pos = add(pos, vel);
88
89 particle = { pos, vel, acc };
90}
91
92long
93distance(const point_type& point)
94{
95 return abs(get<0>(point)) + abs(get<1>(point)) + abs(get<2>(point));
96}
97
98void
99part1(vector<particle_type> particles)
100{
101 size_t current_min_index = particles.size();
102
103 for ( int round = 0; round != 10000; ++round ) {
104 // Alle updaten
105 ranges::for_each(particles, update);
106
107 long step_min_dist = numeric_limits<long>::max();
108 size_t step_min_index = current_min_index;
109
110 // kleinste Distanz suchen
111 for ( size_t i = 0; i != particles.size(); ++i ) {
112 auto min_dist = distance(get<0>(particles.at(i)));
113
114 if ( min_dist < step_min_dist ) {
115 step_min_dist = min_dist;
116 step_min_index = i;
117 }
118 }
119
120 // Prüfen, ob stabil
121 if ( step_min_index != current_min_index ) {
122 current_min_index = step_min_index;
123 round = 0;
124 }
125 }
126
127 cout << "Part1: " << current_min_index << '\n';
128}
129
130void
131part2(vector<particle_type> particles)
132{
133 for ( int round = 0; round != 10000; ++round ) {
134 // Alle updaten
135 ranges::for_each(particles, update);
136
137 map<point_type, size_t> collision_counter;
138
139 for ( const auto& [pos, vel, accl]: particles ) {
140 collision_counter[pos]++;
141 }
142
143 for ( const auto& [pos, count]: collision_counter ) {
144 if ( count > 1 ) {
145 erase_if(particles, [&pos](const auto& particle) { return get<0>(particle) == pos; });
146 round = 0;
147 }
148 }
149 }
150
151 cout << "Part2: " << particles.size() << '\n';
152}
153
154} // namespace
155
156int
157main()
158{
159 auto data = read_file("data/day20.txt");
160 part1(data);
161 part2(data);
162}