day12

7 files changed, 168 insertions, 0 deletions

diff --git a/2021/day12/day12 b/2021/day12/day12
new file mode 100755
index 0000000..4656112
--- /dev/null
+++ b/2021/day12/day12
diff --git a/2021/day12/day12.cpp b/2021/day12/day12.cpp
new file mode 100644
index 0000000..ab6a29e
--- /dev/null
+++ b/2021/day12/day12.cpp
@@ -0,0 +1,106 @@
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <stack>
+#include "../utils.h"
+
+class Arc {
+	public: Arc (std::string s, std::string t) : s(s), t(t) {}
+	std::string s, t;
+};
+
+class Graph {
+	public: Graph () { }
+	std::vector<std::string> nodes;
+	std::vector<Arc> arcs;
+
+	std::vector<std::string> star (std::string start) {
+		std::vector<std::string> res;
+		for (auto arc : arcs) {
+			if (arc.s == start) res.push_back(arc.t);
+			if (arc.t == start) res.push_back(arc.s);
+		}
+		return res;
+	}
+};
+
+int count (std::vector<std::string> vec, std::string str) {
+	return std::count(std::begin(vec), std::end(vec), str);
+}
+
+bool lower (std::string str) {
+	for (auto c : str) if (!islower(c)) return false;
+	return true;
+}
+
+bool check (std::vector<std::string> vec, std::string str, bool twice) {
+	if (!lower(str)) return true;
+	if (count(vec, str) < 1) return true;
+	if (twice) {
+		std::string flag = "";
+		for (auto s : vec) {
+			if (count(vec, s) > 1 && lower(s)) {
+				if (flag == "") flag = s;
+				else return false;
+			}
+		}
+		return true;
+	}
+	return false;
+} 
+
+using Paths = std::vector<std::vector<std::string>>;
+Paths follow (Graph G, std::vector<std::string> path, bool twice) {
+	auto c = path[path.size()-1];
+	auto star = G.star(c);
+	Paths paths;
+	if (c == "end") {
+		paths.push_back(path);
+		return paths;
+	}
+	for (auto n : star) {
+		if (n == "start") continue;
+		if (!check(path, n, twice)) continue;
+
+		std::vector<std::string> newpath = path;
+		newpath.push_back(n);
+		Paths res = follow(G, newpath, twice);
+		paths.insert(std::end(paths), std::begin(res), std::end(res));
+	}
+	return paths;
+}
+
+Paths search (Graph G, bool twice) {
+	return follow(G, std::vector<std::string> { "start" }, twice);
+}
+
+
+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");
+	
+	Graph graph;
+	for (auto line : lines) {
+		if (line.size() == 0) continue; 
+		std::vector<std::string> tokens;
+		split(tokens, line, "-");
+		graph.nodes.push_back(tokens[0]);
+		graph.nodes.push_back(tokens[1]);
+		graph.arcs.push_back(Arc { tokens[0], tokens[1] });
+	}
+	
+	auto paths = search(graph, (argc > 2 ? (atoi(argv[2]) == 1) : false));
+	for (auto p : paths) {
+		for (auto s : p) {
+			std::cout << s << ",";
+		}
+		std::cout << std::endl;
+	}
+
+	std::cout << "paths: " << paths.size() << std::endl;
+
+	return 0;
+}
diff --git a/2021/day12/day12_input.txt b/2021/day12/day12_input.txt
new file mode 100644
index 0000000..2b19f82
--- /dev/null
+++ b/2021/day12/day12_input.txt
@@ -0,0 +1,25 @@
+we-NX
+ys-px
+ys-we
+px-end
+yq-NX
+px-NX
+yq-px
+qk-yq
+pr-NX
+wq-EY
+pr-oe
+wq-pr
+ys-end
+start-we
+ys-start
+oe-DW
+EY-oe
+end-oe
+pr-yq
+pr-we
+wq-start
+oe-NX
+yq-EY
+ys-wq
+ys-pr
diff --git a/2021/day12/day12_input_big.txt b/2021/day12/day12_input_big.txt
new file mode 100644
index 0000000..65f3833
--- /dev/null
+++ b/2021/day12/day12_input_big.txt
@@ -0,0 +1,18 @@
+fs-end
+he-DX
+fs-he
+start-DX
+pj-DX
+end-zg
+zg-sl
+zg-pj
+pj-he
+RW-he
+fs-DX
+pj-RW
+zg-RW
+start-pj
+he-WI
+zg-he
+pj-fs
+start-RW
diff --git a/2021/day12/day12_input_med.txt b/2021/day12/day12_input_med.txt
new file mode 100644
index 0000000..62cc714
--- /dev/null
+++ b/2021/day12/day12_input_med.txt
@@ -0,0 +1,10 @@
+dc-end
+HN-start
+start-kj
+dc-start
+dc-HN
+LN-dc
+HN-end
+kj-sa
+kj-HN
+kj-dc
diff --git a/2021/day12/day12_input_small.txt b/2021/day12/day12_input_small.txt
new file mode 100644
index 0000000..6fd8c41
--- /dev/null
+++ b/2021/day12/day12_input_small.txt
@@ -0,0 +1,7 @@
+start-A
+start-b
+A-c
+A-b
+b-d
+A-end
+b-end
diff --git a/2021/day12/makefile b/2021/day12/makefile
new file mode 100644
index 0000000..1795c03
--- /dev/null
+++ b/2021/day12/makefile
@@ -0,0 +1,2 @@
+all day12.cpp:
+	g++ -std=c++20 -o day12 day12.cpp