1 files changed, 166 insertions, 0 deletions

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);
+}