157 lines
4.3 KiB
C++
157 lines
4.3 KiB
C++
#include <algorithm>
|
|
#include <deque>
|
|
#include <fstream>
|
|
#include <iostream>
|
|
#include <sstream>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
using Point = std::pair<uint64_t, uint64_t>;
|
|
|
|
class Position {
|
|
public:
|
|
Position(uint64_t value) : _value(value) {}
|
|
bool updateDist(uint64_t from_dist) {
|
|
auto new_dist = from_dist + _value;
|
|
if (new_dist < _dist) {
|
|
_dist = new_dist;
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
uint64_t getDist() {
|
|
return _dist;
|
|
}
|
|
|
|
void setDist(uint64_t dist) {
|
|
_dist = dist;
|
|
}
|
|
|
|
uint64_t getValue() {
|
|
return _value;
|
|
}
|
|
|
|
private:
|
|
uint64_t _dist = -1;
|
|
uint64_t _value = 0;
|
|
};
|
|
|
|
std::vector<std::vector<Position>> getMap(const std::string &file_name,
|
|
bool growing = false) {
|
|
std::vector<std::vector<Position>> map;
|
|
|
|
std::ifstream file(file_name);
|
|
std::string str;
|
|
while (std::getline(file, str)) {
|
|
map.emplace_back();
|
|
for (auto &c : str) {
|
|
map.back().emplace_back(c - '0');
|
|
}
|
|
}
|
|
map[0][0].setDist(0);
|
|
auto original_height = map.size();
|
|
auto original_width = map[0].size();
|
|
if (growing) {
|
|
for (auto &line : map) {
|
|
for (int i = 1; i < 5; i++) {
|
|
for (size_t j = 0; j < original_width; j++) {
|
|
auto new_val = line[j].getValue() + i;
|
|
if (new_val > 9) {
|
|
new_val -= 9;
|
|
}
|
|
line.emplace_back(new_val);
|
|
}
|
|
}
|
|
}
|
|
for (int i = 1; i < 5; i++) {
|
|
for (size_t j = 0; j < original_height; j++) {
|
|
map.emplace_back();
|
|
for (auto &position : map[j]) {
|
|
auto new_val = position.getValue() + i;
|
|
if (new_val > 9) {
|
|
new_val -= 9;
|
|
}
|
|
map.back().emplace_back(new_val);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return map;
|
|
}
|
|
|
|
std::vector<Point> getPointsNoDiag(const Point &point, size_t max_x,
|
|
size_t max_y) {
|
|
std::vector<Point> result{};
|
|
if (point.first > 0) {
|
|
result.emplace_back(point.first - 1, point.second);
|
|
}
|
|
if (point.first < max_x) {
|
|
result.emplace_back(point.first + 1, point.second);
|
|
}
|
|
if (point.second > 0) {
|
|
result.emplace_back(point.first, point.second - 1);
|
|
}
|
|
if (point.second < max_y) {
|
|
result.emplace_back(point.first, point.second + 1);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
Position &pointToMap(std::vector<std::vector<Position>> &map,
|
|
const Point &point) {
|
|
return map[point.second][point.first];
|
|
}
|
|
|
|
uint64_t findSafestPath(std::vector<std::vector<Position>> &map) {
|
|
std::deque<Point> to_process = { { 0, 0 } };
|
|
while (!to_process.empty()) {
|
|
auto point = to_process.front();
|
|
auto &map_entry = pointToMap(map, point);
|
|
auto new_points =
|
|
getPointsNoDiag(point, map[0].size() - 1, map.size() - 1);
|
|
for (auto &new_point : new_points) {
|
|
auto &new_map = pointToMap(map, new_point);
|
|
if (new_map.updateDist(map_entry.getDist())) {
|
|
to_process.push_back(new_point);
|
|
}
|
|
}
|
|
to_process.pop_front();
|
|
}
|
|
return map.back().back().getDist();
|
|
}
|
|
|
|
uint64_t part1(const std::string &map_path) {
|
|
auto map = getMap(map_path);
|
|
return findSafestPath(map);
|
|
}
|
|
|
|
uint64_t part2(const std::string &map_path) {
|
|
auto map = getMap(map_path, true);
|
|
return findSafestPath(map);
|
|
}
|
|
|
|
void printMap(std::vector<std::vector<Position>> &map) {
|
|
for (auto &line : map) {
|
|
for (auto &pos : line) {
|
|
std::cout << pos.getValue();
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
if (argc < 2) {
|
|
std::cerr << "You must provide input file!" << std::endl;
|
|
return 1;
|
|
}
|
|
std::cout << "The least risky path has a risk of \033[91;1m"
|
|
<< part1(argv[1]) << "\033[0m." << std::endl;
|
|
std::cout
|
|
<< "The least risky path in the entire cove has a risk of \033[91;1m"
|
|
<< part2(argv[1]) << "\033[0m." << std::endl;
|
|
return 0;
|
|
}
|