Line data    Source code

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