aoc 2018, days 1-11

1 files changed, 152 insertions, 0 deletions

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);
+}