From 173745deea84907aabdee6e522148fd6e94e7f3e Mon Sep 17 00:00:00 2001 From: jacopograndi Date: Sat, 8 Jan 2022 00:20:06 +0100 Subject: day12 --- 2021/day12/day12 | Bin 0 -> 142584 bytes 2021/day12/day12.cpp | 106 +++++++++++++++++++++++++++++++++++++++ 2021/day12/day12_input.txt | 25 +++++++++ 2021/day12/day12_input_big.txt | 18 +++++++ 2021/day12/day12_input_med.txt | 10 ++++ 2021/day12/day12_input_small.txt | 7 +++ 2021/day12/makefile | 2 + 7 files changed, 168 insertions(+) create mode 100755 2021/day12/day12 create mode 100644 2021/day12/day12.cpp create mode 100644 2021/day12/day12_input.txt create mode 100644 2021/day12/day12_input_big.txt create mode 100644 2021/day12/day12_input_med.txt create mode 100644 2021/day12/day12_input_small.txt create mode 100644 2021/day12/makefile diff --git a/2021/day12/day12 b/2021/day12/day12 new file mode 100755 index 0000000..4656112 Binary files /dev/null and b/2021/day12/day12 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 +#include +#include +#include +#include +#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 nodes; + std::vector arcs; + + std::vector star (std::string start) { + std::vector 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 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 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>; +Paths follow (Graph G, std::vector 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 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 { "start" }, twice); +} + + +int main (int argc, char *argv[]) { + std::string raw; + std::getline(std::ifstream(argv[1]), raw, '\0'); + std::vector lines; + split(lines, raw, "\n"); + + Graph graph; + for (auto line : lines) { + if (line.size() == 0) continue; + std::vector 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 -- cgit v1.2.3-54-g00ecf