Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "LinewiseInput.h"
       3              : #include "PuzzleImpl.h"
       4              : 
       5              : #include <libassert/assert.hpp>
       6              : 
       7              : #include <limits>
       8              : #include <queue>
       9              : 
      10              : namespace {
      11              : 
      12              : using Coord = Grid2dSpan<uint8_t const>::Coord;
      13              : 
      14              : enum Dir : uint8_t { N = 0, E = 1, S = 2, W = 3 };
      15              : constexpr std::array<Dir, 4u> directions = {N, E, S, W};
      16              : constexpr std::array<Coord, 4u> stencil = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
      17              : constexpr std::array<Dir, 4u> leftTurn = {W, N, E, S};
      18              : constexpr std::array<Dir, 4u> rightTurn = {E, S, W, N};
      19              : 
      20              : using NodePriority = std::tuple<unsigned, Dir, Coord>;
      21      3647352 : bool operator<(NodePriority const &lhs, NodePriority const &rhs) {
      22      3647352 :   return std::get<0>(lhs) > std::get<0>(rhs);
      23      3647352 : };
      24              : 
      25       275972 : unsigned costHeuristic(Coord start, Coord goal) {
      26       275972 :   return std::abs(start.x() - goal.x()) + std::abs(start.y() - goal.y());
      27       275972 : }
      28              : 
      29              : unsigned findShortestPath(Grid2dSpan<uint8_t const> heatLoss, Coord const &startPos,
      30              :                           Coord const &goalPos, int const minNumStepsSameDir,
      31            2 :                           int const maxNumStepsSameDir) {
      32              : 
      33            2 :   std::priority_queue<NodePriority> openSet;
      34            2 :   std::array<Grid2d<unsigned>, directions.size()> cost;
      35            2 :   for (auto &c : cost)
      36            8 :     c = Grid2d<unsigned>{heatLoss.xSize(), heatLoss.ySize(), std::numeric_limits<unsigned>::max()};
      37              : 
      38            8 :   for (Dir d : directions) {
      39            8 :     openSet.emplace(0, d, startPos);
      40            8 :     cost[d][startPos] = 0u;
      41            8 :   }
      42              : 
      43       261718 :   while (!openSet.empty()) {
      44       261718 :     auto [costEstimate, curDir, curPos] = openSet.top();
      45       261718 :     openSet.pop();
      46              : 
      47       261718 :     unsigned const curCost = cost[curDir][curPos];
      48              : 
      49       261718 :     if (curPos == goalPos)
      50            2 :       return curCost;
      51              : 
      52       261716 :     unsigned neighborCost = curCost;
      53       261716 :     Coord neighborPos = curPos;
      54      2058159 :     for (int steps = 1; steps <= maxNumStepsSameDir; ++steps) {
      55      1808103 :       neighborPos += stencil[curDir];
      56      1808103 :       if (neighborPos.x() < 0 || neighborPos.y() < 0 || neighborPos.x() >= heatLoss.xSize() ||
      57      1808103 :           neighborPos.y() >= heatLoss.ySize())
      58        11660 :         break;
      59              : 
      60      1796443 :       neighborCost += heatLoss[neighborPos];
      61              : 
      62      1796443 :       if (steps < minNumStepsSameDir)
      63       451665 :         continue;
      64              : 
      65      1344778 :       if (neighborCost < cost[leftTurn[curDir]][neighborPos]) {
      66       137986 :         cost[leftTurn[curDir]][neighborPos] = neighborCost;
      67       137986 :         openSet.emplace(neighborCost + costHeuristic(neighborPos, goalPos), leftTurn[curDir],
      68       137986 :                         neighborPos);
      69       137986 :       }
      70              : 
      71      1344778 :       if (neighborCost < cost[rightTurn[curDir]][neighborPos]) {
      72       137986 :         cost[rightTurn[curDir]][neighborPos] = neighborCost;
      73       137986 :         openSet.emplace(neighborCost + costHeuristic(neighborPos, goalPos), rightTurn[curDir],
      74       137986 :                         neighborPos);
      75       137986 :       }
      76      1344778 :     }
      77       261716 :   }
      78            2 :   PANIC();
      79            0 : }
      80              : 
      81              : } // namespace
      82              : 
      83            1 : template <> size_t part1<2023, 17>(std::string_view const input) {
      84            1 :   LinewiseInput lines(input);
      85            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
      86        19881 :   Grid2d<uint8_t> heatLoss = grid.map([](char const c) { return static_cast<uint8_t>(c - '0'); });
      87              : 
      88            1 :   return findShortestPath(heatLoss, {0, heatLoss.ySize() - 1}, {heatLoss.xSize() - 1, 0}, 1, 3);
      89            1 : }
      90              : 
      91            1 : template <> size_t part2<2023, 17>(std::string_view const input) {
      92            1 :   LinewiseInput lines(input);
      93            1 :   Grid2d<char> grid = lines.makeCharGrid2d();
      94        19881 :   Grid2d<uint8_t> heatLoss = grid.map([](char const c) { return static_cast<uint8_t>(c - '0'); });
      95              : 
      96            1 :   return findShortestPath(heatLoss, {0, heatLoss.ySize() - 1}, {heatLoss.xSize() - 1, 0}, 4, 10);
      97            1 : }