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