Day13.cpp

#include <iostream>
#include <string>
#include <array>
#include <map>
#include <set>

using Point = std::array<int, 2>;

inline Point operator+(const Point& p1, const Point& p2) {
  return {{std::get<0>(p1) + std::get<0>(p2), std::get<1>(p1) + std::get<1>(p2)}};
}

int main(int argc, char* argv[]) {
  const bool part2{std::stoi(argv[2]) == 2};
  const int LIMIT{50}, NUM{std::stoi(argv[1])};
  const std::array<Point, 4> DIRS{{{{-1, 0}}, {{1, 0}}, {{0, -1}}, {{0, 1}}}};
  const Point INIT{{1, 1}}, TARGET{{39, 31}};
  auto valid = [NUM](const Point& p) -> bool {
    return p[0] >= 0 && p[1] >= 0 && !(__builtin_popcount(NUM + p[1] * p[1] + 3 * p[1] + 2 * p[1] * p[0] + p[0] + p[0] * p[0]) & 0x1);
  };
  std::set<Point> queue{{INIT}}, walls{};
  std::map<Point, int> dist{{INIT, 0}};
  while (queue.size() != 0 && (part2 || dist.find(TARGET) == dist.end())) {
    std::set<Point> next;
    for (const auto& q : queue)
      for (const auto& d : DIRS)
        if (valid(q + d) && dist.find(q + d) == dist.end() && (!part2 || dist.at(q) < LIMIT))
          next.insert(q + d), dist.emplace(q + d, dist.at(q) + 1);
        else if (!valid(q + d) && (q+d)[0] >= 0 && (q+d)[1] >= 0)
          walls.insert(q + d);
    std::swap(queue, next);
  }
  std::cout << (part2 ? dist.size() : dist.at(TARGET)) << std::endl;

  int minX{INT_MAX},minY{INT_MAX},maxX{INT_MIN},maxY{INT_MIN};
  for (const auto& d : dist)
    minX=std::min(minX,d.first[1]), minY=std::min(minY,d.first[0]), maxX=std::max(maxX,d.first[1]), maxY=std::max(maxY,d.first[0]);
  for (const auto& w : walls)
    minX=std::min(minX,w[1]), minY=std::min(minY,w[0]), maxX=std::max(maxX,w[1]), maxY=std::max(maxY,w[0]);
  for (int y{minY}; y <= maxY; ++y) {
    for (int x{minX}; x <= maxX; ++x) {
      const Point p{{y,x}};
      if (p == TARGET || p == INIT)
        std::cout << 'X';
      else if (walls.find(p) != walls.end())
        std::cout << '#';
      else if (dist.find(p) != dist.end())
          std::cout << (dist[p] % 10);
      else
        std::cout << ' ';
      std::cout << ' ';
    }
    std::cout << std::endl;
  }
}