1 files changed, 143 insertions, 0 deletions

diff --git a/2018/src/day11.cpp b/2018/src/day11.cpp
new file mode 100644
index 0000000..1f8f9e2
--- /dev/null
+++ b/2018/src/day11.cpp
@@ -0,0 +1,143 @@
+#include <iostream>
+#include <map>
+
+using namespace std;
+
+namespace {
+
+const int WIDTH  = 300;
+const int HEIGHT = 300;
+
+using Grid = map<tuple<int, int>, int>;
+
+int
+power_level(int x, int y, int serial)
+{
+        auto rack_id = x + 10;
+        auto level   = rack_id * y;
+        level += serial;
+        level *= rack_id;
+        level /= 100;
+        level %= 10;
+        level -= 5;
+        return level;
+}
+
+Grid
+build_grid(int serial)
+{
+        Grid grid;
+        for ( int x = 1; x <= WIDTH; ++x ) {
+                for ( int y = 1; y <= HEIGHT; ++y ) {
+                        grid[{ x, y }] = power_level(x, y, serial);
+                }
+        }
+        return grid;
+}
+
+int
+sum3x3(const Grid& grid, int x, int y)
+{
+        auto sum = 0;
+        for ( int dx = 0; dx != 3; ++dx ) {
+                for ( int dy = 0; dy != 3; ++dy ) {
+                        sum += grid.at({ x + dx, y + dy });
+                }
+        }
+        return sum;
+}
+
+void
+part1(const int serial)
+{
+        auto grid = build_grid(serial);
+
+        auto best_sum = numeric_limits<int>::min();
+        auto best_x   = 0;
+        auto best_y   = 0;
+
+        for ( int x = 1; x <= WIDTH - 2; ++x ) {
+                for ( int y = 1; y <= HEIGHT - 2; ++y ) {
+                        if ( auto sum = sum3x3(grid, x, y); sum > best_sum ) {
+                                best_sum = sum;
+                                best_x   = x;
+                                best_y   = y;
+                        }
+                }
+        }
+
+        cout << "Part 1: " << best_x << ',' << best_y << '\n';
+}
+
+Grid
+pre_process(const Grid& grid)
+{
+        Grid sat;
+
+        for ( int y = 1; y <= HEIGHT; ++y ) {
+                for ( int x = 1; x <= WIDTH; ++x ) {
+                        const auto a = grid.at({ x, y });
+                        const auto b = (x > 1) ? sat.at({ x - 1, y }) : 0;
+                        const auto c = (y > 1) ? sat.at({ x, y - 1 }) : 0;
+                        const auto d = (x > 1 && y > 1) ? sat.at({ x - 1, y - 1 }) : 0;
+
+                        sat[{ x, y }] = a + b + c - d;
+                }
+        }
+
+        return sat;
+}
+
+int
+get_safe(const Grid& grid, int x, int y)
+{
+        return (x < 1 || y < 1) ? 0 : grid.at({ x, y });
+}
+
+int
+square_sum(const Grid& grid, int x, int y, int s)
+{
+        int x2 = x + s - 1;
+        int y2 = y + s - 1;
+
+        return get_safe(grid, x2, y2) - get_safe(grid, x - 1, y2) - get_safe(grid, x2, y - 1) + get_safe(grid, x - 1, y - 1);
+}
+
+void
+part2(const int serial)
+{
+        static const int MAX_SIZE = 100;
+
+        auto grid = pre_process(build_grid(serial));
+
+        auto best_sum = numeric_limits<int>::min();
+        auto best_x   = 0;
+        auto best_y   = 0;
+        auto best_s   = 0;
+
+        for ( int s = 1; s <= MAX_SIZE; ++s ) {
+                for ( int x = 1; x <= WIDTH - s + 1; ++x ) {
+                        for ( int y = 1; y <= HEIGHT - s + 1; ++y ) {
+                                if ( auto sum = square_sum(grid, x, y, s); sum > best_sum ) {
+                                        best_sum = sum;
+                                        best_x   = x;
+                                        best_y   = y;
+                                        best_s   = s;
+                                }
+                        }
+                }
+        }
+
+        cout << "Part 2: " << best_x << ',' << best_y << "," << best_s << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        static const int SERIAL = 7989;
+
+        part1(SERIAL);
+        part2(SERIAL);
+}