From 154fdf1541545d3a5fe94c564941f8092937a504 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 16 Dec 2023 15:07:56 +0100
Subject: Lösungen für Tag 16
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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

(limited to 'src/day16.cpp')

diff --git a/src/day16.cpp b/src/day16.cpp
new file mode 100644
index 0000000..68defad
--- /dev/null
+++ b/src/day16.cpp
@@ -0,0 +1,139 @@
+#include <array>
+#include <chrono>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#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;
+}
+
+const unsigned DIR_UP    = 0;
+const unsigned DIR_RIGHT = 1;
+const unsigned DIR_DOWN  = 2;
+const unsigned DIR_LEFT  = 3;
+
+size_t
+solve(const vector<string>& lines, tuple<size_t, size_t, unsigned int> start)
+{
+	static const array<tuple<size_t, size_t>, 4> movement{
+		make_tuple(0, -1),
+		make_tuple(1, 0),
+		make_tuple(0, 1),
+		make_tuple(-1, 0),
+	};
+
+	map<tuple<size_t, size_t, unsigned int>, bool> visited;
+
+	queue<tuple<size_t, size_t, unsigned int>> positions;
+
+	positions.emplace(start);
+
+	while ( !positions.empty() ) {
+		auto row = get<0>(positions.front());
+		auto col = get<1>(positions.front());
+		auto dir = get<2>(positions.front());
+		positions.pop();
+
+		while ( true ) {
+			col += get<0>(movement[dir]); // NOLINT
+			row += get<1>(movement[dir]); // NOLINT
+
+			if ( row >= lines.size() || col >= lines[0].size() ) {
+				break;
+			}
+
+			if ( visited[{ row, col, dir }] ) {
+				break;
+			}
+
+			visited[{ row, col, dir }] = true;
+
+			const auto chr = lines[row][col];
+
+			if ( chr == '|' && (dir == DIR_LEFT || dir == DIR_RIGHT) ) {
+				dir = (dir + 1) % 4;
+				positions.emplace(row, col, (dir + 2) % 4);
+			}
+			else if ( chr == '-' && (dir == DIR_UP || dir == DIR_DOWN) ) {
+				dir = (dir + 1) % 4;
+				positions.emplace(row, col, (dir + 2) % 4);
+			}
+			else if ( chr == '/' && (dir == DIR_LEFT || dir == DIR_RIGHT) ) {
+				dir = (dir + 3) % 4;
+			}
+			else if ( chr == '/' && (dir == DIR_UP || dir == DIR_DOWN) ) {
+				dir = (dir + 1) % 4;
+			}
+			else if ( chr == '\\' && (dir == DIR_LEFT || dir == DIR_RIGHT) ) {
+				dir = (dir + 1) % 4;
+			}
+			else if ( chr == '\\' && (dir == DIR_UP || dir == DIR_DOWN) ) {
+				dir = (dir + 3) % 4;
+			}
+		}
+	}
+
+	set<tuple<size_t, size_t>> foo;
+	for (const auto& bar: visited) {
+		foo.emplace(get<0>(bar.first), get<1>(bar.first));
+	}
+	return foo.size();
+}
+
+void
+part1(const vector<string>& lines)
+{
+	auto start = chrono::steady_clock::now();
+
+	auto sum = solve(lines, { 0, -1, DIR_RIGHT });
+
+	auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
+
+	cout << sum << " (" << duration << "ms)" << endl;
+}
+
+void
+part2(const vector<string>& lines)
+{
+	const auto rows = lines.size();
+	const auto cols = lines[0].size();
+
+	auto start = chrono::steady_clock::now();
+
+	size_t sum = 0;
+	for ( size_t row = 0; row != rows; ++row ) {
+		sum = max(sum, solve(lines, { row, -1, DIR_RIGHT }));
+		sum = max(sum, solve(lines, { row, cols, DIR_LEFT }));
+	}
+	for ( size_t col = 0; col != cols; ++col ) {
+		sum = max(sum, solve(lines, { -1, col, DIR_DOWN }));
+		sum = max(sum, solve(lines, { rows, col, DIR_UP }));
+	}
+
+	auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
+
+	cout << sum << " (" << duration << "ms)" << endl;
+}
+
+int
+main()
+{
+	const auto lines = read_file("data/day16.txt");
+	part1(lines);
+	part2(lines);
+}
-- 
cgit v1.3