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