From 3cdf7ef624fd6b6b2eb765af5a2001a1d143687c Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 14 Dec 2023 21:23:49 +0100
Subject: Lösung für Tag 14
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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

(limited to 'src')

diff --git a/src/day14.cpp b/src/day14.cpp
new file mode 100644
index 0000000..2b7a5b8
--- /dev/null
+++ b/src/day14.cpp
@@ -0,0 +1,243 @@
+#include <chrono>
+#include <cstddef>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <string>
+#include <vector>
+using namespace std;
+
+vector<string>
+read_file(string_view filename)
+{
+	fstream        input{ filename };
+	vector<string> data;
+
+	for ( string line; getline(input, line); ) {
+		data.emplace_back(line);
+	}
+
+	return data;
+}
+
+void
+part1()
+{
+	const auto lines = read_file("data/day14.txt");
+
+	auto start = chrono::steady_clock::now();
+
+	size_t sum = 0;
+	for ( size_t col = 0; col != lines[0].size(); ++col ) {
+		size_t counter = lines.size();
+
+		for ( size_t row = 0; row != lines.size(); ++row ) {
+			if ( lines[row][col] == 'O' ) {
+				sum += counter;
+				--counter;
+			}
+			if ( lines[row][col] == '#' ) {
+				counter = lines.size() - row - 1;
+			}
+		}
+	}
+
+	auto duration = chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - start).count();
+
+	cout << sum << " (" << duration << " μs)" << endl;
+}
+
+void
+tilt_north(vector<string>& lines)
+{
+	for ( size_t col = 0; col != lines[0].size(); ++col ) {
+		size_t row = 0;
+		while ( row != lines.size() ) {
+			size_t stones = 0;
+			size_t empty  = 0;
+
+			for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) {
+				if ( lines[idx][col] == '.' ) {
+					++empty;
+				}
+				if ( lines[idx][col] == 'O' ) {
+					++stones;
+				}
+			}
+
+			while ( stones-- != 0 ) {
+				lines[row++][col] = 'O';
+			}
+
+			while ( empty-- != 0 ) {
+				lines[row++][col] = '.';
+			}
+
+			while ( row != lines.size() && lines[row][col] == '#' ) {
+				++row;
+			}
+		}
+	}
+}
+
+void
+tilt_south(vector<string>& lines)
+{
+	for ( size_t col = 0; col != lines[0].size(); ++col ) {
+		size_t row = 0;
+		while ( row != lines.size() ) {
+			size_t stones = 0;
+			size_t empty  = 0;
+
+			for ( size_t idx = row; idx != lines.size() && lines[idx][col] != '#'; ++idx ) {
+				if ( lines[idx][col] == '.' ) {
+					++empty;
+				}
+				if ( lines[idx][col] == 'O' ) {
+					++stones;
+				}
+			}
+
+			while ( empty-- != 0 ) {
+				lines[row++][col] = '.';
+			}
+
+			while ( stones-- != 0 ) {
+				lines[row++][col] = 'O';
+			}
+
+			while ( row != lines.size() && lines[row][col] == '#' ) {
+				++row;
+			}
+		}
+	}
+}
+
+void
+tilt_west(vector<string>& lines)
+{
+	for ( size_t row = 0; row != lines.size(); ++row ) {
+		size_t col = 0;
+		while ( col != lines[0].size() ) {
+			size_t stones = 0;
+			size_t empty  = 0;
+
+			for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) {
+				if ( lines[row][idx] == '.' ) {
+					++empty;
+				}
+				if ( lines[row][idx] == 'O' ) {
+					++stones;
+				}
+			}
+
+			while ( stones-- != 0 ) {
+				lines[row][col++] = 'O';
+			}
+
+			while ( empty-- != 0 ) {
+				lines[row][col++] = '.';
+			}
+
+			while ( col != lines[0].size() && lines[row][col] == '#' ) {
+				++col;
+			}
+		}
+	}
+}
+
+void
+tilt_east(vector<string>& lines)
+{
+	for ( size_t row = 0; row != lines.size(); ++row ) {
+		size_t col = 0;
+		while ( col != lines[0].size() ) {
+			size_t stones = 0;
+			size_t empty  = 0;
+
+			for ( size_t idx = col; idx != lines[0].size() && lines[row][idx] != '#'; ++idx ) {
+				if ( lines[row][idx] == '.' ) {
+					++empty;
+				}
+				if ( lines[row][idx] == 'O' ) {
+					++stones;
+				}
+			}
+
+			while ( empty-- != 0 ) {
+				lines[row][col++] = '.';
+			}
+
+			while ( stones-- != 0 ) {
+				lines[row][col++] = 'O';
+			}
+
+			while ( col != lines[0].size() && lines[row][col] == '#' ) {
+				++col;
+			}
+		}
+	}
+}
+
+void
+tilt(vector<string>& lines)
+{
+	tilt_north(lines);
+	tilt_west(lines);
+	tilt_south(lines);
+	tilt_east(lines);
+}
+
+size_t
+calc(const vector<string>& lines)
+{
+	size_t sum     = 0;
+	size_t counter = lines.size();
+	for ( const auto& line: lines ) {
+		sum += counter * static_cast<size_t>(count_if(line.begin(), line.end(), [](char chr) { return chr == 'O'; }));
+		--counter;
+	}
+	return sum;
+}
+
+void
+part2()
+{
+	auto lines = read_file("data/day14.txt");
+
+	auto                      start = chrono::steady_clock::now();
+	map<vector<string>, long> cache;
+
+	const long dest = 1'000'000'000;
+
+	for ( long index = 0; true; ++index ) {
+		auto iter = cache.find(lines);
+		if ( iter != cache.end() ) {
+			auto offset       = iter->second;
+			auto cycle_length = index - offset;
+
+			auto moves_required = (dest - offset) % cycle_length;
+
+			while ( moves_required-- != 0 ) {
+				tilt(lines);
+			}
+
+			auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
+
+			cout << calc(lines) << " (" << duration << " ms)" << endl;
+			break;
+		}
+		else {
+			cache[lines] = index;
+		}
+
+		tilt(lines);
+	}
+}
+
+int
+main()
+{
+	part1();
+	part2();
+}
-- 
cgit v1.3