aboutsummaryrefslogtreecommitdiff
path: root/2016
diff options
context:
space:
mode:
Diffstat (limited to '2016')
-rw-r--r--2016/src/day19.cpp45
-rw-r--r--2016/src/day20.cpp128
-rw-r--r--2016/src/day21.cpp222
-rw-r--r--2016/src/day22.cpp166
-rw-r--r--2016/src/day23.cpp287
-rw-r--r--2016/src/day24.cpp153
-rw-r--r--2016/src/day25.cpp210
7 files changed, 1211 insertions, 0 deletions
diff --git a/2016/src/day19.cpp b/2016/src/day19.cpp
new file mode 100644
index 0000000..2d7282f
--- /dev/null
+++ b/2016/src/day19.cpp
@@ -0,0 +1,45 @@
1#include <cmath>
2#include <iostream>
3
4using namespace std;
5
6namespace {
7
8template<typename T>
9T
10fn(T N)
11 requires std::is_integral_v<T>
12{
13 return T(1) << static_cast<T>(floor(log2(N)));
14}
15
16void
17part1(unsigned N)
18{
19 cout << (2 * (N - fn(N))) + 1 << '\n';
20}
21
22void
23part2(unsigned N)
24{
25 auto log_3 = [](double x) { return log(x) / log(3); };
26
27 auto threes = pow(3, floor(log_3(N - 1)));
28 if ( N <= 2 * threes ) {
29 cout << static_cast<unsigned>(N - threes);
30 }
31 else {
32 cout << static_cast<unsigned>(N - threes + N - (2 * threes));
33 }
34 cout << '\n';
35}
36
37} // namespace
38
39int
40main()
41{
42 const unsigned puzzle = 3017957;
43 part1(puzzle);
44 part2(puzzle);
45}
diff --git a/2016/src/day20.cpp b/2016/src/day20.cpp
new file mode 100644
index 0000000..49a9ec1
--- /dev/null
+++ b/2016/src/day20.cpp
@@ -0,0 +1,128 @@
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
13struct Range {
14 long long start;
15 long long end;
16};
17
18vector<Range>
19readFile(const filesystem::path& filename)
20{
21 ifstream file{ filename };
22 vector<Range> ranges;
23
24 for ( string line; getline(file, line); ) {
25 stringstream stream{ line };
26 char dash{};
27 long long start{};
28 long long end{};
29
30 stream >> start >> dash >> end;
31
32 ranges.emplace_back(start, end);
33 }
34
35 return ranges;
36}
37
38void
39sortRanges(vector<Range>& ranges)
40{
41 ranges::sort(ranges, [](const auto& lhs, const auto& rhs) {
42 if ( lhs.start != rhs.start ) {
43 return lhs.start < rhs.start;
44 }
45 return lhs.end < rhs.end;
46 });
47}
48
49void
50mergeRanges(vector<Range>& ranges)
51{
52 if ( ranges.empty() ) {
53 return;
54 }
55
56 vector<Range> mergedRanges;
57
58 auto current = ranges[0];
59 for ( size_t i = 1; i != ranges.size(); ++i ) {
60 if ( ranges[i].start <= current.end + 1 ) {
61 current.end = max(current.end, ranges[i].end);
62 }
63 else {
64 mergedRanges.emplace_back(current);
65 current = ranges[i];
66 }
67 }
68 mergedRanges.emplace_back(current);
69
70 ranges.swap(mergedRanges);
71}
72
73long long
74findLowestAllowedIP(const vector<Range>& ranges)
75{
76 if ( ranges.empty() || ranges[0].start > 0 ) {
77 return 0;
78 }
79 return ranges[0].end + 1;
80}
81
82long long
83countAllowedIPs(const vector<Range>& ranges, long long max_ip)
84{
85 long long allowed_count = 0;
86
87 for ( size_t i = 0; i < ranges.size() - 1; ++i ) {
88 allowed_count += ranges[i + 1].start - ranges[i].end - 1;
89 }
90
91 if ( !ranges.empty() && ranges.back().end < max_ip ) {
92 allowed_count += max_ip - ranges.back().end;
93 }
94
95 if ( ranges.empty() ) {
96 allowed_count = max_ip + 1;
97 }
98
99 return allowed_count;
100}
101
102void
103part1(vector<Range> ranges)
104{
105 sortRanges(ranges);
106 mergeRanges(ranges);
107
108 cout << findLowestAllowedIP(ranges) << '\n';
109}
110
111void
112part2(vector<Range> ranges, long long max_ip = 4294967295)
113{
114 sortRanges(ranges);
115 mergeRanges(ranges);
116
117 cout << countAllowedIPs(ranges, max_ip) << '\n';
118}
119
120} // namespace
121
122int
123main()
124{
125 auto ranges = readFile("data/day20.txt");
126 part1(ranges);
127 part2(ranges);
128}
diff --git a/2016/src/day21.cpp b/2016/src/day21.cpp
new file mode 100644
index 0000000..7e8fed7
--- /dev/null
+++ b/2016/src/day21.cpp
@@ -0,0 +1,222 @@
1#include <algorithm>
2#include <filesystem>
3#include <fstream>
4#include <iostream>
5#include <ranges>
6#include <sstream>
7#include <string>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14void
15swap_at_pos(string& str, size_t x, size_t y)
16{
17 if ( str.empty() ) {
18 return;
19 }
20
21 swap(str.at(x), str.at(y));
22}
23
24void
25swap_letter(string& str, char x, char y)
26{
27 if ( str.empty() ) {
28 return;
29 }
30
31 for ( auto& chr: str ) {
32 if ( chr == x ) {
33 chr = y;
34 }
35 else if ( chr == y ) {
36 chr = x;
37 }
38 }
39}
40
41void
42rotate_left(string& str, size_t n)
43{
44 if ( str.empty() ) {
45 return;
46 }
47
48 ranges::rotate(str, str.begin() + static_cast<int>(n % str.size()));
49}
50
51void
52rotate_right(string& str, size_t n)
53{
54 if ( str.empty() ) {
55 return;
56 }
57
58 rotate_left(str, str.size() - n);
59}
60
61void
62rotate(string& str, char chr)
63{
64 if ( str.empty() ) {
65 return;
66 }
67
68 const auto idx = str.find(chr);
69 if ( idx == string::npos ) {
70 return;
71 }
72
73 const auto steps = 1 + idx + (idx >= 4 ? 1 : 0);
74 rotate_right(str, steps % str.size());
75}
76
77void
78reverse(string& str, size_t x, size_t y)
79{
80 if ( str.empty() ) {
81 return;
82 }
83
84 if ( x > y ) {
85 swap(x, y);
86 }
87
88 reverse(str.begin() + static_cast<string::difference_type>(x),
89 str.begin() + static_cast<string::difference_type>(y) + 1);
90}
91
92void
93move(string& str, size_t x, size_t y)
94{
95 if ( str.empty() ) {
96 return;
97 }
98
99 const auto chr = str.at(x);
100
101 str.erase(x, 1);
102 str.insert(y, 1, chr);
103}
104
105vector<string>
106readLines(const filesystem::path& filename)
107{
108 ifstream file{ filename };
109 vector<string> lines;
110
111 for ( string line; getline(file, line); ) {
112 lines.emplace_back(line);
113 }
114
115 return lines;
116}
117
118vector<string>
119split(const string& line, char sep = ' ')
120{
121 vector<string> words;
122 stringstream input{ line };
123
124 for ( string word; getline(input, word, sep); ) {
125 words.emplace_back(word);
126 }
127
128 return words;
129}
130
131void
132part1(const vector<string>& lines, string str)
133{
134 for ( const auto& line: lines ) {
135 auto words = split(line);
136
137 if ( line.starts_with("swap position") ) {
138 swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5)));
139 }
140 else if ( line.starts_with("swap letter") ) {
141 swap_letter(str, words.at(2).at(0), words.at(5).at(0));
142 }
143 else if ( line.starts_with("rotate left") ) {
144 rotate_left(str, stoull(words.at(2)));
145 }
146 else if ( line.starts_with("rotate right") ) {
147 rotate_right(str, stoull(words.at(2)));
148 }
149 else if ( line.starts_with("rotate based") ) {
150 rotate(str, words.at(6).at(0));
151 }
152 else if ( line.starts_with("reverse") ) {
153 reverse(str, stoull(words.at(2)), stoull(words.at(4)));
154 }
155 else if ( line.starts_with("move") ) {
156 move(str, stoull(words.at(2)), stoull(words.at(5)));
157 }
158 else {
159 cerr << "unknown command: " << line << '\n';
160 return;
161 }
162 }
163 cout << str << '\n';
164}
165
166void
167part2(const vector<string>& lines, string str)
168{
169 for ( const auto& line: ranges::reverse_view(lines) ) {
170 auto words = split(line);
171
172 if ( line.starts_with("swap position") ) {
173 swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5)));
174 }
175 else if ( line.starts_with("swap letter") ) {
176 swap_letter(str, words.at(2).at(0), words.at(5).at(0));
177 }
178 else if ( line.starts_with("rotate left") ) {
179 rotate_right(str, stoull(words.at(2)));
180 }
181 else if ( line.starts_with("rotate right") ) {
182 rotate_left(str, stoull(words.at(2)));
183 }
184 else if ( line.starts_with("rotate based") ) {
185 auto chr = words.at(6).at(0);
186 for ( size_t i = 0; i != str.size(); ++i ) {
187 string tmp = str;
188 rotate_left(tmp, i);
189
190 auto idx = tmp.find(chr);
191 auto steps = (1 + idx + (idx >= 4 ? 1 : 0));
192
193 if ( ((steps - i + str.size()) % str.size()) == 0 ) {
194 str = tmp;
195 break;
196 }
197 }
198 }
199 else if ( line.starts_with("reverse") ) {
200 reverse(str, stoull(words.at(2)), stoull(words.at(4)));
201 }
202 else if ( line.starts_with("move") ) {
203 move(str, stoull(words.at(5)), stoull(words.at(2)));
204 }
205 else {
206 cerr << "unknown command: " << line << '\n';
207 return;
208 }
209 }
210 cout << str << '\n';
211}
212
213} // namespace
214
215int
216main()
217{
218 auto lines = readLines("data/day21.txt");
219
220 part1(lines, "abcdefgh");
221 part2(lines, "fbgdceah");
222}
diff --git a/2016/src/day22.cpp b/2016/src/day22.cpp
new file mode 100644
index 0000000..c4d1642
--- /dev/null
+++ b/2016/src/day22.cpp
@@ -0,0 +1,166 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <regex>
6#include <set>
7#include <string>
8#include <vector>
9
10using namespace std;
11
12namespace {
13
14struct Node {
15 int x, y;
16 int size, used, avail, percent;
17
18 [[nodiscard]]
19 tuple<int, int> pos() const
20 {
21 return { x, y };
22 }
23};
24
25vector<Node>
26readNodes(const filesystem::path& filename)
27{
28 static const regex line_regex(R"(^/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T\s+(\d+)%$)");
29
30 ifstream file{ filename };
31 vector<Node> nodes;
32
33 for ( string line; getline(file, line); ) {
34 smatch match;
35
36 if ( !regex_match(line, match, line_regex) ) {
37 continue;
38 }
39
40 Node node{
41 .x = stoi(match[1].str()), // x
42 .y = stoi(match[2].str()), // y
43 .size = stoi(match[3].str()), // size
44 .used = stoi(match[4].str()), // used
45 .avail = stoi(match[5].str()), // avail
46 .percent = stoi(match[6].str()) // percent
47 };
48
49 nodes.emplace_back(node);
50 }
51
52 return nodes;
53}
54
55void
56part1(const vector<Node>& nodes)
57{
58 long count = 0;
59
60 for ( size_t i = 0; i != nodes.size(); ++i ) {
61 if ( nodes[i].used == 0 ) {
62 continue;
63 }
64
65 for ( size_t j = 0; j != nodes.size(); ++j ) {
66 if ( i == j ) {
67 continue;
68 }
69
70 if ( nodes[i].used < nodes[j].avail ) {
71 ++count;
72 }
73 }
74 }
75
76 cout << count << '\n';
77}
78
79void
80part2(const vector<Node>& nodes)
81{
82 using pos_type = tuple<int, int>;
83
84 map<pos_type, char> grid;
85
86#ifdef PRINT
87 const auto max_y = ranges::max_element(nodes, {}, &Node::y)->y;
88#endif
89 const auto max_x = ranges::max_element(nodes, {}, &Node::x)->x;
90 const auto largest = ranges::max_element(nodes, {}, &Node::avail)->avail;
91
92 const pos_type g_pos = { max_x, 0 };
93 const pos_type s_pos = { 0, 0 };
94
95 pos_type start{};
96
97 for ( const auto& node: nodes ) {
98 auto pos = node.pos();
99 if ( pos == s_pos ) {
100 grid[pos] = 'S';
101 }
102 else if ( pos == g_pos ) {
103 grid[pos] = 'G';
104 }
105 else if ( node.used == 0 ) {
106 grid[pos] = '_';
107 start = pos;
108 }
109 else if ( node.used >= largest ) {
110 grid[pos] = '#';
111 }
112 else {
113 grid[pos] = '.';
114 }
115 }
116
117#ifdef PRINT
118 string result{};
119 for ( int pos_y = 0; pos_y <= max_y; ++pos_y ) {
120 for ( int pos_x = 0; pos_x <= max_x; ++pos_x ) {
121 result += grid[{ pos_x, pos_y }];
122 }
123 result += '\n';
124 }
125
126 cout << result << '\n';
127#endif
128
129 set<pos_type> seen;
130 queue<tuple<pos_type, int>> queue; // position, #Schritte
131
132 queue.emplace(start, 0);
133 while ( !queue.empty() ) {
134 const auto [pos, steps] = queue.front();
135 queue.pop();
136
137 if ( pos == g_pos ) {
138 cout << steps + (5 * (max_x - 1)) << '\n';
139 return;
140 }
141
142 static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
143
144 for ( const auto [dx, dy]: dirs ) {
145 const auto [x, y] = pos;
146 const pos_type new_pos{ x + dx, y + dy };
147
148 if ( !grid.contains(new_pos) || grid.at(new_pos) == '#' || seen.contains(new_pos) ) {
149 continue;
150 }
151
152 seen.insert(new_pos);
153 queue.emplace(new_pos, steps + 1);
154 }
155 }
156}
157
158} // namespace
159
160int
161main()
162{
163 auto nodes = readNodes("data/day22.txt");
164 part1(nodes);
165 part2(nodes);
166}
diff --git a/2016/src/day23.cpp b/2016/src/day23.cpp
new file mode 100644
index 0000000..81bffe4
--- /dev/null
+++ b/2016/src/day23.cpp
@@ -0,0 +1,287 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <optional>
6#include <sstream>
7#include <string>
8#include <utility>
9#include <vector>
10
11using namespace std;
12
13namespace {
14
15enum class OpCode : uint8_t {
16 CPY,
17 INC,
18 DEC,
19 JNZ,
20 TGL
21};
22
23using memory_type = map<char, int>;
24
25struct Argument {
26 explicit Argument(string value)
27 : value{ std::move(value) }
28 {
29 }
30
31 [[nodiscard]]
32 int eval(const memory_type& memory) const
33 {
34 const auto chr = value.at(0);
35
36 if ( chr >= 'a' && chr <= 'z' ) {
37 return memory.at(chr);
38 }
39 else {
40 return stoi(value);
41 }
42 }
43
44 [[nodiscard]]
45 char reg() const
46 {
47 if ( !is_reg() ) {
48 throw runtime_error("invalid register access! "s + value);
49 }
50
51 return value.at(0);
52 }
53
54 [[nodiscard]]
55 bool is_reg() const
56 {
57 const auto chr = value.at(0);
58
59 return chr >= 'a' && chr <= 'z';
60 }
61
62 string value;
63};
64
65struct Instruction {
66 Instruction(OpCode opCode, const Argument& x)
67 : opCode{ opCode }
68 , x{ x }
69 {
70 }
71
72 Instruction(OpCode opCode, const Argument& x, const Argument& y)
73 : opCode{ opCode }
74 , x{ x }
75 , y{ y }
76 {
77 }
78
79 OpCode opCode;
80 optional<Argument> x;
81 optional<Argument> y;
82};
83
84vector<string>
85split_words(const string& line, char sep = ' ')
86{
87 vector<string> words;
88 stringstream strm{ line };
89
90 for ( string word; getline(strm, word, sep); ) {
91 words.emplace_back(word);
92 }
93
94 return words;
95}
96
97vector<Instruction>
98read_file(const filesystem::path& filename)
99{
100 ifstream input{ filename };
101
102 vector<Instruction> instructions;
103
104 for ( string line; getline(input, line); ) {
105 const auto words = split_words(line);
106
107 if ( words.at(0) == "cpy" ) {
108 instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2)));
109 }
110 else if ( words.at(0) == "inc" ) {
111 instructions.emplace_back(OpCode::INC, Argument(words.at(1)));
112 }
113 else if ( words.at(0) == "dec" ) {
114 instructions.emplace_back(OpCode::DEC, Argument(words.at(1)));
115 }
116 else if ( words.at(0) == "jnz" ) {
117 instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2)));
118 }
119 else if ( words.at(0) == "tgl" ) {
120 instructions.emplace_back(OpCode::TGL, Argument(words.at(1)));
121 }
122 else {
123 cerr << "unknown opcode..." << '\n';
124 }
125 }
126
127 return instructions;
128}
129
130#define JIT
131
132void
133execute(memory_type& memory, vector<Instruction> instructions)
134{
135 for ( size_t ip = 0; ip < instructions.size(); ) {
136#if defined(JIT)
137 if ( ip + 2 < instructions.size() ) {
138 const auto& i0 = instructions[ip];
139 const auto& i1 = instructions[ip + 1];
140 const auto& i2 = instructions[ip + 2];
141
142 if ( i0.opCode == OpCode::INC &&
143 i1.opCode == OpCode::DEC &&
144 i2.opCode == OpCode::JNZ &&
145 i2.x && i2.x->value == i1.x->value &&
146 i2.y && i2.y->value == "-2" ) {
147 char X = i0.x->reg();
148 char Y = i1.x->reg();
149 memory[X] += memory[Y];
150 memory[Y] = 0;
151 ip += 3;
152 continue;
153 }
154 }
155#endif
156
157#if defined(JIT)
158 if ( ip + 5 < instructions.size() ) {
159 const auto& i0 = instructions[ip];
160 const auto& i1 = instructions[ip + 1];
161 const auto& i2 = instructions[ip + 2];
162 const auto& i3 = instructions[ip + 3];
163 const auto& i4 = instructions[ip + 4];
164 const auto& i5 = instructions[ip + 5];
165
166 if ( i0.opCode == OpCode::CPY &&
167 i1.opCode == OpCode::INC &&
168 i2.opCode == OpCode::DEC &&
169 i3.opCode == OpCode::JNZ &&
170 i4.opCode == OpCode::DEC &&
171 i5.opCode == OpCode::JNZ &&
172 i3.x && i3.y && i3.x->value == i2.x->value && i3.y->value == "-2" &&
173 i5.x && i5.y && i5.x->value == i4.x->value && i5.y->value == "-5" &&
174 i0.y->is_reg() && i1.x->is_reg() && i2.x->is_reg() && i4.x->is_reg() ) {
175 char X = i0.x->is_reg() ? i0.x->reg() : 0;
176 int valX = i0.x->is_reg() ? memory[X] : stoi(i0.x->value);
177
178 char Y = i0.y->reg();
179 char Z = i1.x->reg();
180 char W = i4.x->reg();
181
182 memory[Z] += valX * memory[W];
183 memory[Y] = 0;
184 memory[W] = 0;
185 ip += 6;
186 continue;
187 }
188 }
189#endif
190
191 const auto& instruction = instructions.at(ip);
192
193 // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n';
194
195 switch ( instruction.opCode ) {
196 using enum OpCode;
197 case CPY:
198 memory[instruction.y->reg()] = instruction.x->eval(memory);
199 ++ip;
200 break;
201 case INC:
202 memory[instruction.x->reg()]++;
203 ++ip;
204 break;
205 case DEC:
206 memory[instruction.x->reg()]--;
207 ++ip;
208 break;
209 case JNZ:
210 if ( instruction.x->eval(memory) != 0 ) {
211 ip += static_cast<size_t>(instruction.y->eval(memory));
212 }
213 else {
214 ++ip;
215 }
216 break;
217 case TGL:
218 if ( auto foo = ip + static_cast<size_t>(instruction.x->eval(memory)); foo < instructions.size() ) {
219 switch ( instructions[foo].opCode ) {
220 case CPY:
221 instructions[foo].opCode = JNZ;
222 break;
223 case INC:
224 instructions[foo].opCode = DEC;
225 break;
226 case DEC:
227 instructions[foo].opCode = INC;
228 break;
229 case JNZ:
230 instructions[foo].opCode = CPY;
231 break;
232 case TGL:
233 instructions[foo].opCode = INC;
234 break;
235 }
236 }
237
238 ++ip;
239 break;
240 }
241 }
242}
243
244void
245part1(const vector<Instruction>& instructions)
246{
247 map<char, int> memory;
248
249 memory['a'] = 7;
250 memory['b'] = 0;
251 memory['c'] = 0;
252 memory['d'] = 0;
253
254 execute(memory, instructions);
255
256 cout << "Part1: " << memory['a'] << '\n';
257}
258
259void
260part2(const vector<Instruction>& instructions)
261{
262 map<char, int> memory;
263
264 memory['a'] = 12;
265 memory['b'] = 0;
266 memory['c'] = 0;
267 memory['d'] = 0;
268
269 execute(memory, instructions);
270
271 cout << "Part2: " << memory['a'] << '\n';
272}
273
274} // namespace
275
276int
277main()
278{
279 const auto instructions = read_file("data/day23.txt");
280 try {
281 part1(instructions);
282 part2(instructions);
283 }
284 catch ( exception& e ) {
285 cerr << e.what() << '\n';
286 }
287}
diff --git a/2016/src/day24.cpp b/2016/src/day24.cpp
new file mode 100644
index 0000000..936f216
--- /dev/null
+++ b/2016/src/day24.cpp
@@ -0,0 +1,153 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <queue>
6#include <set>
7#include <string>
8
9using namespace std;
10
11namespace {
12
13using pos_type = tuple<size_t, size_t>;
14using grid_type = map<pos_type, char>;
15using points_type = map<char, pos_type>;
16using dists_type = map<tuple<char, char>, size_t>;
17
18tuple<grid_type, points_type>
19read_file(const filesystem::path& filename)
20{
21 ifstream file{ filename };
22
23 grid_type grid;
24 points_type points;
25
26 size_t row = 0;
27 for ( string line; getline(file, line); ) {
28 for ( size_t col = 0; col != line.size(); ++col ) {
29 auto chr = line[col];
30 pos_type pos{ col, row };
31
32 grid[pos] = chr;
33
34 if ( isdigit(chr) != 0 ) {
35 points[chr] = pos;
36 }
37 }
38
39 ++row;
40 }
41 return { grid, points };
42}
43
44size_t
45bfs(const grid_type& grid, const pos_type src, const pos_type dest)
46{
47 set<pos_type> seen;
48 queue<tuple<pos_type, size_t>> queue;
49
50 queue.emplace(src, 0);
51 seen.insert(src);
52
53 while ( !queue.empty() ) {
54 auto [pos, steps] = queue.front();
55 queue.pop();
56
57 if ( pos == dest ) {
58 return steps;
59 }
60
61 static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
62 const auto [x, y] = pos;
63
64 for ( const auto [dx, dy]: dirs ) {
65 const pos_type new_pos{ x + dx, y + dy };
66
67 if ( grid.at(new_pos) == '#' || seen.contains(new_pos) ) {
68 continue;
69 }
70
71 seen.insert(new_pos);
72 queue.emplace(new_pos, steps + 1);
73 }
74 }
75
76 return 0;
77}
78
79dists_type
80build_dists(const grid_type& grid, const points_type& points)
81{
82 dists_type dists;
83
84 for ( auto src = points.begin(); src != points.end(); ++src ) {
85 for ( auto dest = next(src); dest != points.end(); ++dest ) {
86 const auto dist = bfs(grid, src->second, dest->second);
87
88 dists[{ src->first, dest->first }] = dist;
89 dists[{ dest->first, src->first }] = dist;
90 }
91 }
92
93 return dists;
94}
95
96size_t
97shortest_route(const dists_type& dists,
98 const points_type& points,
99 bool return_to_start)
100{
101 vector<char> others;
102 for ( const auto& [id, _]: points ) {
103 if ( id != '0' ) {
104 others.push_back(id);
105 }
106 }
107
108 size_t best = numeric_limits<size_t>::max();
109
110 do {
111 size_t dist = 0;
112 char current = '0';
113
114 for ( char next: others ) {
115 dist += dists.at({ current, next });
116 current = next;
117 }
118
119 if ( return_to_start ) {
120 dist += dists.at({ current, '0' });
121 }
122
123 best = min(best, dist);
124 } while ( next_permutation(others.begin(), others.end()) );
125
126 return best;
127}
128
129void
130part1(const grid_type& grid, const points_type& points)
131{
132 auto dists = build_dists(grid, points);
133 auto route = shortest_route(dists, points, false);
134 cout << "Part1: " << route << '\n';
135}
136
137void
138part2(const grid_type& grid, const points_type& points)
139{
140 auto dists = build_dists(grid, points);
141 auto route = shortest_route(dists, points, true);
142 cout << "Part2: " << route << '\n';
143}
144
145} // namespace
146
147int
148main()
149{
150 auto [grid, points] = read_file("data/day24.txt");
151 part1(grid, points);
152 part2(grid, points);
153}
diff --git a/2016/src/day25.cpp b/2016/src/day25.cpp
new file mode 100644
index 0000000..ba3ad04
--- /dev/null
+++ b/2016/src/day25.cpp
@@ -0,0 +1,210 @@
1#include <filesystem>
2#include <fstream>
3#include <iostream>
4#include <map>
5#include <optional>
6#include <sstream>
7#include <string>
8#include <utility>
9#include <vector>
10
11using namespace std;
12
13namespace {
14
15enum class OpCode : uint8_t {
16 CPY,
17 INC,
18 DEC,
19 JNZ,
20 OUT,
21};
22
23using memory_type = map<char, int>;
24
25struct Argument {
26 explicit Argument(string value)
27 : value{ std::move(value) }
28 {
29 }
30
31 [[nodiscard]]
32 int eval(const memory_type& memory) const
33 {
34 const auto chr = value.at(0);
35
36 if ( chr >= 'a' && chr <= 'z' ) {
37 return memory.at(chr);
38 }
39 else {
40 return stoi(value);
41 }
42 }
43
44 [[nodiscard]]
45 char reg() const
46 {
47 if ( !is_reg() ) {
48 throw runtime_error("invalid register access! "s + value);
49 }
50
51 return value.at(0);
52 }
53
54 [[nodiscard]]
55 bool is_reg() const
56 {
57 const auto chr = value.at(0);
58
59 return chr >= 'a' && chr <= 'z';
60 }
61
62 string value;
63};
64
65struct Instruction {
66 Instruction(OpCode opCode, const Argument& x)
67 : opCode{ opCode }
68 , x{ x }
69 {
70 }
71
72 Instruction(OpCode opCode, const Argument& x, const Argument& y)
73 : opCode{ opCode }
74 , x{ x }
75 , y{ y }
76 {
77 }
78
79 OpCode opCode;
80 optional<Argument> x;
81 optional<Argument> y;
82};
83
84vector<string>
85split_words(const string& line, char sep = ' ')
86{
87 vector<string> words;
88 stringstream strm{ line };
89
90 for ( string word; getline(strm, word, sep); ) {
91 words.emplace_back(word);
92 }
93
94 return words;
95}
96
97vector<Instruction>
98read_file(const filesystem::path& filename)
99{
100 ifstream input{ filename };
101
102 vector<Instruction> instructions;
103
104 for ( string line; getline(input, line); ) {
105 const auto words = split_words(line);
106
107 if ( words.at(0) == "cpy" ) {
108 instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2)));
109 }
110 else if ( words.at(0) == "inc" ) {
111 instructions.emplace_back(OpCode::INC, Argument(words.at(1)));
112 }
113 else if ( words.at(0) == "dec" ) {
114 instructions.emplace_back(OpCode::DEC, Argument(words.at(1)));
115 }
116 else if ( words.at(0) == "jnz" ) {
117 instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2)));
118 }
119 else if ( words.at(0) == "out" ) {
120 instructions.emplace_back(OpCode::OUT, Argument(words.at(1)));
121 }
122 else {
123 cerr << "unknown opcode..." << '\n';
124 }
125 }
126
127 return instructions;
128}
129
130#define JIT
131
132string
133execute(memory_type& memory, vector<Instruction> instructions)
134{
135 string result;
136
137 for ( size_t ip = 0; ip < instructions.size(); ) {
138 const auto& instruction = instructions.at(ip);
139
140 // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n';
141
142 switch ( instruction.opCode ) {
143 using enum OpCode;
144 case CPY:
145 memory[instruction.y->reg()] = instruction.x->eval(memory);
146 ++ip;
147 break;
148 case INC:
149 memory[instruction.x->reg()]++;
150 ++ip;
151 break;
152 case DEC:
153 memory[instruction.x->reg()]--;
154 ++ip;
155 break;
156 case JNZ:
157 if ( instruction.x->eval(memory) != 0 ) {
158 ip += static_cast<size_t>(instruction.y->eval(memory));
159 }
160 else {
161 ++ip;
162 }
163 break;
164 case OUT:
165 result += to_string(instruction.x->eval(memory));
166 if ( result.size() >= 20 ) {
167 ip = instructions.size();
168 }
169 else {
170 ++ip;
171 }
172 }
173 }
174
175 return result;
176}
177
178void
179part1(const vector<Instruction>& instructions)
180{
181 for ( int seed = 0;; ++seed ) {
182 map<char, int> memory;
183
184 memory['a'] = seed;
185 memory['b'] = 0;
186 memory['c'] = 0;
187 memory['d'] = 0;
188
189 auto result = execute(memory, instructions);
190
191 if ( result == "01010101010101010101" ) {
192 cout << "Part1: " << seed << '\n';
193 return;
194 }
195 }
196}
197
198} // namespace
199
200int
201main()
202{
203 const auto instructions = read_file("data/day25.txt");
204 try {
205 part1(instructions);
206 }
207 catch ( exception& e ) {
208 cerr << e.what() << '\n';
209 }
210}