aoc 2018, days 13 & 14aoc-2018

2 files changed, 305 insertions, 0 deletions

diff --git a/2018/src/day13.cpp b/2018/src/day13.cpp
new file mode 100644
index 0000000..c764f7f
--- /dev/null
+++ b/2018/src/day13.cpp
@@ -0,0 +1,217 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+enum class Direction : uint8_t {
+        Up,
+        Right,
+        Down,
+        Left
+};
+
+struct Cart {
+        size_t        x;
+        size_t        y;
+        Direction     direction;
+        unsigned long intersection{};
+};
+
+using Grid  = vector<string>;
+using Carts = vector<Cart>;
+
+tuple<Grid, Carts>
+read_file(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+
+        Grid  data;
+        Carts carts;
+
+        size_t y = 0;
+        for ( string line; getline(file, line); ) {
+                for ( size_t x = 0; x != line.size(); ++x ) {
+                        using enum Direction;
+
+                        const char chr = line[x];
+                        if ( chr == '^' || chr == 'v' ) {
+                                carts.emplace_back(x, y, chr == '^' ? Up : Down);
+                        }
+                        else if ( chr == '<' || chr == '>' ) {
+                                carts.emplace_back(x, y, chr == '<' ? Left : Right);
+                        }
+                }
+                data.emplace_back(line);
+                ++y;
+        }
+
+        return { data, carts };
+}
+
+void
+sort_carts(Carts& carts)
+{
+        ranges::sort(carts,
+                     [](auto& lhs, auto& rhs) {
+                             return tie(lhs.y, lhs.x) < tie(rhs.y, rhs.x);
+                     });
+}
+
+void
+move_cart(Cart& cart)
+{
+        using enum Direction;
+
+        switch ( cart.direction ) {
+        case Up:
+                --cart.y;
+                break;
+        case Right:
+                ++cart.x;
+                break;
+        case Down:
+                ++cart.y;
+                break;
+        case Left:
+                --cart.x;
+                break;
+        }
+}
+
+void
+apply_direction_rules(const Grid& grid, Cart& cart)
+{
+        using enum Direction;
+
+        const char chr = grid[cart.y][cart.x];
+        switch ( chr ) {
+        case '/':
+                if ( cart.direction == Up ) {
+                        cart.direction = Right;
+                }
+                else if ( cart.direction == Right ) {
+                        cart.direction = Up;
+                }
+                else if ( cart.direction == Down ) {
+                        cart.direction = Left;
+                }
+                else if ( cart.direction == Left ) {
+                        cart.direction = Down;
+                }
+                break;
+        case '\\':
+                if ( cart.direction == Up ) {
+                        cart.direction = Left;
+                }
+                else if ( cart.direction == Right ) {
+                        cart.direction = Down;
+                }
+                else if ( cart.direction == Down ) {
+                        cart.direction = Right;
+                }
+                else if ( cart.direction == Left ) {
+                        cart.direction = Up;
+                }
+                break;
+        case '+':
+                switch ( cart.intersection++ % 3 ) {
+                case 0:
+                        cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 3) % 4);
+                        break;
+                case 2:
+                        cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 1) % 4);
+                        break;
+                default:
+                        break;
+                };
+                break;
+        default:
+                break;
+        }
+}
+
+void
+part1(const Grid& grid, Carts carts)
+{
+        while ( true ) {
+                sort_carts(carts);
+
+                for ( size_t i = 0; i != carts.size(); ++i ) {
+                        auto& cart = carts[i];
+
+                        move_cart(cart);
+                        apply_direction_rules(grid, cart);
+
+                        for ( size_t j = 0; j != carts.size(); ++j ) {
+                                if ( i == j ) {
+                                        continue;
+                                }
+
+                                const auto& other = carts[j];
+
+                                if ( cart.x == other.x && cart.y == other.y ) {
+                                        cout << "Part 1: " << cart.x << ',' << cart.y << '\n';
+                                        return;
+                                }
+                        }
+                }
+        }
+}
+
+void
+part2(const Grid& grid, Carts carts)
+{
+        while ( true ) {
+                sort_carts(carts);
+
+                vector<size_t> carts_to_be_removed;
+
+                for ( size_t i = 0; i != carts.size(); ++i ) {
+                        auto& cart = carts[i];
+
+                        move_cart(cart);
+                        apply_direction_rules(grid, cart);
+
+                        for ( size_t j = 0; j != carts.size(); ++j ) {
+                                if ( i == j ) {
+                                        continue;
+                                }
+
+                                const auto& other = carts[j];
+
+                                if ( cart.x == other.x && cart.y == other.y ) {
+                                        carts_to_be_removed.emplace_back(i);
+                                        carts_to_be_removed.emplace_back(j);
+                                }
+                        }
+                }
+
+                // remove carts
+                ranges::sort(carts_to_be_removed);
+                ranges::reverse(carts_to_be_removed);
+
+                for ( auto num: carts_to_be_removed ) {
+                        carts.erase(carts.begin() + static_cast<long>(num));
+                }
+
+                if ( carts.size() == 1 ) {
+                        cout << "Part 2: " << carts[0].x << ',' << carts[0].y << '\n';
+                        return;
+                }
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        auto [grid, carts] = read_file("data/day13.txt");
+        part1(grid, carts);
+        part2(grid, carts);
+}
diff --git a/2018/src/day14.cpp b/2018/src/day14.cpp
new file mode 100644
index 0000000..95d0717
--- /dev/null
+++ b/2018/src/day14.cpp
@@ -0,0 +1,88 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+void
+part1(const size_t n)
+{
+        vector<size_t> v{ 3, 7 };
+        size_t         first  = 0;
+        size_t         second = 1;
+
+        while ( v.size() < n + 10 ) {
+                auto value = v[first] + v[second];
+                if ( value >= 10 ) {
+                        v.emplace_back(1);
+                        value -= 10;
+                }
+                v.emplace_back(value);
+
+                first  = (first + v[first] + 1) % v.size();
+                second = (second + v[second] + 1) % v.size();
+        }
+
+        cout << "Part 1: ";
+        for ( size_t i = n; i != n + 10; ++i ) {
+                cout << v[i];
+        }
+        cout << '\n';
+}
+
+void
+part2(const size_t n)
+{
+        vector<size_t> v{ 3, 7 };
+        size_t         first  = 0;
+        size_t         second = 1;
+
+        const size_t len = to_string(n).length();
+
+        auto check = [&] {
+                if ( v.size() < len ) {
+                        return false;
+                }
+
+                size_t value = 0;
+                for ( size_t i = len; i > 0; --i ) {
+                        value *= 10;
+                        value += v[v.size() - i];
+                }
+
+                return value == n;
+        };
+
+        for ( ;; ) {
+                auto value = v[first] + v[second];
+                if ( value >= 10 ) {
+                        v.emplace_back(1);
+                        if ( check() ) {
+                                break;
+                        }
+
+                        value -= 10;
+                }
+
+                v.emplace_back(value);
+                if ( check() ) {
+                        break;
+                }
+
+                first  = (first + v[first] + 1) % v.size();
+                second = (second + v[second] + 1) % v.size();
+        }
+
+        cout << "Part 2: " << v.size() - len << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        const size_t input = 607331;
+        part1(input);
+        part2(input);
+}