days 19-25, aoc 2016

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 @@
+#include <cmath>
+#include <iostream>
+
+using namespace std;
+
+namespace {
+
+template<typename T>
+T
+fn(T N)
+    requires std::is_integral_v<T>
+{
+        return T(1) << static_cast<T>(floor(log2(N)));
+}
+
+void
+part1(unsigned N)
+{
+        cout << (2 * (N - fn(N))) + 1 << '\n';
+}
+
+void
+part2(unsigned N)
+{
+        auto log_3 = [](double x) { return log(x) / log(3); };
+
+        auto threes = pow(3, floor(log_3(N - 1)));
+        if ( N <= 2 * threes ) {
+                cout << static_cast<unsigned>(N - threes);
+        }
+        else {
+                cout << static_cast<unsigned>(N - threes + N - (2 * threes));
+        }
+        cout << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        const unsigned puzzle = 3017957;
+        part1(puzzle);
+        part2(puzzle);
+}
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 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Range {
+        long long start;
+        long long end;
+};
+
+vector<Range>
+readFile(const filesystem::path& filename)
+{
+        ifstream      file{ filename };
+        vector<Range> ranges;
+
+        for ( string line; getline(file, line); ) {
+                stringstream stream{ line };
+                char         dash{};
+                long long    start{};
+                long long    end{};
+
+                stream >> start >> dash >> end;
+
+                ranges.emplace_back(start, end);
+        }
+
+        return ranges;
+}
+
+void
+sortRanges(vector<Range>& ranges)
+{
+        ranges::sort(ranges, [](const auto& lhs, const auto& rhs) {
+                if ( lhs.start != rhs.start ) {
+                        return lhs.start < rhs.start;
+                }
+                return lhs.end < rhs.end;
+        });
+}
+
+void
+mergeRanges(vector<Range>& ranges)
+{
+        if ( ranges.empty() ) {
+                return;
+        }
+
+        vector<Range> mergedRanges;
+
+        auto current = ranges[0];
+        for ( size_t i = 1; i != ranges.size(); ++i ) {
+                if ( ranges[i].start <= current.end + 1 ) {
+                        current.end = max(current.end, ranges[i].end);
+                }
+                else {
+                        mergedRanges.emplace_back(current);
+                        current = ranges[i];
+                }
+        }
+        mergedRanges.emplace_back(current);
+
+        ranges.swap(mergedRanges);
+}
+
+long long
+findLowestAllowedIP(const vector<Range>& ranges)
+{
+        if ( ranges.empty() || ranges[0].start > 0 ) {
+                return 0;
+        }
+        return ranges[0].end + 1;
+}
+
+long long
+countAllowedIPs(const vector<Range>& ranges, long long max_ip)
+{
+        long long allowed_count = 0;
+
+        for ( size_t i = 0; i < ranges.size() - 1; ++i ) {
+                allowed_count += ranges[i + 1].start - ranges[i].end - 1;
+        }
+
+        if ( !ranges.empty() && ranges.back().end < max_ip ) {
+                allowed_count += max_ip - ranges.back().end;
+        }
+
+        if ( ranges.empty() ) {
+                allowed_count = max_ip + 1;
+        }
+
+        return allowed_count;
+}
+
+void
+part1(vector<Range> ranges)
+{
+        sortRanges(ranges);
+        mergeRanges(ranges);
+
+        cout << findLowestAllowedIP(ranges) << '\n';
+}
+
+void
+part2(vector<Range> ranges, long long max_ip = 4294967295)
+{
+        sortRanges(ranges);
+        mergeRanges(ranges);
+
+        cout << countAllowedIPs(ranges, max_ip) << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto ranges = readFile("data/day20.txt");
+        part1(ranges);
+        part2(ranges);
+}
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 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <ranges>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+void
+swap_at_pos(string& str, size_t x, size_t y)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        swap(str.at(x), str.at(y));
+}
+
+void
+swap_letter(string& str, char x, char y)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        for ( auto& chr: str ) {
+                if ( chr == x ) {
+                        chr = y;
+                }
+                else if ( chr == y ) {
+                        chr = x;
+                }
+        }
+}
+
+void
+rotate_left(string& str, size_t n)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        ranges::rotate(str, str.begin() + static_cast<int>(n % str.size()));
+}
+
+void
+rotate_right(string& str, size_t n)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        rotate_left(str, str.size() - n);
+}
+
+void
+rotate(string& str, char chr)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        const auto idx = str.find(chr);
+        if ( idx == string::npos ) {
+                return;
+        }
+
+        const auto steps = 1 + idx + (idx >= 4 ? 1 : 0);
+        rotate_right(str, steps % str.size());
+}
+
+void
+reverse(string& str, size_t x, size_t y)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        if ( x > y ) {
+                swap(x, y);
+        }
+
+        reverse(str.begin() + static_cast<string::difference_type>(x),
+                str.begin() + static_cast<string::difference_type>(y) + 1);
+}
+
+void
+move(string& str, size_t x, size_t y)
+{
+        if ( str.empty() ) {
+                return;
+        }
+
+        const auto chr = str.at(x);
+
+        str.erase(x, 1);
+        str.insert(y, 1, chr);
+}
+
+vector<string>
+readLines(const filesystem::path& filename)
+{
+        ifstream       file{ filename };
+        vector<string> lines;
+
+        for ( string line; getline(file, line); ) {
+                lines.emplace_back(line);
+        }
+
+        return lines;
+}
+
+vector<string>
+split(const string& line, char sep = ' ')
+{
+        vector<string> words;
+        stringstream   input{ line };
+
+        for ( string word; getline(input, word, sep); ) {
+                words.emplace_back(word);
+        }
+
+        return words;
+}
+
+void
+part1(const vector<string>& lines, string str)
+{
+        for ( const auto& line: lines ) {
+                auto words = split(line);
+
+                if ( line.starts_with("swap position") ) {
+                        swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5)));
+                }
+                else if ( line.starts_with("swap letter") ) {
+                        swap_letter(str, words.at(2).at(0), words.at(5).at(0));
+                }
+                else if ( line.starts_with("rotate left") ) {
+                        rotate_left(str, stoull(words.at(2)));
+                }
+                else if ( line.starts_with("rotate right") ) {
+                        rotate_right(str, stoull(words.at(2)));
+                }
+                else if ( line.starts_with("rotate based") ) {
+                        rotate(str, words.at(6).at(0));
+                }
+                else if ( line.starts_with("reverse") ) {
+                        reverse(str, stoull(words.at(2)), stoull(words.at(4)));
+                }
+                else if ( line.starts_with("move") ) {
+                        move(str, stoull(words.at(2)), stoull(words.at(5)));
+                }
+                else {
+                        cerr << "unknown command: " << line << '\n';
+                        return;
+                }
+        }
+        cout << str << '\n';
+}
+
+void
+part2(const vector<string>& lines, string str)
+{
+        for ( const auto& line: ranges::reverse_view(lines) ) {
+                auto words = split(line);
+
+                if ( line.starts_with("swap position") ) {
+                        swap_at_pos(str, stoull(words.at(2)), stoull(words.at(5)));
+                }
+                else if ( line.starts_with("swap letter") ) {
+                        swap_letter(str, words.at(2).at(0), words.at(5).at(0));
+                }
+                else if ( line.starts_with("rotate left") ) {
+                        rotate_right(str, stoull(words.at(2)));
+                }
+                else if ( line.starts_with("rotate right") ) {
+                        rotate_left(str, stoull(words.at(2)));
+                }
+                else if ( line.starts_with("rotate based") ) {
+                        auto chr = words.at(6).at(0);
+                        for ( size_t i = 0; i != str.size(); ++i ) {
+                                string tmp = str;
+                                rotate_left(tmp, i);
+
+                                auto idx   = tmp.find(chr);
+                                auto steps = (1 + idx + (idx >= 4 ? 1 : 0));
+
+                                if ( ((steps - i + str.size()) % str.size()) == 0 ) {
+                                        str = tmp;
+                                        break;
+                                }
+                        }
+                }
+                else if ( line.starts_with("reverse") ) {
+                        reverse(str, stoull(words.at(2)), stoull(words.at(4)));
+                }
+                else if ( line.starts_with("move") ) {
+                        move(str, stoull(words.at(5)), stoull(words.at(2)));
+                }
+                else {
+                        cerr << "unknown command: " << line << '\n';
+                        return;
+                }
+        }
+        cout << str << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto lines = readLines("data/day21.txt");
+
+        part1(lines, "abcdefgh");
+        part2(lines, "fbgdceah");
+}
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 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Node {
+        int x, y;
+        int size, used, avail, percent;
+
+        [[nodiscard]]
+        tuple<int, int> pos() const
+        {
+                return { x, y };
+        }
+};
+
+vector<Node>
+readNodes(const filesystem::path& filename)
+{
+        static const regex line_regex(R"(^/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T\s+(\d+)%$)");
+
+        ifstream     file{ filename };
+        vector<Node> nodes;
+
+        for ( string line; getline(file, line); ) {
+                smatch match;
+
+                if ( !regex_match(line, match, line_regex) ) {
+                        continue;
+                }
+
+                Node node{
+                        .x       = stoi(match[1].str()), // x
+                        .y       = stoi(match[2].str()), // y
+                        .size    = stoi(match[3].str()), // size
+                        .used    = stoi(match[4].str()), // used
+                        .avail   = stoi(match[5].str()), // avail
+                        .percent = stoi(match[6].str())  // percent
+                };
+
+                nodes.emplace_back(node);
+        }
+
+        return nodes;
+}
+
+void
+part1(const vector<Node>& nodes)
+{
+        long count = 0;
+
+        for ( size_t i = 0; i != nodes.size(); ++i ) {
+                if ( nodes[i].used == 0 ) {
+                        continue;
+                }
+
+                for ( size_t j = 0; j != nodes.size(); ++j ) {
+                        if ( i == j ) {
+                                continue;
+                        }
+
+                        if ( nodes[i].used < nodes[j].avail ) {
+                                ++count;
+                        }
+                }
+        }
+
+        cout << count << '\n';
+}
+
+void
+part2(const vector<Node>& nodes)
+{
+        using pos_type = tuple<int, int>;
+
+        map<pos_type, char> grid;
+
+#ifdef PRINT
+        const auto max_y = ranges::max_element(nodes, {}, &Node::y)->y;
+#endif
+        const auto max_x   = ranges::max_element(nodes, {}, &Node::x)->x;
+        const auto largest = ranges::max_element(nodes, {}, &Node::avail)->avail;
+
+        const pos_type g_pos = { max_x, 0 };
+        const pos_type s_pos = { 0, 0 };
+
+        pos_type start{};
+
+        for ( const auto& node: nodes ) {
+                auto pos = node.pos();
+                if ( pos == s_pos ) {
+                        grid[pos] = 'S';
+                }
+                else if ( pos == g_pos ) {
+                        grid[pos] = 'G';
+                }
+                else if ( node.used == 0 ) {
+                        grid[pos] = '_';
+                        start     = pos;
+                }
+                else if ( node.used >= largest ) {
+                        grid[pos] = '#';
+                }
+                else {
+                        grid[pos] = '.';
+                }
+        }
+
+#ifdef PRINT
+        string result{};
+        for ( int pos_y = 0; pos_y <= max_y; ++pos_y ) {
+                for ( int pos_x = 0; pos_x <= max_x; ++pos_x ) {
+                        result += grid[{ pos_x, pos_y }];
+                }
+                result += '\n';
+        }
+
+        cout << result << '\n';
+#endif
+
+        set<pos_type>               seen;
+        queue<tuple<pos_type, int>> queue; // position, #Schritte
+
+        queue.emplace(start, 0);
+        while ( !queue.empty() ) {
+                const auto [pos, steps] = queue.front();
+                queue.pop();
+
+                if ( pos == g_pos ) {
+                        cout << steps + (5 * (max_x - 1)) << '\n';
+                        return;
+                }
+
+                static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
+
+                for ( const auto [dx, dy]: dirs ) {
+                        const auto [x, y] = pos;
+                        const pos_type new_pos{ x + dx, y + dy };
+
+                        if ( !grid.contains(new_pos) || grid.at(new_pos) == '#' || seen.contains(new_pos) ) {
+                                continue;
+                        }
+
+                        seen.insert(new_pos);
+                        queue.emplace(new_pos, steps + 1);
+                }
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        auto nodes = readNodes("data/day22.txt");
+        part1(nodes);
+        part2(nodes);
+}
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 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <optional>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+enum class OpCode : uint8_t {
+        CPY,
+        INC,
+        DEC,
+        JNZ,
+        TGL
+};
+
+using memory_type = map<char, int>;
+
+struct Argument {
+        explicit Argument(string value)
+            : value{ std::move(value) }
+        {
+        }
+
+        [[nodiscard]]
+        int eval(const memory_type& memory) const
+        {
+                const auto chr = value.at(0);
+
+                if ( chr >= 'a' && chr <= 'z' ) {
+                        return memory.at(chr);
+                }
+                else {
+                        return stoi(value);
+                }
+        }
+
+        [[nodiscard]]
+        char reg() const
+        {
+                if ( !is_reg() ) {
+                        throw runtime_error("invalid register access! "s + value);
+                }
+
+                return value.at(0);
+        }
+
+        [[nodiscard]]
+        bool is_reg() const
+        {
+                const auto chr = value.at(0);
+
+                return chr >= 'a' && chr <= 'z';
+        }
+
+        string value;
+};
+
+struct Instruction {
+        Instruction(OpCode opCode, const Argument& x)
+            : opCode{ opCode }
+            , x{ x }
+        {
+        }
+
+        Instruction(OpCode opCode, const Argument& x, const Argument& y)
+            : opCode{ opCode }
+            , x{ x }
+            , y{ y }
+        {
+        }
+
+        OpCode             opCode;
+        optional<Argument> x;
+        optional<Argument> y;
+};
+
+vector<string>
+split_words(const string& line, char sep = ' ')
+{
+        vector<string> words;
+        stringstream   strm{ line };
+
+        for ( string word; getline(strm, word, sep); ) {
+                words.emplace_back(word);
+        }
+
+        return words;
+}
+
+vector<Instruction>
+read_file(const filesystem::path& filename)
+{
+        ifstream input{ filename };
+
+        vector<Instruction> instructions;
+
+        for ( string line; getline(input, line); ) {
+                const auto words = split_words(line);
+
+                if ( words.at(0) == "cpy" ) {
+                        instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2)));
+                }
+                else if ( words.at(0) == "inc" ) {
+                        instructions.emplace_back(OpCode::INC, Argument(words.at(1)));
+                }
+                else if ( words.at(0) == "dec" ) {
+                        instructions.emplace_back(OpCode::DEC, Argument(words.at(1)));
+                }
+                else if ( words.at(0) == "jnz" ) {
+                        instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2)));
+                }
+                else if ( words.at(0) == "tgl" ) {
+                        instructions.emplace_back(OpCode::TGL, Argument(words.at(1)));
+                }
+                else {
+                        cerr << "unknown opcode..." << '\n';
+                }
+        }
+
+        return instructions;
+}
+
+#define JIT
+
+void
+execute(memory_type& memory, vector<Instruction> instructions)
+{
+        for ( size_t ip = 0; ip < instructions.size(); ) {
+#if defined(JIT)
+                if ( ip + 2 < instructions.size() ) {
+                        const auto& i0 = instructions[ip];
+                        const auto& i1 = instructions[ip + 1];
+                        const auto& i2 = instructions[ip + 2];
+
+                        if ( i0.opCode == OpCode::INC &&
+                             i1.opCode == OpCode::DEC &&
+                             i2.opCode == OpCode::JNZ &&
+                             i2.x && i2.x->value == i1.x->value &&
+                             i2.y && i2.y->value == "-2" ) {
+                                char X = i0.x->reg();
+                                char Y = i1.x->reg();
+                                memory[X] += memory[Y];
+                                memory[Y] = 0;
+                                ip += 3;
+                                continue;
+                        }
+                }
+#endif
+
+#if defined(JIT)
+                if ( ip + 5 < instructions.size() ) {
+                        const auto& i0 = instructions[ip];
+                        const auto& i1 = instructions[ip + 1];
+                        const auto& i2 = instructions[ip + 2];
+                        const auto& i3 = instructions[ip + 3];
+                        const auto& i4 = instructions[ip + 4];
+                        const auto& i5 = instructions[ip + 5];
+
+                        if ( i0.opCode == OpCode::CPY &&
+                             i1.opCode == OpCode::INC &&
+                             i2.opCode == OpCode::DEC &&
+                             i3.opCode == OpCode::JNZ &&
+                             i4.opCode == OpCode::DEC &&
+                             i5.opCode == OpCode::JNZ &&
+                             i3.x && i3.y && i3.x->value == i2.x->value && i3.y->value == "-2" &&
+                             i5.x && i5.y && i5.x->value == i4.x->value && i5.y->value == "-5" &&
+                             i0.y->is_reg() && i1.x->is_reg() && i2.x->is_reg() && i4.x->is_reg() ) {
+                                char X    = i0.x->is_reg() ? i0.x->reg() : 0;
+                                int  valX = i0.x->is_reg() ? memory[X] : stoi(i0.x->value);
+
+                                char Y = i0.y->reg();
+                                char Z = i1.x->reg();
+                                char W = i4.x->reg();
+
+                                memory[Z] += valX * memory[W];
+                                memory[Y] = 0;
+                                memory[W] = 0;
+                                ip += 6;
+                                continue;
+                        }
+                }
+#endif
+
+                const auto& instruction = instructions.at(ip);
+
+                // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n';
+
+                switch ( instruction.opCode ) {
+                        using enum OpCode;
+                case CPY:
+                        memory[instruction.y->reg()] = instruction.x->eval(memory);
+                        ++ip;
+                        break;
+                case INC:
+                        memory[instruction.x->reg()]++;
+                        ++ip;
+                        break;
+                case DEC:
+                        memory[instruction.x->reg()]--;
+                        ++ip;
+                        break;
+                case JNZ:
+                        if ( instruction.x->eval(memory) != 0 ) {
+                                ip += static_cast<size_t>(instruction.y->eval(memory));
+                        }
+                        else {
+                                ++ip;
+                        }
+                        break;
+                case TGL:
+                        if ( auto foo = ip + static_cast<size_t>(instruction.x->eval(memory)); foo < instructions.size() ) {
+                                switch ( instructions[foo].opCode ) {
+                                case CPY:
+                                        instructions[foo].opCode = JNZ;
+                                        break;
+                                case INC:
+                                        instructions[foo].opCode = DEC;
+                                        break;
+                                case DEC:
+                                        instructions[foo].opCode = INC;
+                                        break;
+                                case JNZ:
+                                        instructions[foo].opCode = CPY;
+                                        break;
+                                case TGL:
+                                        instructions[foo].opCode = INC;
+                                        break;
+                                }
+                        }
+
+                        ++ip;
+                        break;
+                }
+        }
+}
+
+void
+part1(const vector<Instruction>& instructions)
+{
+        map<char, int> memory;
+
+        memory['a'] = 7;
+        memory['b'] = 0;
+        memory['c'] = 0;
+        memory['d'] = 0;
+
+        execute(memory, instructions);
+
+        cout << "Part1: " << memory['a'] << '\n';
+}
+
+void
+part2(const vector<Instruction>& instructions)
+{
+        map<char, int> memory;
+
+        memory['a'] = 12;
+        memory['b'] = 0;
+        memory['c'] = 0;
+        memory['d'] = 0;
+
+        execute(memory, instructions);
+
+        cout << "Part2: " << memory['a'] << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        const auto instructions = read_file("data/day23.txt");
+        try {
+                part1(instructions);
+                part2(instructions);
+        }
+        catch ( exception& e ) {
+                cerr << e.what() << '\n';
+        }
+}
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 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+
+using namespace std;
+
+namespace {
+
+using pos_type    = tuple<size_t, size_t>;
+using grid_type   = map<pos_type, char>;
+using points_type = map<char, pos_type>;
+using dists_type  = map<tuple<char, char>, size_t>;
+
+tuple<grid_type, points_type>
+read_file(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+
+        grid_type   grid;
+        points_type points;
+
+        size_t row = 0;
+        for ( string line; getline(file, line); ) {
+                for ( size_t col = 0; col != line.size(); ++col ) {
+                        auto     chr = line[col];
+                        pos_type pos{ col, row };
+
+                        grid[pos] = chr;
+
+                        if ( isdigit(chr) != 0 ) {
+                                points[chr] = pos;
+                        }
+                }
+
+                ++row;
+        }
+        return { grid, points };
+}
+
+size_t
+bfs(const grid_type& grid, const pos_type src, const pos_type dest)
+{
+        set<pos_type>                  seen;
+        queue<tuple<pos_type, size_t>> queue;
+
+        queue.emplace(src, 0);
+        seen.insert(src);
+
+        while ( !queue.empty() ) {
+                auto [pos, steps] = queue.front();
+                queue.pop();
+
+                if ( pos == dest ) {
+                        return steps;
+                }
+
+                static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
+                const auto [x, y] = pos;
+
+                for ( const auto [dx, dy]: dirs ) {
+                        const pos_type new_pos{ x + dx, y + dy };
+
+                        if ( grid.at(new_pos) == '#' || seen.contains(new_pos) ) {
+                                continue;
+                        }
+
+                        seen.insert(new_pos);
+                        queue.emplace(new_pos, steps + 1);
+                }
+        }
+
+        return 0;
+}
+
+dists_type
+build_dists(const grid_type& grid, const points_type& points)
+{
+        dists_type dists;
+
+        for ( auto src = points.begin(); src != points.end(); ++src ) {
+                for ( auto dest = next(src); dest != points.end(); ++dest ) {
+                        const auto dist = bfs(grid, src->second, dest->second);
+
+                        dists[{ src->first, dest->first }] = dist;
+                        dists[{ dest->first, src->first }] = dist;
+                }
+        }
+
+        return dists;
+}
+
+size_t
+shortest_route(const dists_type&  dists,
+               const points_type& points,
+               bool               return_to_start)
+{
+        vector<char> others;
+        for ( const auto& [id, _]: points ) {
+                if ( id != '0' ) {
+                        others.push_back(id);
+                }
+        }
+
+        size_t best = numeric_limits<size_t>::max();
+
+        do {
+                size_t dist    = 0;
+                char   current = '0';
+
+                for ( char next: others ) {
+                        dist += dists.at({ current, next });
+                        current = next;
+                }
+
+                if ( return_to_start ) {
+                        dist += dists.at({ current, '0' });
+                }
+
+                best = min(best, dist);
+        } while ( next_permutation(others.begin(), others.end()) );
+
+        return best;
+}
+
+void
+part1(const grid_type& grid, const points_type& points)
+{
+        auto dists = build_dists(grid, points);
+        auto route = shortest_route(dists, points, false);
+        cout << "Part1: " << route << '\n';
+}
+
+void
+part2(const grid_type& grid, const points_type& points)
+{
+        auto dists = build_dists(grid, points);
+        auto route = shortest_route(dists, points, true);
+        cout << "Part2: " << route << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto [grid, points] = read_file("data/day24.txt");
+        part1(grid, points);
+        part2(grid, points);
+}
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 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <optional>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+enum class OpCode : uint8_t {
+        CPY,
+        INC,
+        DEC,
+        JNZ,
+        OUT,
+};
+
+using memory_type = map<char, int>;
+
+struct Argument {
+        explicit Argument(string value)
+            : value{ std::move(value) }
+        {
+        }
+
+        [[nodiscard]]
+        int eval(const memory_type& memory) const
+        {
+                const auto chr = value.at(0);
+
+                if ( chr >= 'a' && chr <= 'z' ) {
+                        return memory.at(chr);
+                }
+                else {
+                        return stoi(value);
+                }
+        }
+
+        [[nodiscard]]
+        char reg() const
+        {
+                if ( !is_reg() ) {
+                        throw runtime_error("invalid register access! "s + value);
+                }
+
+                return value.at(0);
+        }
+
+        [[nodiscard]]
+        bool is_reg() const
+        {
+                const auto chr = value.at(0);
+
+                return chr >= 'a' && chr <= 'z';
+        }
+
+        string value;
+};
+
+struct Instruction {
+        Instruction(OpCode opCode, const Argument& x)
+            : opCode{ opCode }
+            , x{ x }
+        {
+        }
+
+        Instruction(OpCode opCode, const Argument& x, const Argument& y)
+            : opCode{ opCode }
+            , x{ x }
+            , y{ y }
+        {
+        }
+
+        OpCode             opCode;
+        optional<Argument> x;
+        optional<Argument> y;
+};
+
+vector<string>
+split_words(const string& line, char sep = ' ')
+{
+        vector<string> words;
+        stringstream   strm{ line };
+
+        for ( string word; getline(strm, word, sep); ) {
+                words.emplace_back(word);
+        }
+
+        return words;
+}
+
+vector<Instruction>
+read_file(const filesystem::path& filename)
+{
+        ifstream input{ filename };
+
+        vector<Instruction> instructions;
+
+        for ( string line; getline(input, line); ) {
+                const auto words = split_words(line);
+
+                if ( words.at(0) == "cpy" ) {
+                        instructions.emplace_back(OpCode::CPY, Argument(words.at(1)), Argument(words.at(2)));
+                }
+                else if ( words.at(0) == "inc" ) {
+                        instructions.emplace_back(OpCode::INC, Argument(words.at(1)));
+                }
+                else if ( words.at(0) == "dec" ) {
+                        instructions.emplace_back(OpCode::DEC, Argument(words.at(1)));
+                }
+                else if ( words.at(0) == "jnz" ) {
+                        instructions.emplace_back(OpCode::JNZ, Argument(words.at(1)), Argument(words.at(2)));
+                }
+                else if ( words.at(0) == "out" ) {
+                        instructions.emplace_back(OpCode::OUT, Argument(words.at(1)));
+                }
+                else {
+                        cerr << "unknown opcode..." << '\n';
+                }
+        }
+
+        return instructions;
+}
+
+#define JIT
+
+string
+execute(memory_type& memory, vector<Instruction> instructions)
+{
+        string result;
+
+        for ( size_t ip = 0; ip < instructions.size(); ) {
+                const auto& instruction = instructions.at(ip);
+
+                // cout << "#" << ip << " - " << memory['a'] << ", " << memory['b'] << ", " << memory['c'] << ", " << memory['d'] << ": " << (int) instruction.opCode << '\n';
+
+                switch ( instruction.opCode ) {
+                        using enum OpCode;
+                case CPY:
+                        memory[instruction.y->reg()] = instruction.x->eval(memory);
+                        ++ip;
+                        break;
+                case INC:
+                        memory[instruction.x->reg()]++;
+                        ++ip;
+                        break;
+                case DEC:
+                        memory[instruction.x->reg()]--;
+                        ++ip;
+                        break;
+                case JNZ:
+                        if ( instruction.x->eval(memory) != 0 ) {
+                                ip += static_cast<size_t>(instruction.y->eval(memory));
+                        }
+                        else {
+                                ++ip;
+                        }
+                        break;
+                case OUT:
+                        result += to_string(instruction.x->eval(memory));
+                        if ( result.size() >= 20 ) {
+                                ip = instructions.size();
+                        }
+                        else {
+                                ++ip;
+                        }
+                }
+        }
+
+        return result;
+}
+
+void
+part1(const vector<Instruction>& instructions)
+{
+        for ( int seed = 0;; ++seed ) {
+                map<char, int> memory;
+
+                memory['a'] = seed;
+                memory['b'] = 0;
+                memory['c'] = 0;
+                memory['d'] = 0;
+
+                auto result = execute(memory, instructions);
+
+                if ( result == "01010101010101010101" ) {
+                        cout << "Part1: " << seed << '\n';
+                        return;
+                }
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        const auto instructions = read_file("data/day25.txt");
+        try {
+                part1(instructions);
+        }
+        catch ( exception& e ) {
+                cerr << e.what() << '\n';
+        }
+}