solution11.cc

#include "advent/answer.h"

namespace advent2020 {
namespace {
static const std::vector<std::pair<int, int>> dirs{
    {-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {0, -1},
};

size_t Neighbors1(const std::vector<std::string> &grid, int i, int j) {
  size_t count = 0;
  for (const auto &[dx, dy] : dirs) {
    int x = i + dx;
    int y = j + dy;
    if (x >= 0 && x < grid.size() && y >= 0 && y < grid.front().size() &&
        grid[x][y] == '#') {
      count++;
    }
  }
  return count;
}

size_t Neighbors2(const std::vector<std::string> &grid, int i, int j) {
  size_t count = 0;
  for (const auto &[dx, dy] : dirs) {
    int x = i + dx;
    int y = j + dy;
    while (x >= 0 && x < grid.size() && y >= 0 && y < grid.front().size()) {
      if (grid[x][y] == '#') {
        count++;
        break;
      } else if (grid[x][y] == 'L') {
        break;
      }
      x += dx;
      y += dy;
    }
  }
  return count;
}

size_t Converge(std::vector<std::string> grid,
                const std::vector<std::pair<int, int>> &seats,
                decltype(Neighbors1) count, size_t k) {
  bool changed = true;
  while (changed) {
    changed = false;
    auto copy = grid;
    for (auto &[i, j] : seats) {
      size_t neighbors = count(grid, i, j);
      if (grid[i][j] == 'L' && neighbors == 0) {
        copy[i][j] = '#';
        changed = true;
      } else if (grid[i][j] == '#' && neighbors >= k) {
        copy[i][j] = 'L';
        changed = true;
      }
    }
    grid = std::move(copy);
  }

  size_t c = 0;
  for (auto &row : grid) {
    c += std::count_if(row.begin(), row.end(), [](char c) { return c == '#'; });
  }
  return c;
}
}  // namespace

void Solution11(std::istream &input, advent::Answer &ans) {
  std::vector<std::string> grid;
  ans.ParseLines(input, grid);

  // precompute which cells have seats
  std::vector<std::pair<int, int>> seats;
  for (int i = 0; i < grid.size(); i++) {
    for (int j = 0; j < grid.front().size(); j++) {
      if (grid[i][j] != '.') {
        seats.emplace_back(i, j);
      }
    }
  }

  ans.Part1(Converge(grid, seats, Neighbors1, 4));
  ans.Part2(Converge(grid, seats, Neighbors2, 5));
}
}  // namespace advent2020