Skip to content

Instantly share code, notes, and snippets.

@chowder
Created December 21, 2021 00:42
Show Gist options
  • Save chowder/edb19149268262e517be7cebe86367b8 to your computer and use it in GitHub Desktop.
Save chowder/edb19149268262e517be7cebe86367b8 to your computer and use it in GitHub Desktop.
Advent of Code 2021 - Day 20 - Sparse Array
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment