From 9a64f1b065060968f0ba0e72f37fba7d37aa16d2 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 18 Dec 2024 17:25:07 +0100
Subject: aoc 2024, day 18, part 2, binary search

---
 2024/src/day18-opti.cpp | 115 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)
 create mode 100644 2024/src/day18-opti.cpp

(limited to '2024/src')

diff --git a/2024/src/day18-opti.cpp b/2024/src/day18-opti.cpp
new file mode 100644
index 0000000..67374fe
--- /dev/null
+++ b/2024/src/day18-opti.cpp
@@ -0,0 +1,115 @@
+#include <fstream>
+#include <iostream>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <string>
+#include <tuple>
+#include <vector>
+using namespace std;
+
+using pos_type = tuple<long, long>;
+
+vector<pos_type>
+read_file(string_view filename)
+{
+	fstream          input{ filename };
+	vector<pos_type> data;
+
+	long lhs = 0;
+	long rhs = 0;
+	char chr = 0;
+
+	while ( input >> lhs >> chr >> rhs ) {
+		data.emplace_back(lhs, rhs);
+	}
+	return data;
+}
+
+optional<long>
+bfs(const vector<pos_type>& data, long size)
+{
+	set<pos_type> stones{ data.begin(), data.end() };
+
+	set<pos_type> seen;
+
+	// x, y, distance
+	queue<tuple<pos_type, long>> queue;
+	queue.push({ { 0, 0 }, 0 });
+
+	while ( !queue.empty() ) {
+		const auto& [pos, distance] = queue.front();
+		queue.pop();
+
+		const auto [x, y] = pos;
+
+		if ( x == size && y == size ) {
+			return distance;
+		}
+
+		if ( x < 0 || y < 0 || x > size || y > size ) {
+			continue;
+		}
+
+		if ( stones.contains(pos) ) {
+			continue;
+		}
+
+		if ( seen.contains(pos) ) {
+			continue;
+		}
+		seen.insert(pos);
+
+		for ( const auto& [nx, ny]: vector<pos_type>{ { x - 1, y }, { x + 1, y }, { x, y - 1 }, { x, y + 1 } } ) {
+			queue.push({ { nx, ny }, distance + 1 });
+		}
+	}
+	return nullopt;
+}
+
+void
+part1(const vector<pos_type>& data, long size)
+{
+	if ( auto result = bfs(data, size) ) {
+		cout << *result << endl;
+	}
+}
+
+void
+part2(const vector<pos_type>& data, long size)
+{
+	size_t lhs = 0;
+	size_t rhs = data.size() - 1;
+
+	while ( lhs < rhs ) {
+		auto mid = lhs + (rhs - lhs) / 2;
+
+		if ( bfs({ data.begin(), data.begin() + ptrdiff_t(mid + 1) }, size) ) {
+			lhs = mid + 1;
+		}
+		else {
+			rhs = mid;
+		}
+	}
+
+	const auto& [x, y] = data[lhs];
+	cout << x << "," << y << endl;
+}
+
+int
+main()
+{
+#if 0
+	const auto data = read_file("data/day18-sample1.txt");
+	const long size = 6;
+
+	part1({ data.begin(), data.begin() + 12 }, size);
+	part2(data, size);
+#else
+	const auto data = read_file("data/day18.txt");
+	const long size = 70;
+
+	part1({ data.begin(), data.begin() + 1024 }, size);
+	part2(data, size);
+#endif
+}
-- 
cgit v1.3