day20

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
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 @@
+..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#
+
+#..#.
+#....
+##..#
+..#..
+..###