1 files changed, 137 insertions, 0 deletions

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