aoc 2018, days 1-11

1 files changed, 113 insertions, 0 deletions

diff --git a/2018/src/day09.cpp b/2018/src/day09.cpp
new file mode 100644
index 0000000..d1b4eb0
--- /dev/null
+++ b/2018/src/day09.cpp
@@ -0,0 +1,113 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Marble {
+        explicit Marble(long score)
+            : score{ score }
+        {
+        }
+
+        Marble(long score, Marble* prev, Marble* next)
+            : score{ score }
+            , prev{ prev }
+            , next{ next }
+        {
+        }
+
+        [[nodiscard]]
+        Marble* insert_after_two(long value) const
+        {
+                auto* insert_after = this->next;
+
+                auto* new_marble = new Marble(value, insert_after, insert_after->next); // NOLINT
+
+                insert_after->next->prev = new_marble;
+                insert_after->next       = new_marble;
+
+                return new_marble;
+        }
+
+        [[nodiscard]]
+        pair<Marble*, long> remove_seventh_back()
+        {
+                auto* to_remove = this;
+                for ( int i = 0; i != 7; ++i ) {
+                        to_remove = to_remove->prev;
+                }
+
+                to_remove->prev->next = to_remove->next;
+                to_remove->next->prev = to_remove->prev;
+
+                auto* new_current = to_remove->next;
+                auto  score       = to_remove->score;
+
+                delete to_remove; // NOLINT
+
+                return { new_current, score };
+        }
+
+        long    score;
+        Marble* prev{ this };
+        Marble* next{ this };
+};
+
+long
+solve(const size_t players, const long last_marble)
+{
+        auto current = new Marble(0); // NOLINT
+
+        vector<long> scores(players, 0);
+        size_t       player = 0;
+
+        for ( long marble = 1; marble <= last_marble; ++marble ) {
+                if ( marble % 23 != 0 ) {
+                        current = current->insert_after_two(marble);
+                }
+                else {
+                        auto [new_current, removed_score] = current->remove_seventh_back();
+
+                        scores[player] += marble + removed_score;
+                        current = new_current;
+                }
+
+                player += 1;
+                player %= players;
+        }
+
+        Marble* start = current;
+        do {
+                Marble* next = start->next;
+                delete start; // NOLINT
+                start = next;
+        } while ( start != current );
+
+        return ranges::max(scores);
+}
+
+void
+part1(const size_t players, const long last_marble)
+{
+        cout << "Part 1: " << solve(players, last_marble) << '\n';
+}
+
+void
+part2(const size_t players, const long last_marble)
+{
+        cout << "Part 2: " << solve(players, last_marble * 100) << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        static const size_t players = 400;
+        static const long   points  = 71864;
+
+        part1(players, points);
+        part2(players, points);
+}