Line data    Source code

       1              : #include "PuzzleImpl.h"
       2              : 
       3              : #include "Grid2d.h"
       4              : #include "LinewiseInput.h"
       5              : 
       6              : #include <algorithm>
       7              : #include <string>
       8              : #include <string_view>
       9              : #include <vector>
      10              : 
      11              : using namespace std::literals;
      12              : 
      13              : namespace {
      14              : 
      15            2 : std::vector<Vec2<int>> findPath(Grid2d<char> const &map) {
      16            2 :   static std::array<Vec2<int>, 4u> constexpr dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      17              : 
      18            2 :   std::vector<Vec2<int>> path;
      19              : 
      20            2 :   Vec2<int> pos = map.find('S');
      21            2 :   Vec2<int> predPos{-1, -1};
      22            2 :   path.push_back(pos);
      23              : 
      24        18826 :   while (map[pos] != 'E') {
      25        47348 :     for (auto d : dirs) {
      26        47348 :       auto n = pos + d;
      27        47348 :       if (n != predPos && map[n] != '#') {
      28        18824 :         predPos = pos;
      29        18824 :         pos = n;
      30        18824 :         path.push_back(pos);
      31        18824 :         break;
      32        18824 :       }
      33        47348 :     }
      34        18824 :   }
      35              : 
      36            2 :   return path;
      37            2 : }
      38              : 
      39              : struct PosIdx {
      40              :   Vec2<int> pos;
      41              :   int idx;
      42              : };
      43              : 
      44            2 : size_t countCheats(Grid2d<char> const &map, int const radius, int const minSaving) {
      45            2 :   std::vector<Vec2<int>> path = findPath(map);
      46              : 
      47            2 :   using ParcelGrid = Grid2d<std::vector<PosIdx>>;
      48            2 :   Vec2<int> constexpr parcelSize{5, 5};
      49            2 :   Vec2<int> parcelRadius = (radius + (parcelSize - 1)) / parcelSize;
      50            2 :   ParcelGrid parcels((map.size() + (parcelSize - 1)) / parcelSize, {},
      51            2 :                      std::max(parcelRadius.x(), parcelRadius.y()));
      52              : 
      53        18828 :   for (int i = 0; i < std::ssize(path); ++i)
      54        18826 :     parcels[path[i] / parcelSize].emplace_back(path[i], i);
      55              : 
      56            2 :   size_t ctr = 0;
      57              : 
      58           60 :   for (ParcelGrid::Coord p1{0, 0}; p1.y() < parcels.ySize(); ++p1.y())
      59         1740 :     for (p1.x() = 0; p1.x() < parcels.xSize(); ++p1.x()) {
      60              :       // for each parcel p1
      61              : 
      62              :       // handle local neighbors
      63         1682 :       auto const &parcel = parcels[p1];
      64        20508 :       for (auto itStart = parcel.begin(); itStart != parcel.end(); ++itStart)
      65       126464 :         for (auto itEnd = std::next(itStart); itEnd != parcel.end(); ++itEnd) {
      66       107638 :           int const cheatLength = (itEnd->pos - itStart->pos).l1norm();
      67       107638 :           if (cheatLength <= radius) {
      68        71487 :             auto saving = (itEnd->idx - itStart->idx) - cheatLength;
      69        71487 :             if (saving >= minSaving)
      70         7984 :               ++ctr;
      71        71487 :           }
      72       107638 :         }
      73              : 
      74              :       // Handle neighbors in neighboring parcels
      75         7569 :       for (ParcelGrid::Coord p2 = p1; p2.y() <= p1.y() + parcelRadius.y(); ++p2.y())
      76         5887 :         for (p2.x() = (p2.y() == p1.y() ? p1.x() + 1 : p1.x() - parcelRadius.x());
      77        42891 :              p2.x() <= p1.x() + parcelRadius.x(); ++p2.x()) {
      78              :           // for each parcel p2 in the neighborhood of p1 (located after p1 in grid order)
      79              : 
      80        37004 :           for (auto const &pp1 : parcels[p1])
      81      4255277 :             for (auto const &pp2 : parcels[p2]) {
      82      4255277 :               auto pathDist = std::abs(pp2.idx - pp1.idx);
      83      4255277 :               auto cheatLength = (pp2.pos - pp1.pos).l1norm();
      84      4255277 :               if (cheatLength <= radius && pathDist - cheatLength >= minSaving)
      85       998852 :                 ++ctr;
      86      4255277 :             }
      87        37004 :         }
      88         1682 :     }
      89              : 
      90            2 :   return ctr;
      91            2 : }
      92              : 
      93              : } // namespace
      94              : 
      95            1 : template <> std::string solvePart1<2024, 20>(std::string_view const input) {
      96            1 :   Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
      97            1 :   return std::to_string(countCheats(map, 2, 100));
      98            1 : }
      99              : 
     100            1 : template <> std::string solvePart2<2024, 20>(std::string_view const input) {
     101            1 :   Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
     102            1 :   return std::to_string(countCheats(map, 20, 100));
     103            1 : }