aoc(2308): Haunted Wasteland

6 files changed, 191 insertions, 0 deletions

diff --git a/2023/08/Makefile b/2023/08/Makefile
new file mode 100644
index 0000000..af6a294
--- /dev/null
+++ b/2023/08/Makefile
@@ -0,0 +1,19 @@
+CXXFLAGS := -std=c++17
+CPPFLAGS := -I../include
+EXE := part1 part2
+
+.PHONY: all clean configure
+
+all: $(EXE)
+
+configure:
+        bear -- $(MAKE) all
+
+%.o: %.cpp
+        $(CXX) -c $(CPPFLAGS) $(CXXFLAGS) $< -o $@
+
+clean:
+        rm -rf $(EXE) src/*.o compile_commands.json
+
+%: src/%.o
+        $(CXX) $^ -o $@
diff --git a/2023/08/resources/input_small1.txt b/2023/08/resources/input_small1.txt
new file mode 100644
index 0000000..9029a1b
--- /dev/null
+++ b/2023/08/resources/input_small1.txt
@@ -0,0 +1,9 @@
+RL
+
+AAA = (BBB, CCC)
+BBB = (DDD, EEE)
+CCC = (ZZZ, GGG)
+DDD = (DDD, DDD)
+EEE = (EEE, EEE)
+GGG = (GGG, GGG)
+ZZZ = (ZZZ, ZZZ)
diff --git a/2023/08/resources/input_small2.txt b/2023/08/resources/input_small2.txt
new file mode 100644
index 0000000..7d1b58d
--- /dev/null
+++ b/2023/08/resources/input_small2.txt
@@ -0,0 +1,5 @@
+LLR
+
+AAA = (BBB, BBB)
+BBB = (AAA, ZZZ)
+ZZZ = (ZZZ, ZZZ)
diff --git a/2023/08/resources/input_small3.txt b/2023/08/resources/input_small3.txt
new file mode 100644
index 0000000..abd2095
--- /dev/null
+++ b/2023/08/resources/input_small3.txt
@@ -0,0 +1,10 @@
+LR
+
+AAA = (AAB, XXX)
+AAB = (XXX, AAZ)
+AAZ = (AAB, XXX)
+BBA = (BBB, XXX)
+BBB = (BBC, BBC)
+BBC = (BBZ, BBZ)
+BBZ = (BBB, BBB)
+XXX = (XXX, XXX)
diff --git a/2023/08/src/part1.cpp b/2023/08/src/part1.cpp
new file mode 100644
index 0000000..9585536
--- /dev/null
+++ b/2023/08/src/part1.cpp
@@ -0,0 +1,70 @@
+#include <iostream>
+#include <fstream>
+#include <sstream>
+#include <unordered_map>
+#include <vector>
+
+#include "util.h"
+
+using Moves = std::vector<bool>;
+using Map = std::unordered_map<int,std::pair<int,int>>;
+
+constexpr char EQUAL[] = "=";
+
+int encode(std::string str)
+{
+    int res{};
+    for (unsigned char c : str)
+    {
+        if ('A' <= c and c <= 'Z')
+        {
+            res *= 1 + 'Z' - 'A';
+            res += c - 'A';
+        }
+    }
+    return res;
+}
+
+std::pair<Moves,Map> parse(const char* path)
+{
+    Map map{};
+    Moves moves{};
+
+    std::ifstream input{ path };
+    if (input.is_open())
+    {
+        std::string line;
+        std::getline(input,line);
+
+        moves.resize(line.size());
+        std::transform(line.cbegin(), line.cend(),
+            moves.begin(), [](unsigned char c) { return c == 'L'; });
+
+        std::string from, tol, tor;
+        while (not std::getline(input,line).eof())
+        {
+            if (line.empty()) continue;
+
+            std::istringstream in{ line };
+            in >> from >> util::skip<EQUAL> >> tol >> tor;
+            map.insert({ encode(from), { encode(tol), encode(tor) } });
+        }
+    }
+    input.close();
+
+    return { std::move(moves), std::move(map) };
+}
+
+int main(int argc, char* argv[])
+{
+    int answer{};
+
+    auto [moves, map] = parse(argv[1]);
+
+    for (int pos = encode("AAA");
+         pos != encode("ZZZ");
+         pos = moves[answer++ % moves.size()] ? map[pos].first : map[pos].second);
+
+    std::cout << answer << std::endl;
+    return 0;
+}
diff --git a/2023/08/src/part2.cpp b/2023/08/src/part2.cpp
new file mode 100644
index 0000000..23b456d
--- /dev/null
+++ b/2023/08/src/part2.cpp
@@ -0,0 +1,78 @@
+#include <fstream>
+#include <iostream>
+#include <sstream>
+#include <unordered_map>
+#include <vector>
+#include <numeric>
+
+#include "util.h"
+
+using Pos = std::string;
+using Moves = std::vector<bool>;
+using Map = std::unordered_map<Pos,std::pair<Pos,Pos>>;
+
+constexpr char EQUAL[] = "=";
+
+std::pair<Moves,Map> parse(const char* path)
+{
+    Map map{};
+    Moves moves{};
+
+    std::ifstream input{ path };
+    if (input.is_open())
+    {
+        std::string line;
+        std::getline(input,line);
+
+        moves.resize(line.size());
+        std::transform(line.cbegin(), line.cend(),
+            moves.begin(), [](unsigned char c) { return c == 'L'; });
+
+        std::string from, tol, tor;
+        while (not std::getline(input,line).eof())
+        {
+            if (line.empty()) continue;
+
+            std::istringstream in{ line };
+            in >> from >> util::skip<EQUAL> >> tol >> tor;
+            tol.erase(0,1); tol.pop_back();
+            tor.pop_back();
+            map.insert({ from, { tol, tor } });
+        }
+    }
+    input.close();
+
+    return { std::move(moves), std::move(map) };
+}
+
+long long compute(const Map& map, const Moves& moves, Pos pos)
+{
+    long long idx{};
+
+    while (pos[2] != 'Z')
+    {
+        bool left = moves[idx++ % moves.size()];
+        pos = left ? map.at(pos).first : map.at(pos).second; 
+    }
+
+    return idx;
+}
+
+int main(int argc, char* argv[])
+{
+    long long answer{ 1 };
+
+    auto [moves, map] = parse(argv[1]);
+
+    for (const auto& kv : map)
+    {
+        if (kv.first[2] == 'A')
+        {
+            answer = std::lcm(answer, compute(map, moves, kv.first));
+        }
+    }
+
+    std::cout << answer << std::endl;
+    return 0;
+}
+