AoC22/d14.cc

#include <iostream>
#include <vector>
#include <complex>

//#define ANIMATE

using namespace std;

enum Tile {
    EMPTY,
    ROCK,
    SAND
};

struct Input {
    vector<vector<complex<unsigned>>> rocks;
    vector<vector<Tile>> map;
    complex<unsigned> start;
    complex<unsigned> size;
};

void make_map(Input &input)
{
    // Figure out map extremes
    unsigned min_x = 500, max_x = 500;
    unsigned min_y = 0, max_y = 0;
    for (auto &rock : input.rocks) {
        for (auto &p : rock) {
            if (p.real() < min_x) min_x = p.real();
            if (p.real() > max_x) max_x = p.real();
            if (p.imag() < min_y) min_y = p.imag();
            if (p.imag() > max_y) max_y = p.imag();
        }
    }

    input.start = {min_x, min_y};
    input.size = {1 + max_x - min_x, 1 + max_y - min_y};

    input.map = vector<vector<Tile>>(input.size.imag(), vector<Tile>(input.size.real()));

    for (auto &rock : input.rocks) {
        complex<unsigned> p = rock.at(0);
        input.map[p.imag() - input.start.imag()][p.real() - input.start.real()] = ROCK;
        for (unsigned i = 1; i < rock.size(); i++) {
            complex<unsigned> &np = rock[i];
            while (p != np) {
                int dx = np.real() - p.real();
                int dy = np.imag() - p.imag();
                if (dx > 1) dx = 1;
                if (dx < -1) dx = -1;
                if (dy > 1) dy = 1;
                if (dy < -1) dy = -1;
                p += complex<int>(dx, dy);
                input.map[p.imag() - input.start.imag()][p.real() - input.start.real()] = ROCK;
            }
        }
    }
}

Input parse()
{
    Input data;
    for (string line; getline(cin, line);) {
        vector<complex<unsigned>> cur;
        unsigned pos = 0;
        for (;;) {
            unsigned first = pos;
            unsigned first_end = line.find(",", pos);
            unsigned second = first_end + 1;
            unsigned second_end = line.find(" -> ", pos);
            pos = second_end + 4;
            if (first == first_end || second == second_end) break;
            unsigned real = stoi(line.substr(first, first_end));
            unsigned imag = stoi(line.substr(second, second_end));
            cur.push_back({real, imag});
        }
        data.rocks.push_back(cur);
    }
    make_map(data);
    return data;
}

#ifdef ANIMATE
#include <fstream>
unsigned render_frame = 0;
void render(const vector<vector<Tile>> &map)
{
    char fname[] = "img/00000.pam";
    sprintf(fname, "img/%05u.pam", render_frame++);
    auto file = ofstream(fname);
    file << "P7\n";
    file << "WIDTH " << map.front().size() << '\n';
    file << "HEIGHT " << map.size() << '\n';
    file << "DEPTH 3\nMAXVAL 255\nTUPLTYPE RGB\nENDHDR\n";

    for (unsigned y = 0; y < map.size(); y++) {
        for (unsigned x = 0; x < map.front().size(); x++) {
            uint32_t color = 0;
            switch (map[y][x]) {
            case ROCK: color = 0xFF0000; break;
            case SAND: color = 0x00FFFF; break;
            default: break;
            }
            file.write((char *)&color, 3);
        }
    }
    file.close();
}
#endif

complex<int> dirs[] = {
    {0, 1},
    {-1, 1},
    {1, 1}
};

unsigned p1(const Input &input)
{
    auto map = input.map;

    const complex<int> sand_start(500, 0);

    unsigned count = 0;
    for (;;) {
        bool oob = false;
        complex<int> sand = sand_start - (complex<int>)input.start;
        for (;;) {
            bool moved = false;
            for (auto &d : dirs) {
                complex<int> test = sand + d;
                if (test.real() < 0 || test.real() >= (int)input.size.real()) oob = true;
                if (test.imag() < 0 || test.imag() >= (int)input.size.imag()) oob = true;
                if (oob) break;
                auto tile = map[test.imag()][test.real()];
                if (tile != EMPTY) continue;
                sand = test;
                moved = true;
                break;
            }
            if (!moved) {
                if (!oob) map[sand.imag()][sand.real()] = SAND;
                break;
            }
        }
#ifdef ANIMATE
        //render(map);
#endif
        if (oob) break;
        count++;
    }
    return count;
}

unsigned p2(const Input &input)
{
    auto map = input.map;

    map.push_back(vector<Tile>(input.size.real(), EMPTY));
    map.push_back(vector<Tile>(input.size.real(), ROCK));
    complex<int> start = input.start;
    complex<int> size = input.size + complex<unsigned>(0, 2);

    const complex<int> sand_start(500, 0);

    unsigned count = 0;
    for (;;) {
        complex<int> sand = sand_start - start;
        if (map[sand.imag()][sand.real()] == SAND) break;
        for (;;) {
            bool moved = false;
            for (auto &d : dirs) {
                complex<int> test = sand + d;

                // Widen the map
                if (test.real() < 0) {
                    for (auto &x : map) x.insert(x.begin(), EMPTY);
                    map.back().front() = ROCK;
                    start += complex<int>(-1, 0);
                    test += complex<int>(1, 0);
                    size += complex<int>(1, 0);
                } else if (test.real() >= size.real()) {
                    for (auto &x : map) x.push_back(EMPTY);
                    map.back().back() = ROCK;
                    size += complex<int>(1, 0);
                }
                if (test.imag() < 0 || test.imag() >= size.imag()) continue;

                auto tile = map[test.imag()][test.real()];
                if (tile != EMPTY) continue;
                sand = test;
                moved = true;
                break;
            }
            if (!moved) {
                map[sand.imag()][sand.real()] = SAND;
                break;
            }
        }
#ifdef ANIMATE
        render(map);
#endif
        count++;
    }

    return count;
}

int main()
{
    auto input = parse();
    cout << p1(input) << endl;
    cout << p2(input) << endl;
}