From ae1e96f10b399266825e275ca4a8100ceede9cad Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 23 Oct 2025 19:28:20 +0200
Subject: days 19-25, aoc 2016

---
 2016/src/day22.cpp | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 166 insertions(+)
 create mode 100644 2016/src/day22.cpp

(limited to '2016/src/day22.cpp')

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);
+}
-- 
cgit v1.3