From 8c96639ec1f6757570510fc27f1c5fabece35eaf Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 16 Nov 2025 13:23:34 +0100
Subject: aoc 2018, days 1-11

---
 2018/src/day09.cpp | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 113 insertions(+)
 create mode 100644 2018/src/day09.cpp

(limited to '2018/src/day09.cpp')

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);
+}
-- 
cgit v1.3