aoc 2018, days 12

1 files changed, 127 insertions, 0 deletions

diff --git a/2018/src/day12.cpp b/2018/src/day12.cpp
new file mode 100644
index 0000000..21d74b2
--- /dev/null
+++ b/2018/src/day12.cpp
@@ -0,0 +1,127 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <string>
+#include <unordered_set>
+
+using namespace std;
+
+namespace {
+
+using Plants = unordered_set<long>;
+using Rules  = map<string, char>;
+using Puzzle = tuple<Plants, Rules>;
+
+Puzzle
+read_file(const filesystem::path& filename)
+{
+        fstream file{ filename };
+
+        string line;
+        getline(file, line);
+        line.erase(0, line.find(": ") + 2);
+
+        Plants plants;
+        for ( size_t idx = 0; idx != line.length(); ++idx ) {
+                if ( line.at(idx) == '#' ) {
+                        plants.insert(static_cast<long>(idx));
+                }
+        }
+
+        getline(file, line);
+
+        Rules rules;
+        while ( getline(file, line) ) {
+                auto lhs = line.substr(0, 5);
+                auto rhs = line.substr(9);
+
+                rules[lhs] = rhs.at(0);
+        }
+
+        return { plants, rules };
+}
+
+Plants
+update(const Plants& current, const Rules& rules)
+{
+        auto [min, max] = ranges::minmax(current);
+
+        Plants next;
+
+        for ( auto i = min - 2; i <= max + 2; ++i ) {
+                string pattern;
+                pattern += current.contains(i - 2) ? '#' : '.';
+                pattern += current.contains(i - 1) ? '#' : '.';
+                pattern += current.contains(i) ? '#' : '.';
+                pattern += current.contains(i + 1) ? '#' : '.';
+                pattern += current.contains(i + 2) ? '#' : '.';
+
+                if ( rules.contains(pattern) && rules.at(pattern) == '#' ) {
+                        next.insert(i);
+                }
+        }
+
+        return next;
+}
+
+void
+part1(const Puzzle& puzzle)
+{
+        auto [state, rules] = puzzle;
+
+        for ( int i = 0; i != 20; ++i ) {
+                state = update(state, rules);
+        }
+
+        long sum = 0;
+        for ( const auto pos: state ) {
+                sum += pos;
+        }
+        cout << "Part 1: " << sum << '\n';
+}
+
+void
+part2(const Puzzle& puzzle)
+{
+        auto [state, rules] = puzzle;
+
+        auto to_string = [&] {
+                string result;
+
+                auto [min, max] = ranges::minmax(state);
+                for ( auto pos = min; pos <= max; ++pos ) {
+                        result += (state.contains(pos) ? '#' : '.');
+                }
+
+                return result;
+        };
+
+        unordered_set<string> seen;
+        for ( long shift = 50000000000;; --shift ) {
+                auto pattern = to_string();
+
+                if ( seen.contains(pattern) ) {
+                        long sum = 0;
+                        for ( const auto pos: state ) {
+                                sum += pos + shift;
+                        }
+                        cout << "Part 2: " << sum << '\n';
+                        return;
+                }
+
+                seen.insert(pattern);
+
+                state = update(state, rules);
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        auto puzzle = read_file("data/day12.txt");
+        part1(puzzle);
+        part2(puzzle);
+}