Advent of Code 2021 - Day 20 - Sparse Array

main.cpp

#include <iostream>
#include <unordered_set>

using namespace std;

typedef pair<int, int> Point;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first * 1024 + v.second;
    }
};

typedef unordered_set<Point, pair_hash> PointSet;

bool enhance_point(
    const PointSet& points, const string& algorithm, 
    int x, int y, 
    int xmin, int xmax, 
    int ymin, int ymax, 
    char frontier
) {
    int index = 0;
    for (int j = -1; j <= 1; j++) {
        for (int i = -1; i <= 1; i++) {
            index <<= 1;
            if (x + i <= xmin || x + i >= xmax || y + j <= ymin || y + j >= ymax) {
                if (frontier == '#') index += 1;
            }
            else if (points.find({x + i, y + j}) != points.end()) {
                index += 1;
            }
        }
    }
    return algorithm[index] == '#';
}

PointSet enhance_picture(
    const PointSet& points, const string& algorithm, 
    int x1, int x2, 
    int y1, int y2, 
    char frontier
) {
    PointSet enhanced;
    for (int i = x1 - 1; i <= x2 + 1; i++)
        for (int j = y1 - 1; j <= y2 + 1; j++)
            if (enhance_point(points, algorithm, i, j, x1 - 1, x2 + 1, y1 - 1, y2 + 1, frontier))
                enhanced.insert({i, j});

    return enhanced;
}

int main() {
    (void)!freopen("input.txt", "r", stdin);

    string algorithm;
    cin >> algorithm;
    cin.ignore(2);
    
    string line;
    int y = 0, x = 0;

    PointSet points;

    while (getline(cin, line)) {
        for (int i = 0; i < line.size(); i++) {
            if (line[i] == '#') points.insert({i, y});
            x = line.size();
        }
        y++;
    }

    int x1 = 0, y1 = 0;
    int x2 = --x, y2 = --y;
    char frontier = '.';

    for (int i = 0; i < 50; i++) {
        points = enhance_picture(points, algorithm, x1--, x2++, y1--, y2++, frontier);
        frontier = frontier == '.' ? '#' : '.';
    }

    cout << points.size() << endl;
}