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 <cctype>
       8              : #include <string>
       9              : #include <unordered_map>
      10              : 
      11              : namespace {
      12            2 : std::unordered_map<char, std::vector<Vec2<int>>> findAntennas(Grid2d<char> const &map) {
      13            2 :   std::unordered_map<char, std::vector<Vec2<int>>> antennas;
      14          102 :   for (int y = 0; y < map.ySize(); ++y)
      15         5100 :     for (int x = 0; x < map.xSize(); ++x)
      16         5000 :       if (std::isalnum(map[x, y]))
      17          376 :         antennas[map[x, y]].emplace_back(x, y);
      18            2 :   return antennas;
      19            2 : }
      20              : 
      21              : Grid2d<char> findAntinodesPt1(Grid2d<char> const &map,
      22            1 :                               std::unordered_map<char, std::vector<Vec2<int>>> &antennas) {
      23            1 :   Grid2d<char> antinodes(map.xSize(), map.ySize(), '.');
      24           50 :   for (auto const &[frequency, locations] : antennas) {
      25          238 :     for (auto it = locations.begin(); it != locations.end(); ++it)
      26          452 :       for (auto it2 = std::next(it); it2 != locations.end(); ++it2) {
      27          264 :         Vec2<int> const delta = *it2 - *it;
      28          264 :         Vec2<int> candidate0 = *it - delta;
      29          264 :         Vec2<int> candidate1 = *it2 + delta;
      30          264 :         if (antinodes.inBounds(candidate0))
      31          175 :           antinodes[candidate0] = '#';
      32          264 :         if (antinodes.inBounds(candidate1))
      33          152 :           antinodes[candidate1] = '#';
      34          264 :       }
      35           50 :   }
      36            1 :   return antinodes;
      37            1 : }
      38              : 
      39              : Grid2d<char> findAntinodesPt2(Grid2d<char> const &map,
      40            1 :                               std::unordered_map<char, std::vector<Vec2<int>>> &antennas) {
      41            1 :   Grid2d<char> antinodes(map.xSize(), map.ySize(), '.');
      42           50 :   for (auto const &[frequency, locations] : antennas) {
      43          238 :     for (auto it = locations.begin(); it != locations.end(); ++it)
      44          452 :       for (auto it2 = std::next(it); it2 != locations.end(); ++it2) {
      45          264 :         Vec2<int> const delta = *it2 - *it;
      46         1191 :         for (Vec2<int> pos = *it; antinodes.inBounds(pos); pos -= delta)
      47          927 :           antinodes[pos] = '#';
      48         1194 :         for (Vec2<int> pos = *it2; antinodes.inBounds(pos); pos += delta)
      49          930 :           antinodes[pos] = '#';
      50          264 :       }
      51           50 :   }
      52            1 :   return antinodes;
      53            1 : }
      54              : 
      55              : } // namespace
      56              : 
      57            1 : template <> std::string solvePart1<2024, 8>(std::string_view const input) {
      58            1 :   Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
      59            1 :   std::unordered_map<char, std::vector<Vec2<int>>> antennas = findAntennas(map);
      60            1 :   Grid2d<char> antinodes = findAntinodesPt1(map, antennas);
      61            1 :   return std::to_string(antinodes.count('#'));
      62            1 : }
      63              : 
      64            1 : template <> std::string solvePart2<2024, 8>(std::string_view const input) {
      65            1 :   Grid2d<char> const map = LinewiseInput(input).makeCharGrid2d();
      66            1 :   std::unordered_map<char, std::vector<Vec2<int>>> antennas = findAntennas(map);
      67            1 :   Grid2d<char> antinodes = findAntinodesPt2(map, antennas);
      68            1 :   return std::to_string(antinodes.count('#'));
      69            1 : }