From 8c96639ec1f6757570510fc27f1c5fabece35eaf Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 16 Nov 2025 13:23:34 +0100
Subject: aoc 2018, days 1-11

---
 2018/src/day10.cpp | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 137 insertions(+)
 create mode 100644 2018/src/day10.cpp

(limited to '2018/src/day10.cpp')

diff --git a/2018/src/day10.cpp b/2018/src/day10.cpp
new file mode 100644
index 0000000..43de95c
--- /dev/null
+++ b/2018/src/day10.cpp
@@ -0,0 +1,137 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <regex>
+#include <set>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Point {
+	long x;
+	long y;
+	long vx;
+	long vy;
+};
+
+vector<Point>
+read_file(const filesystem::path& filename)
+{
+	ifstream file{ filename };
+
+	static const regex pattern{ R"(position=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>\s*velocity=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>)" };
+
+	vector<Point> data;
+	for ( string line; getline(file, line); ) {
+		smatch match;
+		if ( regex_match(line, match, pattern) ) {
+			auto x  = stol(match[1]);
+			auto y  = stol(match[2]);
+			auto vx = stol(match[3]);
+			auto vy = stol(match[4]);
+
+			data.emplace_back(x, y, vx, vy);
+		}
+	}
+
+	return data;
+}
+
+void
+get_bounding_box(const vector<Point>& points, long& min_x, long& min_y, long& max_x, long& max_y)
+{
+	min_x = numeric_limits<long>::max();
+	min_y = numeric_limits<long>::max();
+	max_x = numeric_limits<long>::min();
+	max_y = numeric_limits<long>::min();
+
+	for ( const auto& point: points ) {
+		min_x = min(min_x, point.x);
+		min_y = min(min_y, point.y);
+		max_x = max(max_x, point.x);
+		max_y = max(max_y, point.y);
+	}
+}
+
+long
+bounding_area(const vector<Point>& points)
+{
+	long min_x = 0;
+	long min_y = 0;
+	long max_x = 0;
+	long max_y = 0;
+	get_bounding_box(points, min_x, min_y, max_x, max_y);
+	return 1L * (max_x - min_x + 1) * (max_y - min_y + 1);
+}
+
+void
+update(vector<Point>& points)
+{
+	for ( auto& point: points ) {
+		point.x += point.vx;
+		point.y += point.vy;
+	}
+}
+
+tuple<int, vector<Point>>
+get_best(vector<Point> points)
+{
+	auto best_area = numeric_limits<long>::max();
+
+	vector<Point> best;
+	int           best_t = 0;
+
+	for ( int i = 0; i != 100'000; ++i ) {
+		update(points);
+
+		auto area = bounding_area(points);
+		if ( area < best_area ) {
+			best_area = area;
+			best      = points;
+			best_t    = i + 1;
+		}
+	}
+	return { best_t, best };
+}
+
+void
+print(const vector<Point>& points)
+{
+	set<tuple<long, long>> grid;
+	for ( const auto [x, y, vx, vy]: points ) {
+		grid.emplace(x, y);
+	}
+
+	long min_x = 0;
+	long min_y = 0;
+	long max_x = 0;
+	long max_y = 0;
+	get_bounding_box(points, min_x, min_y, max_x, max_y);
+
+	for ( long y = min_y; y <= max_y; ++y ) {
+		for ( long x = min_x; x <= max_x; ++x ) {
+			cout << (grid.contains({ x, y }) ? '#' : ' ');
+		}
+		cout << '\n';
+	}
+}
+
+void
+solve(const vector<Point>& points)
+{
+	auto [time, best_points] = get_best(points);
+	print(best_points);
+	cout << "Part 2: " << time << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+	auto data = read_file("data/day10.txt");
+	solve(data);
+}
-- 
cgit v1.3