aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rwxr-xr-x2021/day12/day12bin0 -> 142584 bytes
-rw-r--r--2021/day12/day12.cpp106
-rw-r--r--2021/day12/day12_input.txt25
-rw-r--r--2021/day12/day12_input_big.txt18
-rw-r--r--2021/day12/day12_input_med.txt10
-rw-r--r--2021/day12/day12_input_small.txt7
-rw-r--r--2021/day12/makefile2
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
Binary files differ
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