aoc 2017, days 21-25

5 files changed, 732 insertions, 0 deletions

diff --git a/2017/src/day21.cpp b/2017/src/day21.cpp
new file mode 100644
index 0000000..64af5b6
--- /dev/null
+++ b/2017/src/day21.cpp
@@ -0,0 +1,186 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<string>
+split(const string& line, const string& delimiters)
+{
+        vector<string> 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;
+}
+
+vector<string>
+rotate90(const vector<string>& input)
+{
+        if ( input.empty() ) {
+                return {};
+        }
+
+        const auto rows = input.size();
+        const auto cols = input[0].size();
+
+        vector<string> rotated(cols, string(rows, ' '));
+
+        for ( size_t row = 0; row != rows; ++row ) {
+                for ( size_t col = 0; col != cols; ++col ) {
+                        rotated[col][rows - 1 - row] = input[row][col];
+                }
+        }
+
+        return rotated;
+}
+
+vector<string>
+flip(const vector<string>& input)
+{
+        vector<string> result = input;
+
+        // oder: ranges::reverse(result);
+        for ( auto& row: result ) {
+                ranges::reverse(row);
+        }
+
+        return result;
+}
+
+vector<vector<string>>
+generate_variants(vector<string> pattern)
+{
+        vector<vector<string>> variants;
+
+        for ( int flip_count = 0; flip_count < 2; ++flip_count ) {
+                for ( int round = 0; round < 4; ++round ) {
+                        variants.push_back(pattern);
+                        pattern = rotate90(pattern);
+                }
+                pattern = flip(pattern);
+        }
+
+        return variants;
+}
+
+map<vector<string>, vector<string>>
+read_file(const filesystem::path& filename)
+{
+        ifstream                            file{ filename };
+        map<vector<string>, vector<string>> data;
+
+        for ( string line; getline(file, line); ) {
+                auto parts = split(line, " ");
+                auto lhs   = split(parts.at(0), "/");
+                auto rhs   = split(parts.at(2), "/");
+
+                for ( const auto& variant: generate_variants(lhs) ) {
+                        data[variant] = rhs;
+                }
+        }
+
+        return data;
+}
+
+vector<string>
+enhance(const vector<string>& image, const map<vector<string>, vector<string>>& rules)
+{
+        const auto size           = image.size();
+        const auto block_size     = (size % 2 == 0) ? 2U : 3U;
+        const auto new_block_size = block_size + 1;
+        const auto blocks_per_row = size / block_size;
+        const auto new_size       = blocks_per_row * new_block_size;
+
+        vector<string> new_image(new_size, string(new_size, '.'));
+
+        // Für jeden Block...
+        for ( size_t block_row = 0; block_row != blocks_per_row; ++block_row ) {
+                for ( size_t block_col = 0; block_col != blocks_per_row; ++block_col ) {
+                        // ...Extrahiere den Block als vector<string>
+                        vector<string> block;
+                        block.reserve(block_size);
+                        for ( size_t row = 0; row != block_size; ++row ) {
+                                block.push_back(image[(block_row * block_size) + row].substr(block_col * block_size, block_size));
+                        }
+
+                        const auto& new_block = rules.at(block);
+
+                        // Füge neuen Block ins Bild ein
+                        for ( size_t row = 0; row != new_block_size; ++row ) {
+                                for ( size_t col = 0; col != new_block_size; ++col ) {
+                                        new_image[(block_row * new_block_size) + row][(block_col * new_block_size) + col] = new_block[row][col];
+                                }
+                        }
+                }
+        }
+
+        return new_image;
+}
+
+int
+count(const vector<string>& image)
+{
+        int count = 0;
+        for ( const auto& row: image ) {
+                for ( char chr: row ) {
+                        if ( chr == '#' ) {
+                                ++count;
+                        }
+                }
+        }
+        return count;
+}
+
+int
+solve(const map<vector<string>, vector<string>>& rules, size_t iterations)
+{
+        vector<string> image = { ".#.", "..#", "###" };
+
+        while ( iterations-- > 0 ) {
+                image = enhance(image, rules);
+        }
+
+        return count(image);
+}
+
+void
+part1(const map<vector<string>, vector<string>>& rules)
+{
+        cout << "Part1: " << solve(rules, 5) << '\n';
+}
+
+void
+part2(const map<vector<string>, vector<string>>& rules)
+{
+        cout << "Part2: " << solve(rules, 18) << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto rules = read_file("data/day21.txt");
+        part1(rules);
+        part2(rules);
+}
diff --git a/2017/src/day22.cpp b/2017/src/day22.cpp
new file mode 100644
index 0000000..2567fb1
--- /dev/null
+++ b/2017/src/day22.cpp
@@ -0,0 +1,158 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <string>
+#include <tuple>
+
+using namespace std;
+
+namespace {
+
+set<tuple<int, int>>
+read_file(const filesystem::path& filename)
+{
+        ifstream             file{ filename };
+        set<tuple<int, int>> data;
+
+        int row = 0;
+        for ( string line; getline(file, line); ) {
+                int col = 0;
+
+                for ( char chr: line ) {
+                        if ( chr == '#' ) {
+                                data.emplace(col, row);
+                        }
+                        ++col;
+                }
+
+                ++row;
+        }
+
+        return data;
+}
+
+#if 0
+void
+print(const set<tuple<int, int>>& grid, tuple<int, int> pos)
+{
+        for ( int y = -5; y < 5; ++y ) {
+                for ( int x = -5; x < 5; ++x ) {
+                        auto coord = make_tuple(x, y);
+
+                        if ( pos == coord ) {
+                                cout << '[';
+                        }
+                        else {
+                                cout << ' ';
+                        }
+
+                        auto chr = grid.contains(coord) ? '#' : '.';
+                        cout << chr;
+
+                        if ( pos == coord ) {
+                                cout << ']';
+                        }
+                        else {
+                                cout << ' ';
+                        }
+                }
+                cout << '\n';
+        }
+        cout << '\n';
+}
+#endif
+
+void
+part1(set<tuple<int, int>> grid, tuple<int, int> pos)
+{
+        const array<tuple<int, int>, 4> dirs{
+                make_tuple(-1, 0),
+                make_tuple(0, -1),
+                make_tuple(1, 0),
+                make_tuple(0, 1)
+        };
+        unsigned dir = 1; // up
+
+        int infections = 0;
+        for ( int i = 0; i != 10000; ++i ) {
+                if ( grid.contains(pos) ) {
+                        dir = (dir + 1) % 4;
+                        grid.erase(pos);
+                }
+                else {
+                        dir = (dir + 3) % 4;
+                        grid.insert(pos);
+                        ++infections;
+                }
+
+                auto [dx, dy] = dirs.at(dir);
+                get<0>(pos) += dx;
+                get<1>(pos) += dy;
+        }
+        cout << "Part1: " << infections << '\n';
+}
+
+void
+part2(set<tuple<int, int>> grid, tuple<int, int> pos)
+{
+        const array<tuple<int, int>, 4> dirs{
+                make_tuple(-1, 0),
+                make_tuple(0, -1),
+                make_tuple(1, 0),
+                make_tuple(0, 1)
+        };
+        unsigned dir = 1; // up
+
+        static const int weak     = 0;
+        static const int infected = 1;
+        static const int flagged  = 2;
+
+        map<tuple<int, int>, int> grid_;
+        for ( const auto& value: grid ) {
+                grid_[value] = infected;
+        }
+
+        int infections = 0;
+        for ( int i = 0; i != 10000000; ++i ) {
+                if ( !grid_.contains(pos) ) {
+                        grid_[pos] = weak;
+                        dir        = (dir + 3) % 4;
+                }
+                else {
+                        switch ( grid_[pos] ) {
+                        case weak:
+                                grid_[pos] = infected;
+                                ++infections;
+                                break;
+                        case infected:
+                                grid_[pos] = flagged;
+                                dir        = (dir + 1) % 4;
+                                break;
+                        case flagged:
+                                grid_.erase(pos);
+                                dir = (dir + 2) % 4;
+                                break;
+                        default:
+                                cerr << "Wrong state!!" << '\n';
+                                return;
+                        }
+                }
+
+                auto [dx, dy] = dirs.at(dir);
+                get<0>(pos) += dx;
+                get<1>(pos) += dy;
+        }
+        cout << "Part2: " << infections << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto grid = read_file("data/day22.txt");
+        part1(grid, { 12, 12 });
+        part2(grid, { 12, 12 });
+}
diff --git a/2017/src/day23.cpp b/2017/src/day23.cpp
new file mode 100644
index 0000000..1f4b960
--- /dev/null
+++ b/2017/src/day23.cpp
@@ -0,0 +1,158 @@
+#include <charconv>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+template<typename T>
+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 sub(const string& ref, T value)
+        {
+                memory[ref] -= value;
+        }
+
+        void mul(const string& ref, T value)
+        {
+                memory[ref] *= value;
+        }
+
+        T execute(const vector<vector<string>>& code)
+        {
+                int mul_executed = 0;
+
+                for ( size_t ip = 0; ip < code.size(); ++ip ) {
+                        const auto& line   = code.at(ip);
+                        const auto& opcode = line.at(0);
+
+                        if ( opcode == "set" ) {
+                                set(line.at(1), get(line.at(2)));
+                        }
+                        else if ( opcode == "sub" ) {
+                                sub(line.at(1), get(line.at(2)));
+                        }
+                        else if ( opcode == "mul" ) {
+                                ++mul_executed;
+                                mul(line.at(1), get(line.at(2)));
+                        }
+                        else if ( opcode == "jnz" ) {
+                                auto value = get(line.at(1));
+                                if ( value != 0 ) {
+                                        auto offset = get(line.at(2));
+                                        ip += static_cast<size_t>(offset - 1);
+                                }
+                        }
+                        else {
+                                cerr << "unknown opcode: " << opcode << '\n';
+                                return -1;
+                        }
+                }
+                return mul_executed;
+        }
+
+        map<string, T> memory;
+};
+
+vector<string>
+split(const string& line)
+{
+        stringstream   strm{ line };
+        vector<string> data;
+
+        for ( string line; strm >> line; ) {
+                data.emplace_back(line);
+        }
+
+        return data;
+}
+
+vector<vector<string>>
+read_file(const filesystem::path& filename)
+{
+        ifstream               file{ filename };
+        vector<vector<string>> data;
+
+        for ( string line; getline(file, line); ) {
+                const auto parts = split(line);
+                data.emplace_back(parts);
+        }
+
+        return data;
+}
+
+void
+part1(const vector<vector<string>>& code)
+{
+        CPU<long> cpu{};
+
+        cout << "Part1: " << cpu.execute(code) << '\n';
+}
+
+void
+part2(const vector<vector<string>>& code)
+{
+        CPU<long> cpu{};
+        cpu.memory["a"] = 1;
+
+        // execute only initialization code
+        cpu.execute({ code.begin(), code.begin() + 8 });
+
+        auto b_start = cpu.memory["b"];
+        auto c_end   = cpu.memory["c"];
+
+        auto is_prime = [](long n) {
+                if ( n < 2 ) {
+                        return false;
+                }
+                for ( long i = 2; i * i <= n; ++i ) {
+                        if ( n % i == 0 ) {
+                                return false;
+                        }
+                }
+                return true;
+        };
+
+        const long step     = 17;
+        long       memory_h = 0;
+        for ( long b = b_start; b <= c_end; b += step ) {
+                if ( !is_prime(b) ) {
+                        ++memory_h;
+                }
+        }
+
+        cout << "Part2: " << memory_h << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto instr = read_file("data/day23.txt");
+        part1(instr);
+        part2(instr);
+}
diff --git a/2017/src/day24.cpp b/2017/src/day24.cpp
new file mode 100644
index 0000000..fa4148c
--- /dev/null
+++ b/2017/src/day24.cpp
@@ -0,0 +1,102 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <set>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<tuple<long, long>>
+read_file(const filesystem::path& filename)
+{
+        ifstream                  file{ filename };
+        vector<tuple<long, long>> data;
+
+        long lhs = 0;
+        long rhs = 0;
+        char sep = 0;
+
+        while ( file >> lhs >> sep >> rhs ) {
+                data.emplace_back(lhs, rhs);
+        }
+        return data;
+}
+
+long
+strongest(const vector<tuple<long, long>>& data, long current = 0, const set<size_t>& used = {})
+{
+        long best_strength = 0;
+
+        for ( size_t i = 0; i != data.size(); ++i ) {
+                if ( used.contains(i) ) {
+                        continue;
+                }
+
+                auto [lhs, rhs] = data.at(i);
+                if ( lhs == current || rhs == current ) {
+                        auto next_port = (lhs == current) ? rhs : lhs;
+                        auto new_used{ used };
+                        new_used.emplace(i);
+                        auto strength = lhs + rhs + strongest(data, next_port, new_used);
+                        best_strength = max(best_strength, strength);
+                }
+        }
+
+        return best_strength;
+}
+
+tuple<long, size_t>
+strongest_and_longest(const vector<tuple<long, long>>& data, long current = 0, const set<size_t>& used = {})
+{
+        long   best_strength = 0;
+        size_t best_length   = 0;
+
+        for ( size_t i = 0; i != data.size(); ++i ) {
+                if ( used.contains(i) ) {
+                        continue;
+                }
+
+                auto [lhs, rhs] = data.at(i);
+                if ( lhs == current || rhs == current ) {
+                        auto next_port = (lhs == current) ? rhs : lhs;
+                        auto new_used{ used };
+                        new_used.emplace(i);
+                        auto [sub_strength, sub_length] = strongest_and_longest(data, next_port, new_used);
+
+                        auto total_strength = sub_strength + lhs + rhs;
+                        auto total_length   = sub_length + 1;
+
+                        if ( total_length > best_length || (total_length == best_length && total_strength > best_strength) ) {
+                                best_strength = total_strength;
+                                best_length   = total_length;
+                        }
+                }
+        }
+
+        return make_tuple(best_strength, best_length);
+}
+
+void
+part1(const vector<tuple<long, long>>& data)
+{
+        cout << "Part1: " << strongest(data) << '\n';
+}
+
+void
+part2(const vector<tuple<long, long>>& data)
+{
+        auto [strength, length] = strongest_and_longest(data);
+        cout << "Part2: " << strength << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto data = read_file("data/day24.txt");
+        part1(data);
+        part2(data);
+}
diff --git a/2017/src/day25.cpp b/2017/src/day25.cpp
new file mode 100644
index 0000000..36b7dd0
--- /dev/null
+++ b/2017/src/day25.cpp
@@ -0,0 +1,128 @@
+#include <array>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <iterator>
+#include <map>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<string>
+split(const string& line, const string& delimiter)
+{
+        vector<string> result;
+
+        size_t start = 0;
+        size_t end   = 0;
+
+        while ( (end = line.find(delimiter, start)) != string::npos ) {
+                if ( end != start ) {
+                        result.emplace_back(line.substr(start, end - start));
+                }
+
+                start = end + delimiter.length();
+        }
+
+        if ( start != line.size() ) {
+                result.emplace_back(line.substr(start));
+        }
+
+        return result;
+}
+
+vector<vector<vector<string>>>
+read_file(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+        string   content{ istreambuf_iterator<char>{ file }, {} };
+
+        vector<vector<vector<string>>> result;
+
+        auto blocks = split(content, "\n\n");
+        for ( const auto& block: blocks ) {
+                vector<vector<string>> data;
+
+                auto lines = split(block, "\n");
+                for ( auto line: lines ) {
+                        line.pop_back();
+                        auto words = split(line, " ");
+                        data.emplace_back(words);
+                }
+
+                result.emplace_back(data);
+        }
+
+        return result;
+}
+
+using action_type    = tuple<int, int, string>;       // value (0, 1), direction (-1, 1), next_state)
+using condition_type = array<action_type, 2>;         // [0] -> action, [1] -> action
+using rule_type      = map<string, condition_type>;   // "A" -> condition
+using puzzle_type    = tuple<string, int, rule_type>; // (start_state, steps, rules)
+
+puzzle_type
+parse_input(const vector<vector<vector<string>>>& input)
+{
+        rule_type rules{};
+
+        for ( size_t idx = 1; idx < input.size(); ++idx ) {
+                const auto& block = input.at(idx);
+
+                condition_type condition{};
+
+                for ( size_t i = 0; i != 2; ++i ) {
+                        const auto base = i * 4;
+
+                        auto read_val   = stoul(block.at(base + 1).back());
+                        auto write_val  = stoi(block.at(base + 2).back());
+                        auto dir        = block.at(base + 3).back() == "left" ? -1 : 1;
+                        auto next_state = block.at(base + 4).back();
+
+                        condition.at(read_val) = { write_val, dir, next_state };
+                }
+
+                rules[block.at(0).back()] = condition;
+        }
+
+        auto start_state = input[0][0][3];
+        auto steps       = stoi(input[0][1][5]);
+
+        return puzzle_type{ start_state, steps, rules };
+}
+
+void
+part1(const puzzle_type& puzzle)
+{
+        auto [state, steps, rules] = puzzle;
+
+        map<int, int> tape;
+
+        int pos = 0;
+
+        while ( steps-- > 0 ) {
+                auto value                            = tape[pos];
+                const auto& [write, move, next_state] = rules.at(state).at(size_t(value));
+                state                                 = next_state;
+                tape[pos]                             = write;
+                pos += move;
+        }
+
+        int sum = 0;
+        for ( const auto& [key, value]: tape ) {
+                sum += value;
+        }
+        cout << "Part1: " << sum << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto input = read_file("data/day25.txt");
+        part1(parse_input(input));
+}