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/day16.cpp | 174 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 174 insertions(+)
 create mode 100644 2017/src/day16.cpp

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

diff --git a/2017/src/day16.cpp b/2017/src/day16.cpp
new file mode 100644
index 0000000..ea048bb
--- /dev/null
+++ b/2017/src/day16.cpp
@@ -0,0 +1,174 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<string>
+read_line(const filesystem::path& filename)
+{
+	ifstream       file{ filename };
+	vector<string> result;
+
+	for ( string line; getline(file, line, ','); ) {
+		result.emplace_back(line);
+	}
+	return result;
+}
+
+vector<string>
+split(const string& line, char sep = '/')
+{
+	stringstream   strm{ line };
+	vector<string> result;
+
+	for ( string line; getline(strm, line, sep); ) {
+		result.emplace_back(line);
+	}
+	return result;
+}
+
+void
+spin(string& line, size_t n)
+{
+	ranges::reverse(line);
+	reverse(line.begin(), line.begin() + static_cast<string::difference_type>(n));
+	reverse(line.begin() + static_cast<string::difference_type>(n), line.end());
+}
+
+void
+exchange(string& line, size_t a, size_t b)
+{
+	swap(line.at(a), line.at(b));
+}
+
+void
+partner(string& line, char a, char b)
+{
+	auto iter_a = ranges::find(line, a);
+	auto iter_b = ranges::find(line, b);
+	iter_swap(iter_a, iter_b);
+}
+
+void
+dance(const vector<string>& instructions, string& line)
+{
+	for ( const auto& instr: instructions ) {
+		auto values = split(instr.substr(1));
+
+		switch ( instr.at(0) ) {
+		case 's':
+			spin(line, stoul(values.at(0)));
+			break;
+		case 'x':
+			exchange(line, stoul(values.at(0)), stoul(values.at(1)));
+			break;
+		case 'p':
+			partner(line, values.at(0).at(0), values.at(1).at(0));
+			break;
+		default:
+			throw runtime_error("inknown command");
+		}
+	}
+}
+
+void
+part1(const vector<string>& instructions, string line)
+{
+	dance(instructions, line);
+	cout << "Part1: " << line << '\n';
+}
+
+#if defined(WASTE_TIME)
+void
+part2_bf(const vector<string>& instructions, string line)
+{
+	for ( long round = 0; round != 1'000'000'000; ++round ) {
+		dance(instructions, line);
+	}
+
+	cout << "Part2-BF: " << line << '\n';
+}
+#endif
+
+void
+part2(const vector<string>& instructions, string line)
+{
+	map<string, size_t> seen;
+	vector<string>      history;
+
+	size_t cycle_start  = 0;
+	size_t cycle_length = 0;
+
+	for ( size_t round = 0;; ++round ) {
+		if ( seen.contains(line) ) {
+			cycle_start  = seen.at(line);
+			cycle_length = round - cycle_start;
+			break;
+		}
+
+		seen[line] = round;
+		history.emplace_back(line);
+
+		dance(instructions, line);
+	}
+
+	const size_t total_rounds = 1'000'000'000L;
+	const size_t remaining    = (total_rounds - cycle_start) % cycle_length;
+
+	cout << "Part2: " << history.at(cycle_start + remaining) << '\n';
+}
+
+void
+part2_alt(const vector<string>& instructions, const string& line)
+{
+	auto slow = line;
+	dance(instructions, slow);
+
+	auto fast = line;
+	dance(instructions, fast);
+	dance(instructions, fast);
+
+	// find cycle
+	while ( slow != fast ) {
+		dance(instructions, slow);
+		dance(instructions, fast);
+		dance(instructions, fast);
+	}
+
+	// find cycle length
+	size_t cycle_length = 1;
+	dance(instructions, slow);
+	while ( slow != fast ) {
+		dance(instructions, slow);
+		++cycle_length;
+	}
+
+	// process remaining rounds
+	const size_t total_rounds = 1'000'000'000L;
+	for ( auto remaining = total_rounds % cycle_length; remaining-- > 0; ) {
+		dance(instructions, slow);
+	}
+
+	cout << "Part2-Alt: " << slow << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+	auto instructions = read_line("data/day16.txt");
+	auto line         = "abcdefghijklmnop"s;
+
+	part1(instructions, line);
+	part2(instructions, line);
+	part2_alt(instructions, line);
+}
-- 
cgit v1.3