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/day06.cpp | 152 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 152 insertions(+)
 create mode 100644 2018/src/day06.cpp

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

diff --git a/2018/src/day06.cpp b/2018/src/day06.cpp
new file mode 100644
index 0000000..8701cbe
--- /dev/null
+++ b/2018/src/day06.cpp
@@ -0,0 +1,152 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <tuple>
+
+using namespace std;
+
+namespace {
+
+using Point = tuple<int, int>;
+
+set<Point>
+read_file(const filesystem::path& filename)
+{
+	ifstream   file{ filename };
+	set<Point> points;
+
+	int  x{};
+	int  y{};
+	char sep{};
+
+	while ( file >> x >> sep >> y ) {
+		points.insert({ x, y });
+	}
+
+	return points;
+}
+
+void
+getBoundingBox(const set<Point>& points, Point& topLeft, Point& bottomRight)
+{
+	auto minX = numeric_limits<int>::max();
+	auto minY = numeric_limits<int>::max();
+	auto maxX = numeric_limits<int>::min();
+	auto maxY = numeric_limits<int>::min();
+
+	for ( const auto [x, y]: points ) {
+		minX = min(minX, x);
+		minY = min(minY, y);
+		maxX = max(maxX, x);
+		maxY = max(maxY, y);
+	}
+
+	topLeft     = { minX, minY };
+	bottomRight = { maxX, maxY };
+}
+
+int
+manhattanDistance(const Point& lhs, const Point& rhs)
+{
+	int distance = abs(get<0>(lhs) - get<0>(rhs)) + abs(get<1>(lhs) - get<1>(rhs));
+
+	return distance;
+}
+
+void
+part1(const set<Point>& points)
+{
+	Point topLeft{};
+	Point bottomRight{};
+	getBoundingBox(points, topLeft, bottomRight);
+
+	const auto [minX, minY] = topLeft;
+	const auto [maxX, maxY] = bottomRight;
+
+	map<Point, int> areaCount;
+	set<Point>      infinite;
+
+	static const int offset = 1;
+
+	for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
+		for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
+			int   bestDistance = numeric_limits<int>::max();
+			Point bestPoint{};
+			bool  tie = false;
+
+			for ( const auto& point: points ) {
+				int distance = manhattanDistance(point, { posX, posY });
+				if ( distance < bestDistance ) {
+					bestDistance = distance;
+					bestPoint    = point;
+					tie          = false;
+				}
+				else if ( distance == bestDistance ) {
+					tie = true;
+				}
+			}
+
+			if ( !tie ) {
+				areaCount[bestPoint]++;
+
+				if ( posX < minX || posX > maxX || posY < minY || posY > maxY ) {
+					infinite.insert(bestPoint);
+				}
+			}
+		}
+	}
+
+	int maxSize = 0;
+	for ( const auto& [point, size]: areaCount ) {
+		if ( infinite.contains(point) ) {
+			continue;
+		}
+		maxSize = max(maxSize, size);
+	}
+
+	cout << "Part 1: " << maxSize << '\n';
+}
+
+void
+part2(const set<Point>& points, const int threshold)
+{
+	Point topLeft{};
+	Point bottomRight{};
+	getBoundingBox(points, topLeft, bottomRight);
+
+	const auto [minX, minY] = topLeft;
+	const auto [maxX, maxY] = bottomRight;
+
+	static const int offset = 100;
+
+	unsigned int regionSize = 0;
+
+	for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
+		for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
+			int sum = 0;
+
+			for ( const auto& point: points ) {
+				int distance = manhattanDistance(point, { posX, posY });
+				sum += distance;
+			}
+
+			if ( sum < threshold ) {
+				++regionSize;
+			}
+		}
+	}
+
+	cout << "Part 2: " << regionSize << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+	auto points = read_file("data/day06.txt");
+	part1(points);
+	part2(points, 10000);
+}
-- 
cgit v1.3