aboutsummaryrefslogtreecommitdiff
path: root/2021/day20
diff options
context:
space:
mode:
Diffstat (limited to '2021/day20')
-rwxr-xr-x2021/day20/day20bin0 -> 104424 bytes
-rw-r--r--2021/day20/day20.cpp183
-rw-r--r--2021/day20/day20_input.txt102
-rw-r--r--2021/day20/makefile2
-rw-r--r--2021/day20/test0.txt7
5 files changed, 294 insertions, 0 deletions
diff --git a/2021/day20/day20 b/2021/day20/day20
new file mode 100755
index 0000000..347a7ec
--- /dev/null
+++ b/2021/day20/day20
Binary files differ
diff --git a/2021/day20/day20.cpp b/2021/day20/day20.cpp
new file mode 100644
index 0000000..6393d4c
--- /dev/null
+++ b/2021/day20/day20.cpp
@@ -0,0 +1,183 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <map>
+#include <vector>
+
+using vec = std::pair<int, int>;
+using lattice = std::map<vec, int>;
+
+
+std::vector<int> get_bounds (lattice img) {
+ std::vector<int> bounds { 999999, -999999, 999999, -999999 };
+ for (auto k : img) {
+ bounds[0] = std::min(bounds[0], k.first.first);
+ bounds[1] = std::max(bounds[1], k.first.first);
+ bounds[2] = std::min(bounds[2], k.first.second);
+ bounds[3] = std::max(bounds[3], k.first.second);
+ }
+ return bounds;
+}
+
+void show_lattice (lattice img) {
+ auto bounds = get_bounds(img);
+ std::cout << "lattice [" <<
+ bounds[0] <<", " << bounds[1] << ", " <<
+ bounds[2] <<", " << bounds[3] << "]" << std::endl;
+ for (int y=bounds[2]; y<=bounds[3]; y++) {
+ for (int x=bounds[0]; x<=bounds[1]; x++) {
+ if (img[vec(x,y)] == 1)
+ std::cout << "#";
+ else std::cout << ".";
+ }
+ std::cout << std::endl;
+ }
+}
+
+lattice parse_lattice (std::string raw) {
+ lattice img;
+ int y = 0;
+ while (raw.size() > 0) {
+ auto newline = raw.find("\n");
+ std::string line = raw;
+ if (newline != std::string::npos) {
+ line = raw.substr(0, newline);
+ raw = raw.substr(newline+1);
+ }
+ for (int x=0; x<line.size(); x++) {
+ if (line[x] == '#') img[vec(x, y)] = 1;
+ else img[vec(x, y)] = 0;
+ }
+ y ++;
+ }
+ return img;
+}
+
+
+class Matrix {
+ public:
+ Matrix () { background = 0; }
+ Matrix (lattice img) {
+ auto bounds = get_bounds(img);
+ sx = bounds[1]+1 - bounds[0];
+ sy = bounds[3]+1 - bounds[2];
+ offx = bounds[0];
+ offy = bounds[2];
+ for (int y=bounds[2]; y<=bounds[3]; y++) {
+ for (int x=bounds[0]; x<=bounds[1]; x++) {
+ cells.push_back(img[vec(x,y)]);
+ }
+ }
+ }
+
+ lattice to_lattice () {
+ lattice img;
+ for (int y=0; y<sy; y++) {
+ for (int x=0; x<sx; x++) {
+ img[vec(x+offx,y+offy)] = cells[at(x,y)];
+ }
+ }
+ return img;
+ }
+
+ int at (int x, int y) { return x + y*sx; }
+ int get_check (int x, int y) {
+ if (x<0 || x>=sx || y<0 || y>=sy) return background;
+ return cells[at(x, y)];
+ }
+
+ std::vector<int> cells;
+ int sx, sy;
+ int offx, offy;
+ int background;
+
+ Matrix trim (int shrink) {
+ Matrix trimmed;
+ trimmed.offx = offx + shrink;
+ trimmed.offy = offy + shrink;
+ trimmed.sx = sx - shrink*2;
+ trimmed.sy = sy - shrink*2;
+ trimmed.background = background;
+ for (int y=0; y<trimmed.sy; y++) {
+ for (int x=0; x<trimmed.sx; x++) {
+ trimmed.cells.push_back(cells[at(x+shrink, y+shrink)]);
+ }
+ }
+ return trimmed;
+ }
+};
+
+
+int get_rule_index (Matrix m, int s, int t) {
+ int index = 0;
+ for (int j=-1; j<2; j++) {
+ for (int i=-1; i<2; i++) {
+ int val = m.get_check(s+i,t+j);
+ int shift = 8 - ((i+1)+(j+1)*3);
+ index += (val << shift);
+ }
+ }
+ return index;
+}
+
+Matrix apply_rules (std::string rules, Matrix prev) {
+ Matrix next;
+ int expand = 3;
+ next.sx = prev.sx + expand*2;
+ next.sy = prev.sy + expand*2;
+ next.offx = prev.offx - expand;
+ next.offy = prev.offy - expand;
+ if (prev.background == 0) {
+ next.background = rules[0] == '#' ? 1 : 0;
+ }
+ if (prev.background == 1) {
+ next.background = rules[511] == '#' ? 1 : 0;
+ }
+ for (int y = 0; y < next.sy; y++) {
+ for (int x = 0; x < next.sx; x++) {
+ int index = get_rule_index(prev, x-expand, y-expand);
+ int val = (rules[index] == '#') ? 1 : 0;
+ next.cells.push_back(val);
+ }
+ }
+ Matrix trimmed = next.trim(expand-1);
+ return next;
+}
+
+int lit (std::vector<int> bounds, lattice img) {
+ int sum = 0;
+ for (int y = bounds[2]; y <= bounds[3]; y++) {
+ for (int x = bounds[0]; x <= bounds[1]; x++) {
+ sum += img[vec(x,y)];
+ }
+ }
+ return sum;
+}
+
+int main (int argc, char *argv[]) {
+ std::string raw;
+ std::getline(std::ifstream(argv[1]), raw, '\0');
+ auto separator = raw.find("\n\n");
+ std::string rules = raw.substr(0, separator);
+ std::string strimg = raw.substr(separator+2);
+ lattice img = parse_lattice(strimg);
+ show_lattice(img);
+ auto bounds = get_bounds(img);
+ int maxiter = std::stoi(std::string { argv[2] } );
+
+ Matrix m { img };
+ for (int i=0; i<maxiter; i++) {
+ m = apply_rules(rules, m);
+ std::cout << "iter: " << i << std::endl;
+ }
+ lattice out = m.to_lattice();
+
+ show_lattice(out);
+ bounds[0] -= maxiter;
+ bounds[1] += maxiter;
+ bounds[2] -= maxiter;
+ bounds[3] += maxiter;
+ std::cout << "lit " << lit(bounds, out) << std::endl;
+
+ return 0;
+}
diff --git a/2021/day20/day20_input.txt b/2021/day20/day20_input.txt
new file mode 100644
index 0000000..17cb6ce
--- /dev/null
+++ b/2021/day20/day20_input.txt
@@ -0,0 +1,102 @@
+###..#....#####.#.###..#####.#...##.#.#.#...#.###.#..###.###.....######..##..#.#.#...#..#.#..##...####..#.....#.#...####.#...#######.##..#.#.#....###.#..##.#...#.#.#.#....#..........#....##.#..##..#.#.#.....##.#....##.##.##.#.##.....#....######.###..##.#...###.###.#.#.#####..#.##.#.#####...#.##....#...#..#..#.###..##...###...#...#.##...#..#..##.#...#.#...#...#...#....##.##.#.###.###...##...###....#...#.#.#...#....##.#..##.#....#...#.###.#..##.....#.#.#.#####....#.#.#.###.#...#.#..###...##....####...#..####.
+
+.#..#####.#...##..#.###.#...##.###....###.#.#.##.###..###..#..#.###.###..##.#...#..#..#.....#...###.
+##.###.######..##..##.#.#.##.#..#...#..#....#.###........###.###..####..#....#..##.....########.###.
+#.##.##.#...##.##.......##..#.######.###...##.#####..##...#..###.###.###.##..#...#.#...#..#...#..#.#
+#.#...#####.####.#...#.#....####..##.#.####..####..#.#..#.##.....#..##...##......#..#...#.#.##..###.
+...###..#.#.##.#.#.##...##.####.#.##.#..#.#.###..#.##..##..#.#.#.##.#.#.####.........####...#####.##
+#.#..#...#..###.##.#.##.##.##.#.#...##.###.#.#######..#.#.#..#####.....##.##...#.#....#.###.#.#..##.
+##.##....##.##.#....###.#.....##.##...#.#....####...###.#.#.#...##.####.#..##......##...#..#.#.##...
+##...#....#####.#.##.##..#.##.##.###..#..#....#..#....#.#.##.##.##.#.##...#...##.#.#....###...##..##
+..#.##.#...###.....#..#.##..##.##.##.########.####...#..##..#..#..####.####.#.#.#..#...##.##.#.#..#.
+#..........#.....###.........##.#...###....#....#.#........####.#.#...#.##...####.####.##.##.#...#..
+#.##...##...#.##...#..#..#.#...........#..##...#.#..#.#..#...#.###..##...#####..#....#.#..#.##..#...
+#.#...#####.......###.#.##.#.##.###.#.##.##..#.##.##...#.##.#...#..#...###.##.###.#..#..##.###.##..#
+...#...#.#.#.##...#.##.#.####......#..#......#..##...#..#....#...#####...#####..#.#..###....#.#.###.
+.#..#.###.##.....##..####......#..###.#..#...#.#.##.....#.#...##.##.##.####.###.#.##..##...###.#.###
+###..###.##.##....#..#......#..#...####.#....##.#.#####.###..#..#.##.....#.##.###..##..#.#..###.##.#
+....#..##.......##.#...###..##...##....#...###.#....#.#..###......###.....##..###.....##..##.##..###
+###...#..#...##..#.....#.#.########.#.###.#.....##....#.#.#..#.#.#..###....##.#.#.##.##.##.##...#.#.
+##....#.##....##.....#.####..####.#.#..#.###.#.#.#.###..##.####..#..#######.#..#.#.###.#...##.....##
+.#.#.#.#####...#.##...#.###....#.##.##..##.#..###..####..##..############.####.#.#..###...##.#.....#
+..##..#.#.#.#..#####.##..#..#..#...#.###.##..#.###....#.#.###.#.#..######.###.#.#.#.#..####..##.####
+.....#.#...#..#.######.###..####.##...#...######..#...####.#.####.###.#.#..#....#..####..##.....#..#
+....##.#####........#..##....#########.#...##....#...#.####.#....####.####.######..###...##.#......#
+#...###.##.#.#..#.#..##....#.....#...#.##..#.#..#...###.#.##.#....##..###..##.##.##..###.########.##
+.#...#..####....#..#..##..#....###..#..#..#.###.##.#...#.###.....##...#.###..##..###.#..###.#.##.###
+###..#...#..#..###.####.###.####.#.###..#.#..##.##..###...#.#.....#..#.##....#.#.#.#.##.#..###..##.#
+.#.####.#....##...##.###.#.#.#.#..##.##....##.###...#.#.##.#.#..##..##.#..#.#.##......###.....###.##
+.##..##..#.##...####....###....#.###.#.##.##......#.##..#.#....##.####.##....##...#.####....###.#...
+##...#.##..##...##.##.##.########..#..##.#########.#.......##.#..###..#..###.#.#....########..##.##.
+.###...#....##.#..#..#...###...###########.#..#####..#..##........#.#...##...######..#.###.#.....##.
+...###..#.#.#####..#.#######.##.#......###..#..#####...###.#..##.##....###....##.####...#.##.###..#.
+....#....####.#.....###.......#..####...##...#..####......##.##..##.......##.#...#..##.##.#.###.####
+###...#..#......#...##.###..#.##.#.#....###.#..#.#.#........####.#...##.##...#...#..####.#....#..###
+##.#..##.##....##...########.#.#.#.###...#...#.##..##..####..###...###..#.###..#..###.###....##....#
+###...##....###.##.##.###......#..#..#.##.#.##..#..#.....##...##......##.###.######.##.#.#.##.#.##.#
+...##....#.###..##.##.#.##.#.#.....#.#.##..####..#.######....#.#..###...#.#.#......#.#.#.#.#..#.#.#.
+..####..##.#.#####.#........#..###..##..##..#..##.#.###..#..#..##.#.#.##.##.#...####..##.#.##..#.#.#
+...###.#...####..#..####.#..##########.######..##........##....#.#.###..####.#..#.##.....#..#.#.#.#.
+###.....##..#......##.....#.#.####.####..####...#.#.#######..##...##...#.#.##.##..#.#####...####...#
+.#.##.#.###.#..##...#####.#..#.##..###..#.#..##.###.###...#...#.##..##...###........##.......#.###..
+.#...##.###.###....###...######.##.######..........##.....###.##..##.##.#.#..#.#.....#.#####.#.##..#
+.#.#.##.#....##..#.###....#####.####..#.######..#..#..##.#..##..##.##.#..#....#..#.....###.###...#.#
+.##...#...#.##...###.###.#.##..#.###.#.#.##...#.#..#.#.#..#..#..#..###..#....##.######.##..#..##.##.
+.####.#...#....#........#.#..#######.####.#.####.#.#.#.###...#..#####.#.##.#.#.##.#...##...#......##
+.###..#.####.......##.##.#.#.#..####.#..#.#.#####.##.##.##..####....##.#.##.#.#.#..#..#..#.#.....###
+##...###.##.##.....#....##.###.##....#.#.###.....####.##..#.#####.....###.#..####..#.#....##......#.
+#...####..#.####.#.###......##.#.#.##..#...#..#..########.#...#..##.#.#..#.#.#.##.#.##.#..#.####.###
+..#..#.#..##..#.##...#..##....##.#.##..###.#...#....#.......###..#..#...####.#.###.#####.####...###.
+..##.....####.#..#.##..#...#.##.##.#..#.####..##.##..#.########..##.##.#..#.###.#.#..##.#.......#..#
+##..#####.............#######.##..#.#.#.##..#...#...#.##.#...#.##...####.##..##.#.#...#.#..##.#...#.
+#.#.###.#..#.#..##.#..##.#.#...#..###.##...#.#....#.#....#.#.####..##.###..#.###.##..##.#...#..#..#.
+###.##.#..#..##..#..#..###...#..##......#.####..#.###....###.......##...###....###..##.#.#..###.#..#
+##.#.#.#.#..##..#...#..##.#.##...#.#.#..#.##.#######..#.#..#........#..#######..#.#.##..##.##..#.#..
+###.....#.##.##.#.#.##...#...#.#..#.#.#.###..##...##.#..##.#.##.#..#....#..#..###.###....##.###...##
+...##....##..##.##....#.#..########....##..##.##.....##..####..##.#.####...##..###.###.....#...##..#
+.##.....#...#.#.#.###.#....#.#.######.#...###.#..###....#.#.#..#####.....###.######....#.##.#...###.
+###.######..###..##.###.###.#.#.######..####.##.#.####..#.....###..####..#...##.##.......#.#.#.#####
+###..########.#.#####..#.#...#.######.#.##..#..##...####..###..#...##..####.##..#......#..#..#.##.#.
+..#.###.###.#.#..##..#..#..##....##..#####...#.##..##.....##..##..##.##..#....#.#....##...#..###...#
+.#.....#.#.##.#.##..##....##.#.#.#..##.#...#####.#..#..#.##.#...##....##.####....#...#..##.#....#..#
+#.#.#.........###..#.#.#...#.####......#.#..##..##.####.####...#.###.#.#.##.###...##..##.######.####
+#.#.###..#..####.#######.....#...##.#.#.##.############..###.#.##...#.#.##.###.#######...#........#.
+#..###..##.#..########.##.#.#.....#.###...#.###..#.##..###.##.......#..##.......#......##..##..###..
+.#...#.##.#...##..##..#####...##.###.######...###.###.#.#.#..#..#...#..#.#######...####...#####.....
+#.#.#......##.#.#####.#.#.###..####..##..#...#....###..#..##.#.####..##.###...#.###..#.###.###.##.#.
+#.#..##.#...####.#####..........####..#.#.#..##....#.##.#.#..#####.#.#...##.##...###...#.##.#..###.#
+..##.#.#.###.#.###...#####..##..#.###..#.#...#..##.##.#...##.#.####..####..####..#.#.#.....#..###...
+..#.#...#.###...#........##...##..#..#...###.#...#.###..#..#....###..#..#########..###.###.##..##..#
+..#.......#.....#####.##.##.#.#.##...####.##........######.....#.#.##.#..#.#.##..#..#####.#.##.#.#.#
+##.#..#####.##..#####.#####.##.##.##.#.##.#..##......#..##.##..#.#..#.##..#.#..###.........#######..
+..##.#......#####.#.###..###.#.##.#.##.#######..#.##..#.....####.#..#.######..#..#..###.....##.#..##
+#.#.#.....#...###...#.##..###..##..##.#...#.#.#...###.....#.##.#.###.###.#..###...#..#.#.#...##...##
+.#....##.##...#######...#.#..#.#.#.##.#..###.#....#.####.#.##..#.###.....#..#..######.#.##.##.######
+#.#...##.....#######...#.##.#..#...#...####...#.####...####..#.##..#.#.##..#..##..#.#.##.####....###
+##.#####.##...##.#.#.#...#####.####.#.#....###.#.#...#.#..##.#.#..###.#..##..#.###.##.##.#####.#..#.
+.#####..#.#...#.##.##..#...#...#.##.#.#.######..####.#.##..#..#..#####..#.##..##.....###.#.##...##..
+#####..#.#..#..#......#...#####......#.#...#.#.###..####.#...###..#..###..#.#......###.#..###.##...#
+##.###.#.#.##.##...#.##....#..#.###.#####.#...##...##...#.##...##.#.####.#....##.##..#########..##.#
+####.#.#..##....#...#.....#....#.#.#..##.##..####...#..#.#.#..#.##..#..###...#####.#.#.##...####....
+.#..#..#######.#....####.######.......##.#.###...##.##.########.#.###...#....#..###.###.##.###..#.#.
+##..##.###.#.##...##..#...##.###..#####.....#..####.##....#.#.#....###.#......#..#.##.#.##.#.#......
+..#.##.#.#..###.####.###.#....#######.###.#..##.##.##.#.####.###.#...#...##...#.#####..##.#.#.....##
+.......##.######..#.....####...####.###.####.##.#...##..###..###.#...#####....#....###.##.....#.#.##
+..#.##.####..#.#.#.#.#.#...##.##.##.##...#########.###.#.#.##..#####.#.##..##......##.######..#.##..
+.#.##..#...#..#....#....#.##.##.###...##...#....##.##.###.#..........##..##.#.##.##..##....#.#.##.##
+##.#.#.###.#...#...####...#.#..##.#..##..#..#..#.###.####.##.##...#.#.###.#..###...#.#####..#.###.##
+#..#######....####.##.#..###.####..#.#.........#.###....####....#..###.#.#.###.#####.#..#...#.##.#.#
+...#..####...###...#..###....#..#.#..##.#..###.##.........###.###..##.##.###..###.....##.###.#..###.
+###.##.####....##..#..##.#...#.#.##..#.#.##.##....#####.####....##...#...###.##......#.#..#.#####...
+####...#.#.#..#.#.....##.##..#######.##.#####....##########.#....##......#...#####...#..#..#....##..
+####.###.#.####..#..#.#.#.##........##..####.#.###.....#.#...#.#.#.##..#.#..#.##.#......#.#.#.###..#
+#.###....#..###.###.##..##...#######...##.#...#....########...###.....######.##...###..#..#.###.#.##
+.#.#...#..#.#########..###.#.#.#..#..##.#.....###.#.....##.########..####.###.#.#..#..#.#..##.#.#.#.
+####.#..#....#####..###.#####..#..#..#...#..#..#.##.#.####....#.###..#.....###..#...#####..#.##.##..
+....#.##.##.#.#.#...#####..#.#..###...##..##..####.#..#...#.#####...#.###..###....##.#.##.####.#.##.
+#...###.###.##########.###..####..##....###.#..#.#..##.#.###..##..###.####.###..###..#..#......###..
+#.##.##....##.#..###.##.##.#.......#.#....#######.###..#.###.....####..######..##.##.###.##.#.......
+.##....###..#..###...##..####.#.###.#####....#.#....######..#.###......###..#.....#..#.###..#...#.##
+##.#.##...##...#....###.#.###.##.#..##.###.#.#..#.#.#...##.#...#.###.#...#..##.###.###..#..###..#.##
+##....#.#.#...##.....#..#.#..#..####......#####.##.#.#.#.########..#####..#....#.####.....#...#..#..
+...#..##.#.#.#.#..###.##.#...#..#.#..#..#.##.....#.##..###.##.#.#..##.##..##..#.###...#.#..#.#..###.
diff --git a/2021/day20/makefile b/2021/day20/makefile
new file mode 100644
index 0000000..391d6fc
--- /dev/null
+++ b/2021/day20/makefile
@@ -0,0 +1,2 @@
+all day20:
+ g++ -std=c++20 day20.cpp -o day20
diff --git a/2021/day20/test0.txt b/2021/day20/test0.txt
new file mode 100644
index 0000000..8fa4bd4
--- /dev/null
+++ b/2021/day20/test0.txt
@@ -0,0 +1,7 @@
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###