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