[cpp] Day 12

Viewer

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <fstream>
  5. #include <algorithm>
  6. #include <queue>
  7. #include <ostream>
  8. #include <ranges>
  9.  
  10. struct location {
  11.     int x{-1};
  12.     int y{-1};
  13.     int cost{0};
  14.  
  15.     bool operator==(location const& rhs) const { return x == rhs.x and y == rhs.y; }
  16.     bool operator>(location const& rhs) const { return cost > rhs.cost; };
  17. };
  18.  
  19. static std::ostream& operator<<(std::ostream& out, location const& p) {
  20.     out << "(" << p.x << ", " << p.y << ", " << p.cost << ")";
  21.     return out;
  22. }
  23.  
  24. static std::vector<location> get_neighbours(int currentX, int currentY, std::vector<std::string> const& height_map) {
  25.     std::vector<location> neighbours{};
  26.  
  27.     int left = currentX - 1;
  28.     int right = currentX + 1;
  29.     int up = currentY - 1;
  30.     int down = currentY + 1;
  31.  
  32.     char current_height = height_map[currentY][currentX];
  33.  
  34.     if(left >= 0 and height_map[currentY][left] <= (current_height + 1)) neighbours.push_back({.x = left, .y = currentY});
  35.     if(up >= 0   and height_map[up][currentX]   <= (current_height + 1)) neighbours.push_back({.x = currentX, .y = up});
  36.  
  37.     if(right < height_map[0].size() and height_map[currentY][right]  <= (current_height + 1)) neighbours.push_back({.x = right, .y = currentY});
  38.     if(down < height_map.size()     and height_map[down][currentX]   <= (current_height + 1)) neighbours.push_back({.x = currentX, .y = down});
  39.  
  40.     return neighbours;
  41. }
  42.  
  43. static void part_one(location const& start,  location const& end, std::vector<std::string> const& height_map) {
  44.     std::vector<location> visited_locations{};
  45.     std::vector<location> already_pushed{};
  46.  
  47.     std::priority_queue<location, std::vector<location>, std::greater<location>> to_visit;
  48.     to_visit.push(start);
  49.  
  50.     auto already_visited_comp = [](location const& loc){ return [&loc](location p){ return loc.x == p.x and loc.y == p.y; }; };
  51.     auto already_pushed_comp = [](location const& loc){ return [&loc](location p){  return loc.x == p.x and loc.y == p.y; }; };
  52.  
  53.     while(not to_visit.empty()) {
  54.         auto current_location = to_visit.top();
  55.         to_visit.pop();
  56.  
  57.         visited_locations.push_back(current_location);
  58.         auto possible_neighbours = get_neighbours(current_location.x, current_location.y, height_map);
  59.  
  60.         // find good candidate
  61.         for( location loc : possible_neighbours) {
  62.             // fist check if we already visited this location or if it was already pushed
  63.             if(auto ptr = std::ranges::find_if(visited_locations, already_visited_comp(loc)); ptr != visited_locations.end()) continue;
  64.             if(auto ptr = std::ranges::find_if(already_pushed, already_pushed_comp(loc)); ptr != already_pushed.end()) continue;
  65.  
  66.             loc.cost = current_location.cost + 1;
  67.             to_visit.push(loc);
  68.             already_pushed.push_back(loc);
  69.         }
  70.     }
  71.  
  72.     auto iter = std::ranges::find_if(visited_locations, [&end](location const& loc){ return loc == end; });
  73.     if(iter != visited_locations.end())
  74.         std::cout << *iter << std::endl;
  75. }
  76.  
  77. static void part_two(location const& end, std::vector<std::string> const& height_map) { 
  78.     std::vector<location> locations{};
  79.  
  80.     // get all locations with elevation a
  81.     for(int row{0}; row < height_map.size(); row++) {
  82.         for(int col{0}; col < height_map[0].size(); col++) {
  83.             if(height_map[row][col] == 'a') {
  84.               locations.push_back({.x = col, .y = row, .cost = 0});
  85.             }
  86.         }
  87.     }
  88.  
  89.     // do stupid stuff
  90.     for(location const& start : locations) {
  91.       part_one(start, end, height_map);
  92.     }
  93. }
  94.  
  95. int main() {
  96.     std::ifstream file("input-final.txt");
  97.  
  98.     if(file.fail()) return 1;
  99.  
  100.     std::vector<std::string> height_map{};
  101.  
  102.     std::string line;
  103.     location start;
  104.     location end;
  105.  
  106.     while(std::getline(file, line)) {
  107.         height_map.push_back(line);
  108.  
  109.         if(std::size_t pos = line.find_first_of('S'); pos != std::string::npos) {
  110.             start = {.x = pos, .y = height_map.size() - 1};
  111.             height_map.back()[pos] = 'a';
  112.         }
  113.  
  114.         if(std::size_t pos = line.find_first_of('E'); pos != std::string::npos) {
  115.             end = {.x = pos, .y = height_map.size() - 1};
  116.             height_map.back()[pos] = 'z';
  117.         }
  118.     }
  119.  
  120.     part_one(start, end, height_map);
  121.     part_two(end, height_map);
  122. }
  123.  

Editor

You can edit this paste and save as new:


File Description
  • Day 12
  • Paste Code
  • 28 Dec-2022
  • 4.35 Kb
You can Share it: