Line data    Source code

       1              : #include "Grid2d.h"
       2              : #include "IntegerCast.h"
       3              : #include "LinewiseInput.h"
       4              : #include "PuzzleImpl.h"
       5              : 
       6              : #include <algorithm>
       7              : #include <array>
       8              : #include <cstdint>
       9              : #include <numeric>
      10              : #include <string>
      11              : #include <string_view>
      12              : 
      13              : namespace {
      14              : 
      15            1 : Grid2d<unsigned char> computeVisibility(Grid2d<signed char> const &treeHeights) {
      16            1 :   Grid2d<unsigned char> visibility(treeHeights.xSize(), treeHeights.ySize(), 0);
      17              : 
      18          100 :   for (int y = 0; y < treeHeights.ySize(); ++y) {
      19           99 :     signed char visibleHeight = -1;
      20         9900 :     for (int x = 0; x < treeHeights.xSize(); ++x) {
      21         9801 :       if (treeHeights[x, y] > visibleHeight) {
      22          542 :         visibility[x, y] = 1;
      23          542 :         visibleHeight = treeHeights[x, y];
      24          542 :       }
      25         9801 :     }
      26           99 :     visibleHeight = -1;
      27         9900 :     for (int x = treeHeights.xSize() - 1; x >= 0; --x) {
      28         9801 :       if (treeHeights[x, y] > visibleHeight) {
      29          510 :         visibility[x, y] = 1;
      30          510 :         visibleHeight = treeHeights[x, y];
      31          510 :       }
      32         9801 :     }
      33           99 :   }
      34              : 
      35          100 :   for (int x = 0; x < treeHeights.xSize(); ++x) {
      36           99 :     signed char visibleHeight = -1;
      37         9900 :     for (int y = 0; y < treeHeights.ySize(); ++y) {
      38         9801 :       if (treeHeights[x, y] > visibleHeight) {
      39          519 :         visibility[x, y] = 1;
      40          519 :         visibleHeight = treeHeights[x, y];
      41          519 :       }
      42         9801 :     }
      43           99 :     visibleHeight = -1;
      44         9900 :     for (int y = treeHeights.ySize() - 1; y >= 0; --y) {
      45         9801 :       if (treeHeights[x, y] > visibleHeight) {
      46          531 :         visibility[x, y] = 1;
      47          531 :         visibleHeight = treeHeights[x, y];
      48          531 :       }
      49         9801 :     }
      50           99 :   }
      51              : 
      52            1 :   return visibility;
      53            1 : }
      54              : 
      55            1 : int computeScenicScore(Grid2d<signed char> const &treeHeights) {
      56              : 
      57            1 :   Grid2d<int> scenicScore(treeHeights.xSize(), treeHeights.ySize(), 0);
      58              : 
      59           98 :   for (int y = 1; y < treeHeights.ySize() - 1; ++y) {
      60         9506 :     for (int x = 1; x < treeHeights.xSize() - 1; ++x) {
      61         9409 :       scenicScore[x, y] = 1;
      62         9409 :       int c = 0;
      63        26308 :       for (c = x - 1; c >= 1 && treeHeights[c, y] < treeHeights[x, y]; --c)
      64        16899 :         ;
      65         9409 :       scenicScore[x, y] *= x - c;
      66        25815 :       for (c = x + 1; c < treeHeights.xSize() - 1 && treeHeights[c, y] < treeHeights[x, y]; ++c)
      67        16406 :         ;
      68         9409 :       scenicScore[x, y] *= c - x;
      69        25992 :       for (c = y - 1; c >= 1 && treeHeights[x, c] < treeHeights[x, y]; --c)
      70        16583 :         ;
      71         9409 :       scenicScore[x, y] *= y - c;
      72        26025 :       for (c = y + 1; c < treeHeights.ySize() - 1 && treeHeights[x, c] < treeHeights[x, y]; ++c)
      73        16616 :         ;
      74         9409 :       scenicScore[x, y] *= c - y;
      75         9409 :     }
      76           97 :   }
      77              : 
      78            1 :   return scenicScore.max();
      79            1 : }
      80              : 
      81              : } // namespace
      82              : 
      83            1 : template <> std::string solvePart1<2022, 8>(std::string_view const input) {
      84            1 :   LinewiseInput lines(input);
      85            1 :   Grid2d<char> inputGrid = lines.makeCharGrid2d();
      86              : 
      87            1 :   Grid2d<signed char> treeHeights =
      88         9801 :       inputGrid.map([](char const c) { return static_cast<signed char>(c - '0'); });
      89              : 
      90            1 :   Grid2d<unsigned char> visibility = computeVisibility(treeHeights);
      91              : 
      92            1 :   return std::to_string(visibility.count(1));
      93            1 : }
      94              : 
      95            1 : template <> std::string solvePart2<2022, 8>(std::string_view const input) {
      96            1 :   LinewiseInput lines(input);
      97            1 :   Grid2d<char> inputGrid = lines.makeCharGrid2d();
      98              : 
      99            1 :   Grid2d<signed char> treeHeights =
     100         9801 :       inputGrid.map([](char const c) { return static_cast<signed char>(c - '0'); });
     101              : 
     102            1 :   return std::to_string(computeScenicScore(treeHeights));
     103            1 : }