175 lines
6.2 KiB
C++
175 lines
6.2 KiB
C++
#include <algorithm>
|
|
#include <fstream>
|
|
#include <iostream>
|
|
#include <set>
|
|
#include <sstream>
|
|
#include <vector>
|
|
#include <deque>
|
|
|
|
class Point : public std::pair<uint64_t, uint64_t> {
|
|
public:
|
|
Point(uint64_t x, uint64_t y) : std::pair<uint64_t, uint64_t>(x, y) {}
|
|
|
|
int getHeight(const std::vector<std::vector<int>> &heights) const {
|
|
return heights[first][second];
|
|
}
|
|
|
|
uint64_t getX() const {
|
|
return first;
|
|
}
|
|
uint64_t getY() const {
|
|
return second;
|
|
}
|
|
};
|
|
|
|
std::vector<std::vector<int>> getHeights(const std::string &file_name) {
|
|
std::vector<std::vector<int>> heights;
|
|
|
|
std::ifstream file(file_name);
|
|
std::string str;
|
|
while (std::getline(file, str)) {
|
|
heights.emplace_back();
|
|
for (auto &height : str) {
|
|
heights.back().push_back(height - '0');
|
|
}
|
|
}
|
|
return heights;
|
|
}
|
|
|
|
std::vector<Point> getLowPoints(const std::vector<std::vector<int>> &heights) {
|
|
std::vector<Point> low_points{};
|
|
for (size_t i = 1; i < heights.size() - 1; i++) {
|
|
for (size_t j = 1; j < heights[i].size() - 1; j++) {
|
|
auto &point = heights[i][j];
|
|
if (heights[i][j - 1] > point && heights[i][j + 1] > point &&
|
|
heights[i - 1][j] > point && heights[i + 1][j] > point) {
|
|
low_points.emplace_back(i, j);
|
|
}
|
|
}
|
|
}
|
|
for (size_t i = 1; i < heights[0].size() - 1; i++) {
|
|
if (heights[0][i - 1] > heights[0][i] &&
|
|
heights[0][i + 1] > heights[0][i] &&
|
|
heights[1][i] > heights[0][i]) {
|
|
low_points.emplace_back(0, i);
|
|
}
|
|
if (heights[heights.size() - 1][i - 1] >
|
|
heights[heights.size() - 1][i] &&
|
|
heights[heights.size() - 1][i + 1] >
|
|
heights[heights.size() - 1][i] &&
|
|
heights[heights.size() - 2][i] > heights[heights.size() - 1][i]) {
|
|
low_points.emplace_back(heights.size() - 1, i);
|
|
}
|
|
}
|
|
for (size_t i = 1; i < heights.size() - 1; i++) {
|
|
if (heights[i - 1][0] > heights[i][0] &&
|
|
heights[i + 1][0] > heights[i][0] &&
|
|
heights[i][1] > heights[i][0]) {
|
|
low_points.emplace_back(i, 0);
|
|
}
|
|
if (heights[i - 1][heights[0].size() - 1] >
|
|
heights[i][heights[0].size() - 1] &&
|
|
heights[i + 1][heights[0].size() - 1] >
|
|
heights[i][heights[0].size() - 1] &&
|
|
heights[i][heights[0].size() - 2] >
|
|
heights[i][heights[0].size() - 1]) {
|
|
low_points.emplace_back(i, heights[0].size() - 1);
|
|
}
|
|
}
|
|
if (heights[0][1] > heights[0][0] && heights[1][0] > heights[0][0]) {
|
|
low_points.emplace_back(0, 0);
|
|
}
|
|
if (heights[heights.size() - 1][1] > heights[heights.size() - 1][0] &&
|
|
heights[heights.size() - 2][0] > heights[heights.size() - 1][0]) {
|
|
low_points.emplace_back(heights.size() - 1, 0);
|
|
}
|
|
if (heights[0][heights[0].size() - 2] > heights[0][heights[0].size() - 1] &&
|
|
heights[1][heights[0].size() - 1] > heights[0][heights[0].size() - 1]) {
|
|
low_points.emplace_back(0, heights[0].size() - 1);
|
|
}
|
|
if (heights[heights.size() - 1][heights[0].size() - 2] >
|
|
heights[heights.size() - 1][heights[0].size() - 1] &&
|
|
heights[heights.size() - 2][heights[0].size() - 1] >
|
|
heights[heights.size() - 1][heights[0].size() - 1]) {
|
|
low_points.emplace_back(heights.size() - 1, heights[0].size() - 1);
|
|
}
|
|
return low_points;
|
|
}
|
|
|
|
std::vector<std::set<Point>>
|
|
getBasins(const std::vector<std::vector<int>> &heights,
|
|
const std::vector<Point> &low_points) {
|
|
std::vector<std::set<Point>> result{};
|
|
for (auto &point : low_points) {
|
|
std::set<Point> basin{};
|
|
std::deque<Point> basin_deque{};
|
|
basin_deque.push_back(point);
|
|
while (basin_deque.size() != 0) {
|
|
const auto &working_point = basin_deque.front();
|
|
basin.insert(working_point);
|
|
for (int i = -1; i < 2; i += 1) {
|
|
for (int j = -1; j < 2; j += 1) {
|
|
if ((i != 0 && j != 0) || (i == 0 && j == 0)) {
|
|
continue;
|
|
}
|
|
auto new_point = Point(working_point.getX() + i,
|
|
working_point.getY() + j);
|
|
if (new_point.getX() == (uint64_t)-1 ||
|
|
new_point.getX() >= heights.size()) {
|
|
continue;
|
|
}
|
|
if (new_point.getY() == (uint64_t)-1 ||
|
|
new_point.getY() >= heights[0].size()) {
|
|
continue;
|
|
}
|
|
if (basin.find(new_point) != basin.end()) {
|
|
continue;
|
|
}
|
|
if (new_point.getHeight(heights) == 9) {
|
|
continue;
|
|
}
|
|
basin_deque.push_back(new_point);
|
|
}
|
|
}
|
|
basin_deque.pop_front();
|
|
}
|
|
result.push_back(std::move(basin));
|
|
}
|
|
return result;
|
|
}
|
|
|
|
uint64_t part1(const std::vector<std::vector<int>> &heights,
|
|
const std::vector<Point> &low_points) {
|
|
uint64_t score = 0;
|
|
for (const auto &point : low_points) {
|
|
score += point.getHeight(heights) + 1;
|
|
}
|
|
return score;
|
|
}
|
|
|
|
uint64_t part2(const std::vector<std::vector<int>> &heights,
|
|
const std::vector<Point> &low_points) {
|
|
auto basins = getBasins(heights, low_points);
|
|
std::vector<uint64_t> sizes{};
|
|
for (auto &basin : basins) {
|
|
sizes.push_back(basin.size());
|
|
}
|
|
std::sort(sizes.begin(), sizes.end());
|
|
std::reverse(sizes.begin(), sizes.end());
|
|
return sizes[0] * sizes[1] * sizes[2];
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
if (argc < 2) {
|
|
std::cerr << "You must provide input file!" << std::endl;
|
|
return 1;
|
|
}
|
|
auto heights = getHeights(argv[1]);
|
|
auto low_points = getLowPoints(heights);
|
|
std::cout << "There sum of low points risks is \033[91;1m"
|
|
<< part1(heights, low_points) << "\033[0m." << std::endl;
|
|
std::cout << "There product of three largest basins is \033[91;1m"
|
|
<< part2(heights, low_points) << "\033[0m." << std::endl;
|
|
return 0;
|
|
}
|