From 756f22d58bb198b8f34589c112e1003614ccdcd6 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Sun, 2 Nov 2025 21:41:58 +0100 Subject: aoc 2017, days 1-20 --- 2017/src/day01.cpp | 44 ++++++++- 2017/src/day02.cpp | 71 ++++++++++++++ 2017/src/day03.cpp | 94 +++++++++++++++++++ 2017/src/day04.cpp | 78 ++++++++++++++++ 2017/src/day05.cpp | 57 ++++++++++++ 2017/src/day06.cpp | 82 +++++++++++++++++ 2017/src/day07.cpp | 145 +++++++++++++++++++++++++++++ 2017/src/day08.cpp | 118 ++++++++++++++++++++++++ 2017/src/day09.cpp | 75 +++++++++++++++ 2017/src/day10.cpp | 124 +++++++++++++++++++++++++ 2017/src/day11.cpp | 104 +++++++++++++++++++++ 2017/src/day12.cpp | 115 +++++++++++++++++++++++ 2017/src/day13.cpp | 77 ++++++++++++++++ 2017/src/day14.cpp | 146 +++++++++++++++++++++++++++++ 2017/src/day15.cpp | 73 +++++++++++++++ 2017/src/day16.cpp | 174 +++++++++++++++++++++++++++++++++++ 2017/src/day17.cpp | 47 ++++++++++ 2017/src/day18.cpp | 266 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2017/src/day19.cpp | 97 +++++++++++++++++++ 2017/src/day20.cpp | 162 ++++++++++++++++++++++++++++++++ 20 files changed, 2148 insertions(+), 1 deletion(-) create mode 100644 2017/src/day02.cpp create mode 100644 2017/src/day03.cpp create mode 100644 2017/src/day04.cpp create mode 100644 2017/src/day05.cpp create mode 100644 2017/src/day06.cpp create mode 100644 2017/src/day07.cpp create mode 100644 2017/src/day08.cpp create mode 100644 2017/src/day09.cpp create mode 100644 2017/src/day10.cpp create mode 100644 2017/src/day11.cpp create mode 100644 2017/src/day12.cpp create mode 100644 2017/src/day13.cpp create mode 100644 2017/src/day14.cpp create mode 100644 2017/src/day15.cpp create mode 100644 2017/src/day16.cpp create mode 100644 2017/src/day17.cpp create mode 100644 2017/src/day18.cpp create mode 100644 2017/src/day19.cpp create mode 100644 2017/src/day20.cpp (limited to '2017') 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 @@ +#include +#include #include +#include using namespace std; +namespace { + +string +read_line(const filesystem::path& filename) +{ + ifstream file{ filename }; + string line; + getline(file, line); + return line; +} + +long +calculate(string_view captcha, size_t offset) +{ + long sum = 0; + for ( size_t i = 0; i != captcha.size(); ++i ) { + if ( captcha[i] == captcha[(i + offset) % captcha.size()] ) { + sum += captcha[i] - '0'; + } + } + return sum; +} + +void +part1(string_view captcha) +{ + cout << "Part1: " << calculate(captcha, 1) << '\n'; +} + +void +part2(string_view captcha) +{ + cout << "Part2: " << calculate(captcha, captcha.size() / 2) << '\n'; +} + +} // namespace + int main() { - cout << "Hallo Welt" << '\n'; + auto captcha = read_line("data/day01.txt"); + part1(captcha); + part2(captcha); } 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 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector> +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector> grid; + + for ( string line; getline(file, line); ) { + stringstream strm{ line }; + + vector row; + + for ( int value{}; strm >> value; ) { + row.emplace_back(value); + } + + grid.emplace_back(row); + } + + return grid; +} + +void +part1(const vector>& grid) +{ + int checksum = 0; + for ( const auto& row: grid ) { + auto [min, max] = ranges::minmax_element(row); + checksum += *max - *min; + } + cout << "Part1: " << checksum << '\n'; +} + +void +part2(const vector>& grid) +{ + int checksum = 0; + for ( auto row: grid ) { + ranges::sort(row, ranges::greater()); + + for ( auto it = row.begin(); it != row.end(); ++it ) { + for ( auto it2 = next(it); it2 != row.end(); ++it2 ) { + if ( *it % *it2 == 0 ) { + checksum += *it / *it2; + } + } + } + } + cout << "Part2: " << checksum << '\n'; +} + +} // namespace + +int +main() +{ + auto grid = read_file("data/day02.txt"); + part1(grid); + part2(grid); +} 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 @@ +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +void +part1(int value) +{ + auto ring = static_cast(ceil((sqrt(value) - 1) / 2)); + auto side_len = (2 * ring) + 1; + auto max_value = side_len * side_len; + + array centers = { + max_value - ring - (2 * ring * 0), + max_value - ring - (2 * ring * 1), + max_value - ring - (2 * ring * 2), + max_value - ring - (2 * ring * 3) + }; + + auto* itr = ranges::min_element(centers, {}, [value](int rhs) { return abs(value - rhs); }); + + auto dist_to_center = abs(value - *itr); + + cout << "Part1: " << ring + dist_to_center << '\n'; +} + +void +part2(int value) +{ + static const array, 4> dirs{ + make_tuple(1, 0), // right + make_tuple(0, -1), // up + make_tuple(-1, 0), // left + make_tuple(0, 1), // down + }; + + static const array offsets = { -1, 0, 1 }; + + map, int> grid; // (x,y) => value + + int x = 0; + int y = 0; + int steps = 1; + + grid[{ x, y }] = 1; + + while ( true ) { + for ( const auto [dx, dy]: dirs ) { + for ( int _ = 0; _ != steps; ++_ ) { + x += dx; + y += dy; + + int sum = 0; + for ( const auto off_x: offsets ) { + for ( const auto off_y: offsets ) { + if ( off_x == 0 && off_y == 0 ) { + continue; + } + + const auto pos = make_tuple(x + off_x, y + off_y); + if ( grid.contains(pos) ) { + sum += grid.at(pos); + } + } + } + + if ( sum > value ) { + cout << "Part2: " << sum << '\n'; + return; + } + + grid[{ x, y }] = sum; + } + if ( dx == 0 ) { + ++steps; + } + } + } +} + +} // namespace + +int +main() +{ + static const auto puzzle = 265149; + part1(puzzle); + part2(puzzle); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_lines(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( string line; getline(file, line); ) { + lines.emplace_back(line); + } + + return lines; +} + +vector +split(const string& line) +{ + stringstream strm{ line }; + vector words; + + for ( string word; strm >> word; ) { + words.emplace_back(word); + } + + return words; +} + +void +part1(const vector& lines) +{ + auto num = ranges::count_if(lines, [](const string& line) { + auto words = split(line); + set set{ words.begin(), words.end() }; + + return set.size() == words.size(); + }); + + cout << "Part1: " << num << '\n'; +} + +void +part2(const vector& lines) +{ + auto num = ranges::count_if(lines, [](const string& line) { + auto words = split(line); + set set; + + for ( auto word: words ) { + ranges::sort(word); + set.insert(word); + } + + return set.size() == words.size(); + }); + + cout << "Part2: " << num << '\n'; +} + +} // namespace + +int +main() +{ + auto lines = read_lines("data/day04.txt"); + part1(lines); + part2(lines); +} 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 @@ +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_lines(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( int value{}; file >> value; ) { + lines.emplace_back(value); + } + + return lines; +} + +void +part1(vector values) +{ + int steps = 0; + for ( size_t ip = 0; ip < values.size(); ) { + auto offset = values[ip]++; + ip += static_cast(offset); + ++steps; + } + + cout << "Part1: " << steps << '\n'; +} + +void +part2(vector values) +{ + int steps = 0; + for ( size_t ip = 0; ip < values.size(); ) { + auto offset = values[ip]; + values[ip] += (offset >= 3) ? -1 : 1; + ip += static_cast(offset); + ++steps; + } + + cout << "Part2: " << steps << '\n'; +} + +} // namespace + +int +main() +{ + auto values = read_lines("data/day05.txt"); + part1(values); + part2(values); +} 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 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_lines(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector lines; + + for ( int value{}; file >> value; ) { + lines.emplace_back(value); + } + + return lines; +} + +void +distribute(vector& values) +{ + auto iter = ranges::max_element(values); + auto max_value = *iter; + + *iter = 0; + + while ( max_value-- > 0 ) { + ++iter; + if ( iter == values.end() ) { + iter = values.begin(); + } + *iter += 1; + } +} + +void +part1(vector values) +{ + set> seen; + for ( int step = 0;; ++step ) { + if ( seen.contains(values) ) { + cout << "Part1: " << step << '\n'; + return; + } + + seen.insert(values); + + distribute(values); + } +} + +void +part2(vector values) +{ + map, int> seen; + for ( int step = 0;; ++step ) { + if ( seen.contains(values) ) { + cout << "Part2: " << step - seen.at(values) << '\n'; + return; + } + + seen.emplace(values, step); + + distribute(values); + } +} + +} // namespace + +int +main() +{ + auto values = read_lines("data/day06.txt"); + part1(values); + part2(values); +} 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 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +struct Node { + int weight; + optional parent; + vector children; +}; + +vector +split(const string& line, const string& delimiters) +{ + vector result; + + size_t start = 0; + size_t end = 0; + + while ( (end = line.find_first_of(delimiters, start)) != string::npos ) { + if ( end != start ) { + result.emplace_back(line.substr(start, end - start)); + } + + start = end + 1; + } + + if ( start != line.size() ) { + result.emplace_back(line.substr(start)); + } + + return result; +} + +map +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + + map data; // name -> (weight, parent) + + for ( string line; getline(file, line); ) { + const auto parts = split(line, " ()->,"); + const auto& parent = parts.at(0); + + data[parent].weight = stoi(parts.at(1)); + + for ( size_t idx = 2; idx != parts.size(); ++idx ) { + const auto& child = parts.at(idx); + data[child].parent = parent; + data[parent].children.emplace_back(child); + } + } + + return data; +} + +string +root_node(const map& data) +{ + for ( const auto& [name, node]: data ) { + if ( !node.parent ) { + return name; + } + } + throw runtime_error("no root found"); +} + +void +part1(const map& data) +{ + cout << "Part1: " << root_node(data) << '\n'; +} + +int +calculate_weight(const map& data, const string& name) // NOLINT +{ + const auto& node = data.at(name); + + if ( node.children.empty() ) { + return node.weight; + } + + int total_weight = node.weight; + + map child_weights; + for ( const auto& child: node.children ) { + auto child_weight = calculate_weight(data, child); + child_weights.emplace(child, child_weight); + total_weight += child_weight; + } + + map> grouped; + for ( const auto& [child, weight]: child_weights ) { + grouped[weight].emplace_back(child); + } + + if ( grouped.size() != 1 ) { + int wrong_weight{}; + int correct_weight{}; + string wrong_name; + + for ( const auto& [weight, names]: grouped ) { + if ( names.size() == 1 ) { + wrong_weight = weight; + wrong_name = names.front(); + } + else { + correct_weight = weight; + } + } + + const auto& wrong_node = data.at(wrong_name); + auto diff = wrong_weight - correct_weight; + + cout << "Part2: " << wrong_node.weight - diff << '\n'; + + exit(0); + } + + return total_weight; +} + +void +part2(const map& data) +{ + auto node = root_node(data); + calculate_weight(data, node); +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day07.txt"); + part1(data); + part2(data); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +split(const string& line, char sep = ' ') +{ + stringstream strm{ line }; + vector parts; + + for ( string part; getline(strm, part, sep); ) { + parts.emplace_back(part); + } + + return parts; +} + +vector> +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector> data; + + for ( string line; getline(file, line); ) { + auto parts = split(line); + data.emplace_back(parts); + } + + return data; +} + +void +compute(const vector>& data, map& memory, int& max_value) +{ + auto match = [](int lhs, string_view rel, int rhs) { + if ( rel == "==" ) { + return lhs == rhs; + } + else if ( rel == "!=" ) { + return lhs != rhs; + } + else if ( rel == "<" ) { + return lhs < rhs; + } + else if ( rel == "<=" ) { + return lhs <= rhs; + } + else if ( rel == ">" ) { + return lhs > rhs; + } + else if ( rel == ">=" ) { + return lhs >= rhs; + } + + throw runtime_error("unknown relation operator: "s + string(rel)); + }; + + auto execute = [&](const string& reg, string_view opcode, int value) { + if ( opcode == "inc" ) { + memory[reg] += value; + } + else if ( opcode == "dec" ) { + memory[reg] -= value; + } + else { + throw runtime_error("unknown opcode: "s + string(opcode)); + } + }; + + for ( const auto& instr: data ) { + const auto& reg = instr.at(0); + const auto& opcode = instr.at(1); + const auto value = stoi(instr.at(2)); + const auto lhs = memory[instr.at(4)]; + const auto& rel = instr.at(5); + const auto rhs = stoi(instr.at(6)); + + if ( match(lhs, rel, rhs) ) { + execute(reg, opcode, value); + max_value = max(max_value, memory[reg]); + } + } +} + +void +solve(const vector>& data) +{ + map memory; + auto max_value = numeric_limits::min(); + + compute(data, memory, max_value); + + auto itr = ranges::max_element(memory, [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; }); + cout << "Part1: " << itr->second << '\n'; + cout << "Part2: " << max_value << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day08.txt"); + try { + solve(data); + } + catch ( exception& e ) { + cerr << "Fehler: " << e.what() << '\n'; + } +} 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 @@ +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +string +remove_garbage(string_view line, int& removed) +{ + string result; + + removed = 0; + for ( size_t pos = 0; pos < line.size(); ) { + if ( line.at(pos) == '<' ) { + ++pos; + while ( pos < line.size() && line.at(pos) != '>' ) { + if ( line.at(pos) == '!' ) { + pos += 2; + } + else { + ++pos; + ++removed; + } + } + ++pos; + } + else { + result += line.at(pos); + ++pos; + } + } + + return result; +} + +string +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + return { istreambuf_iterator{ file }, {} }; +} + +void +solve(string_view data) +{ + int score = 0; + int depth = 0; + int removed = 0; + + for ( const auto chr: remove_garbage(data, removed) ) { + if ( chr == '{' ) { + ++depth; + } + else if ( chr == '}' ) { + score += depth; + --depth; + } + } + + cout << "Part1: " << score << '\n'; + cout << "Part2: " << removed << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day09.txt"); + solve(data); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +string +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + string line; + getline(file, line); + return line; +} + +vector +split(const string& line) +{ + stringstream strm{ line }; + vector data; + + for ( string word; getline(strm, word, ','); ) { + data.emplace_back(stoul(word)); + } + + return data; +} + +vector +gen_data(size_t len) +{ + vector data(len); + iota(data.begin(), data.end(), 0UL); + return data; +} + +void +reverse(vector& data, size_t start, size_t len) +{ + auto end = start + len; + + while ( start < end ) { + swap(data.at(start++ % data.size()), data.at(--end % data.size())); + } +} + +void +hash(vector& data, const vector& lengths) +{ + size_t pos = 0; + for ( size_t skip = 0; skip != lengths.size(); ++skip ) { + reverse(data, pos, lengths.at(skip)); + pos += lengths.at(skip) + skip; + } +} + +void +part1(size_t len, const string& line) +{ + auto data = gen_data(len); + auto lengths = split(line); + + hash(data, lengths); + + cout << "Part1: " << data.at(0) * data.at(1) << '\n'; +} + +void +hash64(vector& data, const vector& lengths) +{ + size_t pos = 0; + size_t skip = 0; + for ( size_t i = 0; i != 64; ++i ) { + for ( auto length: lengths ) { + reverse(data, pos, length); + pos += length + skip; + ++skip; + } + } +} + +void +part2(string line) +{ + line += char(17); + line += char(31); + line += char(73); + line += char(47); + line += char(23); + + vector lengths; + for ( const auto byte: line ) { + lengths.emplace_back(static_cast(byte)); + } + + auto data = gen_data(256); + hash64(data, lengths); + + cout << "Part2: "; + for ( size_t i = 0; i != 256; i += 16 ) { + size_t value = 0; + for ( size_t j = 0; j != 16; ++j ) { + value ^= data.at(i + j); + } + cout << setw(2) << setfill('0') << hex << (value & 0xFF); + } + cout << '\n'; +} + +} // namespace + +int +main() +{ + auto line = read_file("data/day10.txt"); + part1(256, line); + part2(line); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include + +// see: https://www.redblobgames.com/grids/hexagons/ + +using namespace std; + +namespace { + +string +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + string line; + getline(file, line); + return line; +} + +vector +split(const string& line) +{ + stringstream strm{ line }; + vector data; + + for ( string word; getline(strm, word, ','); ) { + data.emplace_back(word); + } + + return data; +} + +void +part1(const vector& steps) +{ + // string => (q, s, r) + map> dirs{ + { "n", { 0, 1, -1 } }, + { "nw", { -1, 1, 0 } }, + { "sw", { -1, 0, 1 } }, + { "s", { 0, -1, 1 } }, + { "se", { 1, -1, 0 } }, + { "ne", { 1, 0, -1 } } + }; + + tuple current = { 0, 0, 0 }; + for ( const auto& step: steps ) { + const auto [dq, ds, dr] = dirs.at(step); + + get<0>(current) += dq; + get<1>(current) += ds; + get<2>(current) += dr; + } + + auto dist = (abs(get<0>(current)) + abs(get<1>(current)) + abs(get<2>(current))) / 2; + + cout << "Part1: " << dist << '\n'; +} + +void +part2(const vector& steps) +{ + // string => (q, s, r) + map> dirs{ + { "n", { 0, 1, -1 } }, + { "nw", { -1, 1, 0 } }, + { "sw", { -1, 0, 1 } }, + { "s", { 0, -1, 1 } }, + { "se", { 1, -1, 0 } }, + { "ne", { 1, 0, -1 } } + }; + + int max_dist = 0; + + tuple current = { 0, 0, 0 }; + for ( const auto& step: steps ) { + const auto [dq, ds, dr] = dirs.at(step); + + get<0>(current) += dq; + get<1>(current) += ds; + get<2>(current) += dr; + + auto dist = (abs(get<0>(current)) + abs(get<1>(current)) + abs(get<2>(current))) / 2; + + max_dist = max(max_dist, dist); + } + + cout << "Part2: " << max_dist << '\n'; +} + +} // namespace + +int +main() +{ + auto line = read_file("data/day11.txt"); + auto steps = split(line); + part1(steps); + part2(steps); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +using graph_type = map>; + +vector +split_to_int(const string& line, const string& delimiters) +{ + vector result; + + size_t start = 0; + size_t end = 0; + + while ( (end = line.find_first_of(delimiters, start)) != string::npos ) { + if ( end != start ) { + result.emplace_back(stoi(line.substr(start, end - start))); + } + + start = end + 1; + } + + if ( start != line.size() ) { + result.emplace_back(stoi(line.substr(start))); + } + + return result; +} + +graph_type +read_lines(const filesystem::path& filename) +{ + ifstream file{ filename }; + graph_type result; + + for ( string line; getline(file, line); ) { + auto parts = split_to_int(line, "<-> ,"); + + for ( size_t i = 1; i < parts.size(); ++i ) { + result[parts[0]].insert(parts[i]); + result[parts[i]].insert(parts[0]); + } + } + + return result; +} + +void +bfs_mark(const graph_type& graph, int start, set& seen) +{ + queue queue; + + queue.emplace(start); + seen.emplace(start); + + while ( !queue.empty() ) { + int prg = queue.front(); + queue.pop(); + + for ( auto link: graph.at(prg) ) { + if ( !seen.contains(link) ) { + queue.emplace(link); + seen.emplace(link); + } + } + } +} + +void +part1(const graph_type& graph) +{ + set seen; + + bfs_mark(graph, 0, seen); + + cout << "Part1: " << seen.size() << '\n'; +} + +void +part2(const graph_type& graph) +{ + set seen; + + int count = 0; + + for ( const auto& [i, _]: graph ) { + if ( seen.contains(i) ) { + continue; + } + + ++count; + + bfs_mark(graph, i, seen); + } + cout << "Part2: " << count << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_lines("data/day12.txt"); + part1(data); + part2(data); +} 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 @@ +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector> +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + unsigned long depth = 0; + unsigned long range = 0; + char colon = 0; + + vector> data; + + while ( file >> depth >> colon >> range ) { + data.emplace_back(depth, range); + } + + return data; +} + +template +T +get_pos(T depth, T range, T time) +{ + const auto period = 2 * (range - 1); + const auto remainder = (depth + time) % period; + return remainder < range ? remainder : period - remainder; +} + +void +part1(const vector>& data) +{ + unsigned long sum = 0; + for ( const auto [depth, range]: data ) { + if ( get_pos(depth, range, 0UL) == 0 ) { + sum += depth * range; + } + } + cout << "Part1: " << sum << '\n'; +} + +void +part2(const vector>& data) +{ + for ( unsigned long delay = 0;; ++delay ) { + bool pass = true; + + for ( const auto [depth, range]: data ) { + if ( get_pos(depth, range, delay) == 0 ) { + pass = false; + break; + } + } + + if ( pass ) { + cout << "Part2: " << delay << '\n'; + return; + } + } +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day13.txt"); + part1(data); + part2(data); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +gen_data(size_t len) +{ + vector data(len); + iota(data.begin(), data.end(), 0UL); + return data; +} + +void +reverse(vector& data, size_t start, size_t len) +{ + auto end = start + len; + + while ( start < end ) { + swap(data.at(start++ % data.size()), data.at(--end % data.size())); + } +} + +void +hash64(vector& data, const vector& lengths) +{ + size_t pos = 0; + size_t skip = 0; + for ( size_t i = 0; i != 64; ++i ) { + for ( auto length: lengths ) { + reverse(data, pos, length); + pos += length + skip; + ++skip; + } + } +} + +vector +knothash(string line) +{ + line += char(17); + line += char(31); + line += char(73); + line += char(47); + line += char(23); + + vector lengths; + for ( const auto byte: line ) { + lengths.emplace_back(static_cast(byte)); + } + + auto data = gen_data(256); + hash64(data, lengths); + + vector result; + for ( size_t i = 0; i != 256; i += 16 ) { + size_t value = 0; + for ( size_t j = 0; j != 16; ++j ) { + value ^= data.at(i + j); + } + result.emplace_back(value & 0xFF); + } + return result; +} + +void +part1(const string& line) +{ + int count = 0; + for ( int i = 0; i != 128; ++i ) { + auto result = knothash(line + "-"s + to_string(i)); + + for ( const auto value: result ) { + count += popcount(value); + } + } + cout << "Part1: " << count << '\n'; +} + +void +part2(const string& line) +{ + set> grid; + + for ( size_t y = 0; y != 128; ++y ) { + auto result = knothash(line + "-"s + to_string(y)); + + for ( size_t x = 0; x != 128; ++x ) { + auto value = result.at(x / 8); + auto mask = 1u << (7 - (x % 8)); + + if ( (value & mask) != 0 ) { + grid.emplace(x, y); + } + } + } + + int count = 0; + + for ( size_t x = 0; x != 128; ++x ) { + for ( size_t y = 0; y != 128; ++y ) { + if ( !grid.contains({ x, y }) ) { + continue; + } + + ++count; + + queue> queue; + queue.emplace(x, y); + + while ( !queue.empty() ) { + auto pos = queue.front(); + queue.pop(); + + grid.erase(pos); + + static array, 4> dirs{ make_tuple(-1, 0), make_tuple(1, 0), make_tuple(0, -1), make_tuple(0, 1) }; + + for ( const auto [dx, dy]: dirs ) { + const auto new_pos = make_tuple(dx + get<0>(pos), dy + get<1>(pos)); + if ( grid.contains(new_pos) ) { + queue.emplace(new_pos); + } + } + } + } + } + cout << "Part2: " << count << '\n'; +} + +} // namespace + +int +main() +{ + const string input = "ffayrhll"; + part1(input); + part2(input); +} 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 @@ +#include + +using namespace std; + +namespace { + +struct Generator { + Generator(unsigned long factor, unsigned long prev) + : factor{ factor } + , prev{ prev } + { + } + + unsigned long next() + { + prev *= factor; + prev %= 2147483647; + return prev; + } + + unsigned long factor; + unsigned long prev; +}; + +void +part1(unsigned long start_a, unsigned long start_b) +{ + Generator GenA(16807, start_a); + Generator GenB(48271, start_b); + + int count = 0; + for ( int i = 0; i != 40000000; ++i ) { + if ( (GenA.next() & 0xFFFF) == (GenB.next() & 0xFFFF) ) { + ++count; + } + } + cout << "Part1: " << count << '\n'; +} + +void +part2(unsigned long start_a, unsigned long start_b) +{ + Generator GenA(16807, start_a); + Generator GenB(48271, start_b); + + int count = 0; + for ( int i = 0; i != 5000000; ++i ) { + auto value_a = GenA.next(); + while ( value_a % 4 != 0 ) { + value_a = GenA.next(); + } + auto value_b = GenB.next(); + while ( value_b % 8 != 0 ) { + value_b = GenB.next(); + } + if ( (value_a & 0xFFFF) == (value_b & 0xFFFF) ) { + ++count; + } + } + cout << "Part2: " << count << '\n'; +} + +} // namespace + +int +main() +{ + static const unsigned long start_a = 618; + static const unsigned long start_b = 814; + + part1(start_a, start_b); + part2(start_a, start_b); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +vector +read_line(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector result; + + for ( string line; getline(file, line, ','); ) { + result.emplace_back(line); + } + return result; +} + +vector +split(const string& line, char sep = '/') +{ + stringstream strm{ line }; + vector result; + + for ( string line; getline(strm, line, sep); ) { + result.emplace_back(line); + } + return result; +} + +void +spin(string& line, size_t n) +{ + ranges::reverse(line); + reverse(line.begin(), line.begin() + static_cast(n)); + reverse(line.begin() + static_cast(n), line.end()); +} + +void +exchange(string& line, size_t a, size_t b) +{ + swap(line.at(a), line.at(b)); +} + +void +partner(string& line, char a, char b) +{ + auto iter_a = ranges::find(line, a); + auto iter_b = ranges::find(line, b); + iter_swap(iter_a, iter_b); +} + +void +dance(const vector& instructions, string& line) +{ + for ( const auto& instr: instructions ) { + auto values = split(instr.substr(1)); + + switch ( instr.at(0) ) { + case 's': + spin(line, stoul(values.at(0))); + break; + case 'x': + exchange(line, stoul(values.at(0)), stoul(values.at(1))); + break; + case 'p': + partner(line, values.at(0).at(0), values.at(1).at(0)); + break; + default: + throw runtime_error("inknown command"); + } + } +} + +void +part1(const vector& instructions, string line) +{ + dance(instructions, line); + cout << "Part1: " << line << '\n'; +} + +#if defined(WASTE_TIME) +void +part2_bf(const vector& instructions, string line) +{ + for ( long round = 0; round != 1'000'000'000; ++round ) { + dance(instructions, line); + } + + cout << "Part2-BF: " << line << '\n'; +} +#endif + +void +part2(const vector& instructions, string line) +{ + map seen; + vector history; + + size_t cycle_start = 0; + size_t cycle_length = 0; + + for ( size_t round = 0;; ++round ) { + if ( seen.contains(line) ) { + cycle_start = seen.at(line); + cycle_length = round - cycle_start; + break; + } + + seen[line] = round; + history.emplace_back(line); + + dance(instructions, line); + } + + const size_t total_rounds = 1'000'000'000L; + const size_t remaining = (total_rounds - cycle_start) % cycle_length; + + cout << "Part2: " << history.at(cycle_start + remaining) << '\n'; +} + +void +part2_alt(const vector& instructions, const string& line) +{ + auto slow = line; + dance(instructions, slow); + + auto fast = line; + dance(instructions, fast); + dance(instructions, fast); + + // find cycle + while ( slow != fast ) { + dance(instructions, slow); + dance(instructions, fast); + dance(instructions, fast); + } + + // find cycle length + size_t cycle_length = 1; + dance(instructions, slow); + while ( slow != fast ) { + dance(instructions, slow); + ++cycle_length; + } + + // process remaining rounds + const size_t total_rounds = 1'000'000'000L; + for ( auto remaining = total_rounds % cycle_length; remaining-- > 0; ) { + dance(instructions, slow); + } + + cout << "Part2-Alt: " << slow << '\n'; +} + +} // namespace + +int +main() +{ + auto instructions = read_line("data/day16.txt"); + auto line = "abcdefghijklmnop"s; + + part1(instructions, line); + part2(instructions, line); + part2_alt(instructions, line); +} 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 @@ +#include +#include + +using namespace std; + +namespace { + +void +part1(size_t steps, size_t iterations) +{ + vector buffer{ 0 }; + size_t pos = 0; + + for ( size_t i = 1; i <= iterations; ++i ) { + pos = (pos + steps) % i + 1; + buffer.insert(buffer.begin() + static_cast::difference_type>(pos), i); + } + + cout << "Part1: " << buffer[(pos + 1) % buffer.size()] << '\n'; +} + +void +part2(size_t steps, size_t iterations) +{ + size_t pos = 0; + size_t value = 0; + + for ( size_t i = 1; i <= iterations; ++i ) { + pos = (pos + steps) % i; + if ( pos == 0 ) { + value = i; + } + pos = (pos + 1) % (i + 1); + } + + cout << "Part2: " << value << '\n'; +} + +} // namespace + +int +main() +{ + const auto input = 371; + part1(input, 2017); + part2(input, 50'000'000); +} 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 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +template +struct CPU { + [[nodiscard]] + T get(const string& ref) + { + T value{}; + auto [ptr, ec] = from_chars(ref.data(), ref.data() + ref.size(), value); + + if ( ec == errc() ) { + return value; + } + + return memory[ref]; + } + + void set(const string& ref, T value) + { + memory[ref] = value; + } + + void add(const string& ref, T value) + { + memory[ref] += value; + } + + void mul(const string& ref, T value) + { + memory[ref] *= value; + } + + void mod(const string& ref, T value) + { + memory[ref] %= value; + } + + T execute(const vector>& code) + { + long played_sound{}; + + for ( size_t ip = 0; ip < code.size(); ++ip ) { + const auto& line = code.at(ip); + const auto& opcode = line.at(0); + + if ( opcode == "snd" ) { + played_sound = get(line.at(1)); + } + else if ( opcode == "rcv" ) { + auto value = get(line.at(1)); + if ( value != 0 ) { + return played_sound; + } + } + else if ( opcode == "set" ) { + set(line.at(1), get(line.at(2))); + } + else if ( opcode == "add" ) { + add(line.at(1), get(line.at(2))); + } + else if ( opcode == "mul" ) { + mul(line.at(1), get(line.at(2))); + } + else if ( opcode == "mod" ) { + mod(line.at(1), get(line.at(2))); + } + else if ( opcode == "jgz" ) { + auto value = get(line.at(1)); + if ( value > 0 ) { + auto offset = get(line.at(2)); + ip += static_cast(offset - 1); + } + } + else { + cerr << "unknown opcode: " << opcode << '\n'; + return -1; + } + } + return -1; + } + + map memory; +}; + +template +struct CPU2 { + CPU2(queue& in, queue& out) + : in{ in } + , out{ out } + { + } + + [[nodiscard]] + T get(const string& ref) + { + T value{}; + auto [ptr, ec] = from_chars(ref.data(), ref.data() + ref.size(), value); + + if ( ec == errc() ) { + return value; + } + + return memory[ref]; + } + + void set(const string& ref, T value) + { + memory[ref] = value; + } + + void add(const string& ref, T value) + { + memory[ref] += value; + } + + void mul(const string& ref, T value) + { + memory[ref] *= value; + } + + void mod(const string& ref, T value) + { + memory[ref] %= value; + } + + bool step(const vector>& code) + { + if ( ip >= code.size() ) { + return false; + } + + const auto& line = code.at(ip); + const auto& opcode = line.at(0); + + if ( opcode == "snd" ) { + out.push(get(line.at(1))); + ++send_count; + } + else if ( opcode == "rcv" ) { + if ( in.empty() ) { + waiting = true; + return true; + } + else { + auto value = in.front(); + in.pop(); + set(line.at(1), value); + waiting = false; + } + } + else if ( opcode == "set" ) { + set(line.at(1), get(line.at(2))); + } + else if ( opcode == "add" ) { + add(line.at(1), get(line.at(2))); + } + else if ( opcode == "mul" ) { + mul(line.at(1), get(line.at(2))); + } + else if ( opcode == "mod" ) { + mod(line.at(1), get(line.at(2))); + } + else if ( opcode == "jgz" ) { + auto value = get(line.at(1)); + if ( value > 0 ) { + auto offset = get(line.at(2)); + ip += static_cast(offset); + return true; + } + } + else { + cerr << "unknown opcode: " << opcode << '\n'; + return false; + } + + ++ip; + + return true; + } + + size_t ip{}; + queue& in; + queue& out; + bool waiting{ false }; + T send_count{}; + map memory; +}; + +vector +split(const string& line) +{ + stringstream strm{ line }; + vector data; + + for ( string line; strm >> line; ) { + data.emplace_back(line); + } + + return data; +} + +vector> +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector> data; + + for ( string line; getline(file, line); ) { + const auto parts = split(line); + data.emplace_back(parts); + } + + return data; +} + +void +part1(const vector>& code) +{ + CPU cpu{}; + + cout << "Part1: " << cpu.execute(code) << '\n'; +} + +void +part2(const vector>& code) +{ + queue queue1; + queue queue2; + CPU2 cpu1{ queue1, queue2 }; + CPU2 cpu2{ queue2, queue1 }; + + cpu1.set("p", 0); + cpu2.set("p", 1); + + for ( ;; ) { + auto cpu1_running = cpu1.step(code); + auto cpu2_running = cpu2.step(code); + + if ( (cpu1.waiting || !cpu1_running) && (cpu2.waiting || !cpu2_running) ) { + break; + } + } + cout << "Part2: " << cpu2.send_count << '\n'; +} + +} // namespace + +int +main() +{ + auto instr = read_file("data/day18.txt"); + part1(instr); + part2(instr); +} 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 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +using dir_type = tuple; +using pos_type = tuple; +using puzzle_type = map; + +puzzle_type +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + puzzle_type data; + + size_t row = 0; + for ( string line; getline(file, line); ) { + for ( size_t col = 0; col != line.size(); ++col ) { + if ( line.at(col) != ' ' ) { + data.emplace(pos_type{ col, row }, line.at(col)); + } + } + ++row; + } + + return data; +} + +pos_type +find_start(const puzzle_type& puzzle) +{ + for ( size_t col = 0;; ++col ) { + const pos_type pos{ col, 0 }; + if ( puzzle.contains(pos) && puzzle.at(pos) == '|' ) { + return pos; + } + } +} + +void +solve(const puzzle_type& puzzle) +{ + string result; + size_t steps = 0; + + pos_type pos = find_start(puzzle); + dir_type dir{ 0, 1 }; + + while ( puzzle.contains(pos) ) { + auto chr = puzzle.at(pos); + + if ( chr >= 'A' && chr <= 'Z' ) { + result += chr; + } + else if ( chr == '+' ) { + auto [dx, dy] = dir; + auto left = dir_type{ -dy, dx }; + auto right = dir_type{ dy, -dx }; + + pos_type next_left = { get<0>(pos) + get<0>(left), get<1>(pos) + get<1>(left) }; + pos_type next_right = { get<0>(pos) + get<0>(right), get<1>(pos) + get<1>(right) }; + + if ( puzzle.contains(next_left) ) { + dir = left; + } + else if ( puzzle.contains(next_right) ) { + dir = right; + } + else { + cerr << "Error!\n"; + return; + } + } + + get<0>(pos) += get<0>(dir); + get<1>(pos) += get<1>(dir); + ++steps; + } + + cout << "Part1: " << result << '\n'; + cout << "Part2: " << steps << '\n'; +} + +} // namespace + +int +main() +{ + auto puzzle = read_file("data/day19.txt"); + solve(puzzle); +} 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 @@ +#include +#include +#include +#include +#include +#include + +using namespace std; + +namespace { + +using point_type = tuple; +using particle_type = tuple; + +#if 0 +ostream& +operator<<(ostream& strm, const point_type& point) +{ + const auto [x, y, z] = point; + strm << '<' << x << ',' << y << ',' << z << '>'; + return strm; +} + +ostream& +operator<<(ostream& strm, const particle_type& particle) +{ + const auto [pos, velo, accel] = particle; + strm << "p=" << pos << ", v=" << velo << ", a=" << accel; + return strm; +} +#endif + +vector +split(const string& line, const string& delimiters) +{ + vector result; + + size_t start = 0; + size_t end = 0; + + while ( (end = line.find_first_of(delimiters, start)) != string::npos ) { + if ( end != start ) { + result.emplace_back(stol(line.substr(start, end - start))); + } + + start = end + 1; + } + + if ( start != line.size() ) { + result.emplace_back(stol(line.substr(start))); + } + + return result; +} + +vector +read_file(const filesystem::path& filename) +{ + ifstream file{ filename }; + vector data; + + for ( string line; getline(file, line); ) { + auto parts = split(line, "p=<>,va "); + + point_type position{ parts.at(0), parts.at(1), parts.at(2) }; + point_type velocity{ parts.at(3), parts.at(4), parts.at(5) }; + point_type acceleration{ parts.at(6), parts.at(7), parts.at(8) }; + + data.emplace_back(position, velocity, acceleration); + } + + return data; +} + +point_type +add(const point_type& lhs, const point_type& rhs) +{ + return { get<0>(lhs) + get<0>(rhs), get<1>(lhs) + get<1>(rhs), get<2>(lhs) + get<2>(rhs) }; +} + +void +update(particle_type& particle) +{ + auto [pos, vel, acc] = particle; + + vel = add(vel, acc); + pos = add(pos, vel); + + particle = { pos, vel, acc }; +} + +long +distance(const point_type& point) +{ + return abs(get<0>(point)) + abs(get<1>(point)) + abs(get<2>(point)); +} + +void +part1(vector particles) +{ + size_t current_min_index = particles.size(); + + for ( int round = 0; round != 10000; ++round ) { + // Alle updaten + ranges::for_each(particles, update); + + long step_min_dist = numeric_limits::max(); + size_t step_min_index = current_min_index; + + // kleinste Distanz suchen + for ( size_t i = 0; i != particles.size(); ++i ) { + auto min_dist = distance(get<0>(particles.at(i))); + + if ( min_dist < step_min_dist ) { + step_min_dist = min_dist; + step_min_index = i; + } + } + + // Prüfen, ob stabil + if ( step_min_index != current_min_index ) { + current_min_index = step_min_index; + round = 0; + } + } + + cout << "Part1: " << current_min_index << '\n'; +} + +void +part2(vector particles) +{ + for ( int round = 0; round != 10000; ++round ) { + // Alle updaten + ranges::for_each(particles, update); + + map collision_counter; + + for ( const auto& [pos, vel, accl]: particles ) { + collision_counter[pos]++; + } + + for ( const auto& [pos, count]: collision_counter ) { + if ( count > 1 ) { + erase_if(particles, [&pos](const auto& particle) { return get<0>(particle) == pos; }); + round = 0; + } + } + } + + cout << "Part2: " << particles.size() << '\n'; +} + +} // namespace + +int +main() +{ + auto data = read_file("data/day20.txt"); + part1(data); + part2(data); +} -- cgit v1.3