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