From 756f22d58bb198b8f34589c112e1003614ccdcd6 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 2 Nov 2025 21:41:58 +0100
Subject: aoc 2017, days 1-20

---
 2017/src/day14.cpp | 146 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 146 insertions(+)
 create mode 100644 2017/src/day14.cpp

(limited to '2017/src/day14.cpp')

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 <array>
+#include <iostream>
+#include <numeric>
+#include <queue>
+#include <set>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<unsigned>
+gen_data(size_t len)
+{
+	vector<unsigned> data(len);
+	iota(data.begin(), data.end(), 0UL);
+	return data;
+}
+
+void
+reverse(vector<unsigned>& 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<unsigned>& data, const vector<size_t>& 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<uint8_t>
+knothash(string line)
+{
+	line += char(17);
+	line += char(31);
+	line += char(73);
+	line += char(47);
+	line += char(23);
+
+	vector<size_t> lengths;
+	for ( const auto byte: line ) {
+		lengths.emplace_back(static_cast<unsigned char>(byte));
+	}
+
+	auto data = gen_data(256);
+	hash64(data, lengths);
+
+	vector<uint8_t> 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<tuple<size_t, size_t>> 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<tuple<size_t, size_t>> queue;
+			queue.emplace(x, y);
+
+			while ( !queue.empty() ) {
+				auto pos = queue.front();
+				queue.pop();
+
+				grid.erase(pos);
+
+				static array<tuple<size_t, size_t>, 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);
+}
-- 
cgit v1.3