aoc2023-day21-cpp

#include <algorithm>
#include <deque>
#include <fstream>
#include <vector>
#include <map>
#include <chrono>

#include <range/v3/all.hpp>
#include <fmt/format.h>
#include <fmt/chrono.h>
#include <flux.hpp>

struct P {
    int x{}, y{};
    int parity() const { return (x + y) & 1; }
    auto operator<=>(P const&) const = default;
};

using Grid = std::vector<std::vector<char>>;

std::vector<P> reachableIn(Grid const& g, int steps, P start) {
    std::deque<std::pair<P, int>> q{{start, 0}};
    std::map<P, int> seen{{start, 0}};

    while(!q.empty()) {
        auto [n, d] = q.front();
        q.pop_front();

        for(P const& p : {P{n.x-1, n.y}, P{n.x+1, n.y}, P{n.x, n.y-1}, P{n.x, n.y+1}}) {
            if(p.y < 0 || p.x < 0 || p.y >= g.size() || p.x >= g.at(p.y).size() || g.at(p.y).at(p.x) == '#')
                continue;
            if(!seen.contains(p)) {
                seen[p] = d + 1;
                q.push_back({p, d+1});
            }
        }
    }

    return seen | std::views::filter([&](auto x) { return x.second <= steps; }) | std::views::transform([](auto x) { return x.first; }) | ranges::to_vector;

}

long solve1(Grid const& g, P start) {
    return std::ranges::ssize(reachableIn(g, 64, start) | std::views::filter([=](P p) { return p.parity() == start.parity(); }) | ranges::to_vector);
}

long solve2(Grid const& g, P start) {

    long steps = 26501365;
    long size = g.size();
    assert(size == 131);
    assert((steps - size/2) % size == 0);
    assert(steps % 2 == 1 && size % 2 == 1);

    long d = steps/size;
    long k = (2 * d + 1);
    long k1 = k*k/2;

    auto sq = [](long x) { return x * x; };
    auto center = reachableIn(g, size/2, start);
    auto full = reachableIn(g, 2*size, start);

    long d0 = std::ranges::count_if(center, [=](P p) { return p.parity() != start.parity(); });
    long dr = std::ranges::count_if(full, [=](P p) { return p.parity() != start.parity(); }) - d0;
    long dn0 = center.size() - d0;
    long dnr = dr + d0 - dn0;

    long r = sq(2 * d + 1) / 2;
    auto [rplus, rminus] = std::make_pair(r/2, r/2);
    long z = sq(2 * d + 1) / 2 + 1;
    long zplus = sq(1 + 2*(d/2));
    long zminus = z - zplus;

    return zplus * d0 + zminus * dn0 + rplus * dr + rminus * dnr;
}

Grid parse(std::string filename) {
    std::ifstream in(std::move(filename));
    return flux::getlines(in).map([](std::string s) { return flux::from(std::move(s)).to<std::vector<char>>(); }).to<Grid>();
}

int main(int argc, char* argv[]) {
    auto time = std::chrono::steady_clock::now();
    auto g = parse(argc > 1 ? argv[1] : "../task1.txt");

    P start;
    for(int y = 0; y < g.size(); ++y)
        for(int x = 0; x < g.at(y).size(); ++x)
            if(g.at(y).at(x) == 'S')
                start = P{.x = x, .y = y};

    fmt::println("task1={}\ntask2={}", solve1(g, start), solve2(g, start));
    fmt::println("took {}", std::chrono::steady_clock::now() - time);
}