1 files changed, 122 insertions, 0 deletions
diff --git a/2021/day15/day15.cpp b/2021/day15/day15.cpp
new file mode 100644
index 0000000..f829cd5
--- /dev/null
+++ b/2021/day15/day15.cpp
@@ -0,0 +1,122 @@
+#include <iostream>
+#include <fstream>
+#include <vector>
+#include <string>
+#include <map>
+#include <queue>
+#include <functional>
+#include "../utils.h"
+
+class Grid {
+	public: Grid () { }
+	int xytoi (int x, int y) { return x+ y*sizex; }
+	int itox (int i) { return i % sizex; }
+	int itoy (int i) { return i / sizex; }
+	bool oob (int x, int y) {
+		if (x < 0 || x > sizex-1) return true;
+		if (y < 0 || y > sizey-1) return true;
+		return false;
+	}
+
+	int sizex, sizey;
+	std::vector<int> cells;
+
+	std::vector<int> fw (int i) {
+		int x = itox(i), y = itoy(i);
+		std::vector<int> star;
+		for (int t=-1; t<2; t++) {
+			for (int s=-1; s<2; s++) {
+				if (abs(s)+abs(t) == 1 && !oob(x+s, y+t)) {
+					star.push_back(xytoi(x+s, y+t));
+				}
+			}
+		}
+		return star;
+	}
+
+	int astar (int istart, int iend) {
+		std::map<int, int> cost;
+		std::map<int, int> prev;
+		cost[iend] = cells[iend];
+		prev[iend] = iend;
+		auto cmp = [&cost] (int a, int b) { return cost[a] > cost[b]; };
+		std::priority_queue<int, std::vector<int>, decltype(cmp)> Q(cmp);
+		Q.push(iend);
+
+		while (Q.size() > 0) {
+			int n = Q.top(); Q.pop();
+			auto star = fw(n);
+			int min = cost[prev[n]];
+			for (int j : star) {
+				if (prev.find(j) == prev.end()) {
+					prev[j] = n;
+					cost[j] = cost[prev[j]] + cells[j];
+					Q.push(j);
+				}
+				if (min >= cost[j]) {
+					prev[n] = j;
+					cost[n] = cost[prev[n]] + cells[n];
+					min = cost[j];
+				}
+			}
+		}
+
+		if (true) {
+			for (int y=0; y<sizey; y++) {
+				for (int x=0; x<sizex; x++) {
+					int n = xytoi(x, y);
+					int i = itox(prev[n]);
+					int j = itoy(prev[n]);
+					std::cout << cells[n];
+				}
+				std::cout << std::endl;
+			}
+		}
+
+		return cost[istart] - cells[istart];
+	}
+};
+
+Grid five (Grid grid) {
+	Grid big;
+	big.sizex = grid.sizex * 5;
+	big.sizey = grid.sizey * 5;
+	for (int j=0; j<5; j++) {
+		for (int y=0; y<grid.sizey; y++) {
+			for (int i=0; i<5; i++) {
+				for (int x=0; x<grid.sizex; x++) {
+					int k = grid.cells[grid.xytoi(x, y)]+(i+j);
+					while (k > 9) k -= 9;
+					big.cells.push_back(k);
+				}
+			}
+		}
+	}
+	return big;
+}
+
+int main (int argc, char *argv[]) {
+	std::string raw;
+	std::getline(std::ifstream(argv[1]), raw, '\0');
+	std::vector<std::string> lines;
+	split(lines, raw, "\n");
+
+	Grid grid;
+	grid.sizey = 0;
+	for (std::string line : lines) {
+		if (line.size() == 0) continue;
+		grid.sizex = 0;
+		for (char c : line) {
+			grid.cells.push_back(std::stoi(std::string { c }));
+			grid.sizex ++;
+		}
+		grid.sizey ++;
+	}
+
+	if (argc > 2) grid = five(grid);
+
+	int l = grid.astar(grid.xytoi(0, 0), grid.xytoi(grid.sizex-1, grid.sizey-1));
+	std::cout << "min risk: " << l << std::endl;
+
+	return 0;
+}