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