[cpp] Day 12
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
- #include <iostream>
- #include <vector>
- #include <string>
- #include <fstream>
- #include <algorithm>
- #include <queue>
- #include <ostream>
- #include <ranges>
- struct location {
- int x{-1};
- int y{-1};
- int cost{0};
- bool operator==(location const& rhs) const { return x == rhs.x and y == rhs.y; }
- bool operator>(location const& rhs) const { return cost > rhs.cost; };
- };
- static std::ostream& operator<<(std::ostream& out, location const& p) {
- out << "(" << p.x << ", " << p.y << ", " << p.cost << ")";
- return out;
- }
- static std::vector<location> get_neighbours(int currentX, int currentY, std::vector<std::string> const& height_map) {
- std::vector<location> neighbours{};
- int left = currentX - 1;
- int right = currentX + 1;
- int up = currentY - 1;
- int down = currentY + 1;
- char current_height = height_map[currentY][currentX];
- if(left >= 0 and height_map[currentY][left] <= (current_height + 1)) neighbours.push_back({.x = left, .y = currentY});
- if(up >= 0 and height_map[up][currentX] <= (current_height + 1)) neighbours.push_back({.x = currentX, .y = up});
- if(right < height_map[0].size() and height_map[currentY][right] <= (current_height + 1)) neighbours.push_back({.x = right, .y = currentY});
- if(down < height_map.size() and height_map[down][currentX] <= (current_height + 1)) neighbours.push_back({.x = currentX, .y = down});
- return neighbours;
- }
- static void part_one(location const& start, location const& end, std::vector<std::string> const& height_map) {
- std::vector<location> visited_locations{};
- std::vector<location> already_pushed{};
- std::priority_queue<location, std::vector<location>, std::greater<location>> to_visit;
- to_visit.push(start);
- auto already_visited_comp = [](location const& loc){ return [&loc](location p){ return loc.x == p.x and loc.y == p.y; }; };
- auto already_pushed_comp = [](location const& loc){ return [&loc](location p){ return loc.x == p.x and loc.y == p.y; }; };
- while(not to_visit.empty()) {
- auto current_location = to_visit.top();
- to_visit.pop();
- visited_locations.push_back(current_location);
- auto possible_neighbours = get_neighbours(current_location.x, current_location.y, height_map);
- // find good candidate
- for( location loc : possible_neighbours) {
- // fist check if we already visited this location or if it was already pushed
- if(auto ptr = std::ranges::find_if(visited_locations, already_visited_comp(loc)); ptr != visited_locations.end()) continue;
- if(auto ptr = std::ranges::find_if(already_pushed, already_pushed_comp(loc)); ptr != already_pushed.end()) continue;
- loc.cost = current_location.cost + 1;
- to_visit.push(loc);
- already_pushed.push_back(loc);
- }
- }
- auto iter = std::ranges::find_if(visited_locations, [&end](location const& loc){ return loc == end; });
- if(iter != visited_locations.end())
- std::cout << *iter << std::endl;
- }
- static void part_two(location const& end, std::vector<std::string> const& height_map) {
- std::vector<location> locations{};
- // get all locations with elevation a
- for(int row{0}; row < height_map.size(); row++) {
- for(int col{0}; col < height_map[0].size(); col++) {
- if(height_map[row][col] == 'a') {
- locations.push_back({.x = col, .y = row, .cost = 0});
- }
- }
- }
- // do stupid stuff
- for(location const& start : locations) {
- part_one(start, end, height_map);
- }
- }
- int main() {
- std::ifstream file("input-final.txt");
- if(file.fail()) return 1;
- std::vector<std::string> height_map{};
- std::string line;
- location start;
- location end;
- while(std::getline(file, line)) {
- height_map.push_back(line);
- if(std::size_t pos = line.find_first_of('S'); pos != std::string::npos) {
- start = {.x = pos, .y = height_map.size() - 1};
- height_map.back()[pos] = 'a';
- }
- if(std::size_t pos = line.find_first_of('E'); pos != std::string::npos) {
- end = {.x = pos, .y = height_map.size() - 1};
- height_map.back()[pos] = 'z';
- }
- }
- part_one(start, end, height_map);
- part_two(end, height_map);
- }
Editor
You can edit this paste and save as new: