aoc 2018, days 1-11

11 files changed, 1303 insertions, 0 deletions

diff --git a/2018/src/day01.cpp b/2018/src/day01.cpp
new file mode 100644
index 0000000..d57a187
--- /dev/null
+++ b/2018/src/day01.cpp
@@ -0,0 +1,58 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <numeric>
+#include <unordered_set>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<long>
+read_file(const filesystem::path& filename)
+{
+        ifstream     file{ filename };
+        vector<long> values;
+
+        for ( long value = 0; file >> value; ) {
+                values.emplace_back(value);
+        }
+
+        return values;
+}
+
+void
+part1(const vector<long>& values)
+{
+        auto sum = accumulate(values.begin(), values.end(), 0L);
+        cout << "Part1: " << sum << '\n';
+}
+
+void
+part2(const vector<long>& values)
+{
+        unordered_set<long> seen;
+
+        long sum = 0;
+        for ( size_t idx = 0;; ++idx ) {
+                sum += values.at(idx % values.size());
+
+                if ( seen.contains(sum) ) {
+                        cout << "Part2: " << sum << '\n';
+                        return;
+                }
+
+                seen.emplace(sum);
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        auto values = read_file("data/day01.txt");
+        part1(values);
+        part2(values);
+}
diff --git a/2018/src/day02.cpp b/2018/src/day02.cpp
new file mode 100644
index 0000000..5dc6c7f
--- /dev/null
+++ b/2018/src/day02.cpp
@@ -0,0 +1,87 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<string>
+read_lines(const filesystem::path& filename)
+{
+        ifstream       file{ filename };
+        vector<string> lines;
+
+        for ( string line; getline(file, line); ) {
+                lines.emplace_back(line);
+        }
+
+        return lines;
+}
+
+void
+part1(const vector<string>& lines)
+{
+        int twos   = 0;
+        int threes = 0;
+        for ( const auto& line: lines ) {
+                map<char, int> foo;
+                for ( const auto chr: line ) {
+                        foo[chr]++;
+                }
+
+                set<int> counts;
+                for ( const auto& [chr, count]: foo ) {
+                        counts.insert(count);
+                }
+
+                if ( counts.contains(2) ) {
+                        ++twos;
+                }
+                if ( counts.contains(3) ) {
+                        ++threes;
+                }
+        }
+        cout << "Part 1: " << twos * threes << '\n';
+}
+
+void
+part2(const vector<string>& lines)
+{
+        for ( size_t i = 0; i != lines.size(); ++i ) {
+                for ( size_t j = i + 1; j != lines.size(); ++j ) {
+                        const auto& lhs = lines.at(i);
+                        const auto& rhs = lines.at(j);
+
+                        if ( lhs.length() != rhs.length() ) {
+                                throw runtime_error("invalid data");
+                        }
+
+                        string result;
+                        for ( size_t k = 0; k != lhs.length(); ++k ) {
+                                if ( lhs[k] == rhs[k] ) {
+                                        result += lhs[k];
+                                }
+                        }
+
+                        if ( result.length() + 1 == lhs.length() ) {
+                                cout << "Part 2: " << result << '\n';
+                                return;
+                        }
+                }
+        }
+}
+
+} // namespace
+
+int
+main()
+{
+        auto lines = read_lines("data/day02.txt");
+        part1(lines);
+        part2(lines);
+}
diff --git a/2018/src/day03.cpp b/2018/src/day03.cpp
new file mode 100644
index 0000000..bed3acb
--- /dev/null
+++ b/2018/src/day03.cpp
@@ -0,0 +1,95 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Claim {
+        int id;
+        int left;
+        int top;
+        int width;
+        int height;
+};
+
+#if 0
+ostream&
+operator<<(ostream& ostrm, const Claim& claim)
+{
+        ostrm << "id: " << claim.id
+              << " (" << claim.left << ", " << claim.top << ": " << claim.width << "x" << claim.height;
+        return ostrm;
+}
+#endif
+
+vector<Claim>
+read_file(const filesystem::path& filename)
+{
+        ifstream      file{ filename };
+        vector<Claim> claims;
+
+        regex  pattern(R"#((\d+) @ (\d+),(\d+): (\d+)x(\d+))#");
+        smatch match;
+
+        for ( string line; getline(file, line); ) {
+                if ( !regex_search(line, match, pattern) ) {
+                        continue;
+                }
+
+                Claim claim{};
+                claim.id     = stoi(match[1]);
+                claim.left   = stoi(match[2]);
+                claim.top    = stoi(match[3]);
+                claim.width  = stoi(match[4]);
+                claim.height = stoi(match[5]);
+
+                claims.emplace_back(claim);
+        }
+
+        return claims;
+}
+
+void
+solve(const vector<Claim>& claims)
+{
+        map<tuple<int, int>, vector<int>> fabric;
+        set<int>                          allIds;
+
+        for ( const auto& claim: claims ) {
+                for ( int x = claim.left; x < claim.left + claim.width; ++x ) {
+                        for ( int y = claim.top; y < claim.top + claim.height; ++y ) {
+                                fabric[{ x, y }].emplace_back(claim.id);
+                        }
+                }
+                allIds.emplace(claim.id);
+        }
+
+        int overlapCount = 0;
+        for ( const auto& [pos, ids]: fabric ) {
+                if ( ids.size() > 1 ) {
+                        ++overlapCount;
+                        for ( const auto& id: ids ) {
+                                allIds.erase(id);
+                        }
+                }
+        }
+
+        cout << "Part 1: " << overlapCount << '\n';
+        cout << "Part 2: " << *allIds.begin() << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto claims = read_file("data/day03.txt");
+        solve(claims);
+}
diff --git a/2018/src/day04.cpp b/2018/src/day04.cpp
new file mode 100644
index 0000000..ea3c69f
--- /dev/null
+++ b/2018/src/day04.cpp
@@ -0,0 +1,135 @@
+#include <algorithm>
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Record {
+        int  guard_id;
+        long start_sleep;
+        long stop_sleep;
+};
+
+long
+to_timestamp(const string& line)
+{
+        long year = stol(line.substr(1, 4));
+        long mon  = stol(line.substr(6, 2));
+        long day  = stol(line.substr(9, 2));
+        long hour = stol(line.substr(12, 2));
+        long min  = stol(line.substr(15, 2));
+
+        auto timestamp = (year * 100'000'000) + (mon * 1'000'000) + (day * 10'000) + (hour * 100) + min; // NOLINT
+
+        return timestamp;
+}
+
+vector<Record>
+read_file(const filesystem::path& filename)
+{
+        ifstream       file{ filename };
+        vector<string> lines;
+
+        for ( string line; getline(file, line); ) {
+                lines.emplace_back(line);
+        }
+
+        ranges::sort(lines);
+
+        vector<Record> records;
+
+        int  guard       = -1;
+        long start_sleep = -1;
+        long stop_sleep  = -1;
+        for ( const auto& line: lines ) {
+                if ( line.find(" Guard #") != string::npos ) {
+                        guard = stoi(line.substr(26));
+                }
+                else if ( line.find(" falls asleep") != string::npos ) {
+                        start_sleep = to_timestamp(line);
+                }
+                else if ( line.find(" wakes up") != string::npos ) {
+                        stop_sleep = to_timestamp(line);
+                        records.emplace_back(guard, start_sleep, stop_sleep);
+                }
+        }
+
+        return records;
+}
+
+void
+part1(const vector<Record>& records)
+{
+        map<int, long> sleep_amounts;
+
+        for ( const auto& record: records ) {
+                sleep_amounts[record.guard_id] += record.stop_sleep - record.start_sleep;
+        }
+
+        auto max_amount = ranges::max_element(sleep_amounts,
+                                              [](const auto& lhs, const auto& rhs) {
+                                                      return lhs.second < rhs.second;
+                                              });
+
+        map<long, unsigned> sleep_counts;
+
+        for ( const auto& record: records ) {
+                if ( record.guard_id != max_amount->first ) {
+                        continue;
+                }
+
+                for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) {
+                        sleep_counts[timestamp % 10'000]++;
+                }
+        }
+
+        auto max_count = ranges::max_element(sleep_counts,
+                                             [](const auto& lhs, const auto& rhs) {
+                                                     return lhs.second < rhs.second;
+                                             });
+
+        cout << "Part 1: " << max_amount->first * (max_count->first % 100) << '\n';
+}
+
+void
+part2(const vector<Record>& records)
+{
+        map<int, map<long, unsigned>> sleep_counts;
+
+        for ( const auto& record: records ) {
+                for ( auto timestamp = record.start_sleep; timestamp != record.stop_sleep; ++timestamp ) {
+                        sleep_counts[record.guard_id][timestamp % 10'000]++;
+                }
+        }
+
+        int      found_guard = -1;
+        long     found_min   = -1;
+        unsigned max_count   = 0;
+        for ( const auto& [id, times]: sleep_counts ) {
+                for ( const auto& [min, count]: times ) {
+                        if ( count > max_count ) {
+                                max_count   = count;
+                                found_guard = id;
+                                found_min   = min % 100;
+                        }
+                }
+        }
+
+        cout << "Part 2: " << found_guard * found_min << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto records = read_file("data/day04.txt");
+        part1(records);
+        part2(records);
+}
diff --git a/2018/src/day05.cpp b/2018/src/day05.cpp
new file mode 100644
index 0000000..9de484d
--- /dev/null
+++ b/2018/src/day05.cpp
@@ -0,0 +1,101 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <string>
+
+using namespace std;
+
+namespace {
+
+string
+read_line(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+        string   line;
+        getline(file, line);
+        return line;
+}
+
+bool
+xorEqual(char lhs, char rhs)
+{
+        return (lhs ^ (1 << 5)) == rhs;
+}
+
+#if 0
+void
+part1(string str)
+{
+        size_t idx = 1;
+        while ( idx < str.length() ) {
+                if ( xorEqual(str[idx - 1], str[idx]) ) {
+                        str.erase(idx - 1, 2);
+                        idx = 1;
+                }
+                else {
+                        ++idx;
+                }
+        }
+
+        cout << "Part 1: " << str.length() << '\n';
+}
+#endif
+
+void
+part1_opti(string_view str)
+{
+        string result;
+
+        for ( const auto chr: str ) {
+                if ( !result.empty() && xorEqual(result.back(), chr) ) {
+                        result.pop_back();
+                }
+                else {
+                        result.push_back(chr);
+                }
+        }
+
+        cout << "Part 1: " << result.length() << '\n';
+}
+
+void
+part2(string_view str)
+{
+        size_t min_length = str.size();
+        for ( auto ch = 'a'; ch != 'z'; ++ch ) {
+                string result;
+
+                for ( const auto chr: str ) {
+                        if ( tolower(chr) == ch ) {
+                                // nichts
+                        }
+                        else if ( !result.empty() && xorEqual(result.back(), chr) ) {
+                                result.pop_back();
+                        }
+                        else {
+                                result.push_back(chr);
+                        }
+                }
+                min_length = min(min_length, result.length());
+        }
+
+        cout << "Part 2: " << min_length << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto line = read_line("data/day05.txt");
+        // part1(line);
+        part1_opti(line);
+        part2(line);
+        /*
+        cout << reduce("aA") << '\n';
+        cout << reduce("abBA") << '\n';
+        cout << reduce("abAB") << '\n';
+        cout << reduce("aabAAB") << '\n';
+        cout << reduce("dabAcCaCBAcCcaDA") << '\n';
+        */
+}
diff --git a/2018/src/day06.cpp b/2018/src/day06.cpp
new file mode 100644
index 0000000..8701cbe
--- /dev/null
+++ b/2018/src/day06.cpp
@@ -0,0 +1,152 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <tuple>
+
+using namespace std;
+
+namespace {
+
+using Point = tuple<int, int>;
+
+set<Point>
+read_file(const filesystem::path& filename)
+{
+        ifstream   file{ filename };
+        set<Point> points;
+
+        int  x{};
+        int  y{};
+        char sep{};
+
+        while ( file >> x >> sep >> y ) {
+                points.insert({ x, y });
+        }
+
+        return points;
+}
+
+void
+getBoundingBox(const set<Point>& points, Point& topLeft, Point& bottomRight)
+{
+        auto minX = numeric_limits<int>::max();
+        auto minY = numeric_limits<int>::max();
+        auto maxX = numeric_limits<int>::min();
+        auto maxY = numeric_limits<int>::min();
+
+        for ( const auto [x, y]: points ) {
+                minX = min(minX, x);
+                minY = min(minY, y);
+                maxX = max(maxX, x);
+                maxY = max(maxY, y);
+        }
+
+        topLeft     = { minX, minY };
+        bottomRight = { maxX, maxY };
+}
+
+int
+manhattanDistance(const Point& lhs, const Point& rhs)
+{
+        int distance = abs(get<0>(lhs) - get<0>(rhs)) + abs(get<1>(lhs) - get<1>(rhs));
+
+        return distance;
+}
+
+void
+part1(const set<Point>& points)
+{
+        Point topLeft{};
+        Point bottomRight{};
+        getBoundingBox(points, topLeft, bottomRight);
+
+        const auto [minX, minY] = topLeft;
+        const auto [maxX, maxY] = bottomRight;
+
+        map<Point, int> areaCount;
+        set<Point>      infinite;
+
+        static const int offset = 1;
+
+        for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
+                for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
+                        int   bestDistance = numeric_limits<int>::max();
+                        Point bestPoint{};
+                        bool  tie = false;
+
+                        for ( const auto& point: points ) {
+                                int distance = manhattanDistance(point, { posX, posY });
+                                if ( distance < bestDistance ) {
+                                        bestDistance = distance;
+                                        bestPoint    = point;
+                                        tie          = false;
+                                }
+                                else if ( distance == bestDistance ) {
+                                        tie = true;
+                                }
+                        }
+
+                        if ( !tie ) {
+                                areaCount[bestPoint]++;
+
+                                if ( posX < minX || posX > maxX || posY < minY || posY > maxY ) {
+                                        infinite.insert(bestPoint);
+                                }
+                        }
+                }
+        }
+
+        int maxSize = 0;
+        for ( const auto& [point, size]: areaCount ) {
+                if ( infinite.contains(point) ) {
+                        continue;
+                }
+                maxSize = max(maxSize, size);
+        }
+
+        cout << "Part 1: " << maxSize << '\n';
+}
+
+void
+part2(const set<Point>& points, const int threshold)
+{
+        Point topLeft{};
+        Point bottomRight{};
+        getBoundingBox(points, topLeft, bottomRight);
+
+        const auto [minX, minY] = topLeft;
+        const auto [maxX, maxY] = bottomRight;
+
+        static const int offset = 100;
+
+        unsigned int regionSize = 0;
+
+        for ( auto posX = minX - offset; posX <= maxX + offset; ++posX ) {
+                for ( auto posY = minY - offset; posY <= maxY + offset; ++posY ) {
+                        int sum = 0;
+
+                        for ( const auto& point: points ) {
+                                int distance = manhattanDistance(point, { posX, posY });
+                                sum += distance;
+                        }
+
+                        if ( sum < threshold ) {
+                                ++regionSize;
+                        }
+                }
+        }
+
+        cout << "Part 2: " << regionSize << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto points = read_file("data/day06.txt");
+        part1(points);
+        part2(points, 10000);
+}
diff --git a/2018/src/day07.cpp b/2018/src/day07.cpp
new file mode 100644
index 0000000..e6147d6
--- /dev/null
+++ b/2018/src/day07.cpp
@@ -0,0 +1,194 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<string>
+split(const string& line)
+{
+        stringstream   strm{ line };
+        vector<string> words;
+
+        for ( string word; getline(strm, word, ' '); ) {
+                words.emplace_back(word);
+        }
+
+        return words;
+}
+
+map<string, set<string>>
+read_file(const filesystem::path& filename)
+{
+        ifstream                 file{ filename };
+        map<string, set<string>> graph;
+
+        for ( string line; getline(file, line); ) {
+                auto words = split(line);
+                graph[words.at(1)].emplace(words.at(7));
+        }
+
+        return graph;
+}
+
+vector<string>
+topologicalSort(const map<string, set<string>>& graph)
+{
+        map<string, int> indegree;
+
+        // Eingangsgrade initialisieren
+        for ( const auto& [node, neighbors]: graph ) {
+                if ( !indegree.contains(node) ) {
+                        indegree[node] = 0;
+                }
+                for ( const auto& neighbor: neighbors ) {
+                        indegree[neighbor]++;
+                }
+        }
+
+        // Queue mit Knoten, deren Eingangsgrad 0 ist
+        priority_queue<string, vector<string>, greater<>> queue;
+        for ( const auto& [node, deg]: indegree ) {
+                if ( deg == 0 ) {
+                        queue.push(node);
+                }
+        }
+
+        vector<string> sorted;
+
+        // Kahn's Algorithmus
+        while ( !queue.empty() ) {
+                string node = queue.top();
+                queue.pop();
+
+                sorted.push_back(node);
+
+                if ( !graph.contains(node) ) {
+                        continue;
+                }
+
+                for ( const auto& neighbor: graph.at(node) ) {
+                        indegree[neighbor]--;
+                        if ( indegree[neighbor] == 0 ) {
+                                queue.push(neighbor);
+                        }
+                }
+        }
+
+        // Prüfen auf Zyklus
+        if ( sorted.size() != indegree.size() ) {
+                throw runtime_error("Zyklus im Graph gefunden! Keine topologische Sortierung möglich.");
+        }
+
+        return sorted;
+}
+
+void
+part1(const map<string, set<string>>& graph)
+{
+        auto sorted = topologicalSort(graph);
+
+        cout << "Part 1: ";
+        ranges::copy(sorted, ostream_iterator<string>(cout));
+        cout << '\n';
+}
+
+void
+part2(const map<string, set<string>>& graph, const int workers, const int base)
+{
+        map<string, int> indegree;
+
+        // Eingangsgrade initialisieren
+        for ( const auto& [node, neighbors]: graph ) {
+                if ( !indegree.contains(node) ) {
+                        indegree[node] = 0;
+                }
+                for ( const auto& neighbor: neighbors ) {
+                        indegree[neighbor]++;
+                }
+        }
+
+        set<string> available;
+        for ( const auto& [node, deg]: indegree ) {
+                if ( deg == 0 ) {
+                        available.insert(node);
+                }
+        }
+
+        set<pair<int, string>> finishing;
+
+        int active_workers = 0;
+        int time           = 0;
+
+        while ( !indegree.empty() ) {
+                while ( !finishing.empty() && finishing.begin()->first == time ) {
+                        auto [finish_time, node] = *finishing.begin();
+                        finishing.erase(finishing.begin());
+
+                        active_workers--;
+
+                        indegree.erase(node);
+
+                        if ( !graph.contains(node) ) {
+                                continue;
+                        }
+
+                        for ( const auto& neighbor: graph.at(node) ) {
+                                indegree[neighbor]--;
+                                if ( indegree[neighbor] == 0 ) {
+                                        available.insert(neighbor);
+                                }
+                        }
+                }
+
+                while ( active_workers < workers && !available.empty() ) {
+                        auto node = *available.begin();
+                        available.erase(available.begin());
+
+                        int duration    = base + (node.at(0) - 'A' + 1);
+                        int finish_time = time + duration;
+
+                        finishing.emplace(finish_time, node);
+                        active_workers++;
+                }
+
+                if ( finishing.empty() ) {
+                        if ( available.empty() ) {
+                                break;
+                        }
+                        else {
+                                time++;
+                        }
+                }
+                else {
+                        time = finishing.begin()->first;
+                }
+        }
+
+        cout << "Part 2: " << time << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto graph = read_file("data/day07.txt");
+        try {
+                part1(graph);
+
+                static const int WORKERS = 5;
+                static const int BASE    = 60;
+                part2(graph, WORKERS, BASE);
+        }
+        catch ( exception& e ) {
+                cerr << "Fehler: " << e.what() << '\n';
+        }
+}
diff --git a/2018/src/day08.cpp b/2018/src/day08.cpp
new file mode 100644
index 0000000..9c2a093
--- /dev/null
+++ b/2018/src/day08.cpp
@@ -0,0 +1,88 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+vector<int>
+read_file(const filesystem::path& filename)
+{
+        ifstream    file{ filename };
+        vector<int> data;
+
+        for ( int number{}; file >> number; ) {
+                data.emplace_back(number);
+        }
+
+        return data;
+}
+
+void
+part1(const vector<int>& data)
+{
+        size_t idx = 0;
+        int    sum = 0;
+
+        function<void()> func = [&] {
+                auto count_child = data.at(idx++);
+                auto count_meta  = data.at(idx++);
+
+                while ( count_child-- > 0 ) {
+                        func();
+                }
+
+                while ( count_meta-- > 0 ) {
+                        sum += data.at(idx++);
+                }
+        };
+
+        func();
+
+        cout << "Part 1: " << sum << '\n';
+}
+
+void
+part2(const vector<int>& data)
+{
+        size_t idx = 0;
+
+        function<int()> func = [&] {
+                const auto count_child = data.at(idx++);
+                const auto count_meta  = data.at(idx++);
+
+                vector<int> child_values;
+                for ( int i = 0; i != count_child; ++i ) {
+                        child_values.emplace_back(func());
+                }
+
+                int value = 0;
+                for ( int i = 0; i != count_meta; ++i ) {
+                        auto meta = data.at(idx++);
+                        if ( count_child == 0 ) {
+                                value += meta;
+                        }
+                        else {
+                                meta--;
+                                if ( meta >= 0 && meta < count_child ) {
+                                        value += child_values[static_cast<size_t>(meta)];
+                                }
+                        }
+                }
+                return value;
+        };
+
+        cout << "Part 2: " << func() << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto data = read_file("data/day08.txt");
+        part1(data);
+        part2(data);
+}
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);
+}
diff --git a/2018/src/day10.cpp b/2018/src/day10.cpp
new file mode 100644
index 0000000..43de95c
--- /dev/null
+++ b/2018/src/day10.cpp
@@ -0,0 +1,137 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <regex>
+#include <set>
+#include <tuple>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+struct Point {
+        long x;
+        long y;
+        long vx;
+        long vy;
+};
+
+vector<Point>
+read_file(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+
+        static const regex pattern{ R"(position=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>\s*velocity=<\s*(-?\d+)\s*,\s*(-?\d+)\s*>)" };
+
+        vector<Point> data;
+        for ( string line; getline(file, line); ) {
+                smatch match;
+                if ( regex_match(line, match, pattern) ) {
+                        auto x  = stol(match[1]);
+                        auto y  = stol(match[2]);
+                        auto vx = stol(match[3]);
+                        auto vy = stol(match[4]);
+
+                        data.emplace_back(x, y, vx, vy);
+                }
+        }
+
+        return data;
+}
+
+void
+get_bounding_box(const vector<Point>& points, long& min_x, long& min_y, long& max_x, long& max_y)
+{
+        min_x = numeric_limits<long>::max();
+        min_y = numeric_limits<long>::max();
+        max_x = numeric_limits<long>::min();
+        max_y = numeric_limits<long>::min();
+
+        for ( const auto& point: points ) {
+                min_x = min(min_x, point.x);
+                min_y = min(min_y, point.y);
+                max_x = max(max_x, point.x);
+                max_y = max(max_y, point.y);
+        }
+}
+
+long
+bounding_area(const vector<Point>& points)
+{
+        long min_x = 0;
+        long min_y = 0;
+        long max_x = 0;
+        long max_y = 0;
+        get_bounding_box(points, min_x, min_y, max_x, max_y);
+        return 1L * (max_x - min_x + 1) * (max_y - min_y + 1);
+}
+
+void
+update(vector<Point>& points)
+{
+        for ( auto& point: points ) {
+                point.x += point.vx;
+                point.y += point.vy;
+        }
+}
+
+tuple<int, vector<Point>>
+get_best(vector<Point> points)
+{
+        auto best_area = numeric_limits<long>::max();
+
+        vector<Point> best;
+        int           best_t = 0;
+
+        for ( int i = 0; i != 100'000; ++i ) {
+                update(points);
+
+                auto area = bounding_area(points);
+                if ( area < best_area ) {
+                        best_area = area;
+                        best      = points;
+                        best_t    = i + 1;
+                }
+        }
+        return { best_t, best };
+}
+
+void
+print(const vector<Point>& points)
+{
+        set<tuple<long, long>> grid;
+        for ( const auto [x, y, vx, vy]: points ) {
+                grid.emplace(x, y);
+        }
+
+        long min_x = 0;
+        long min_y = 0;
+        long max_x = 0;
+        long max_y = 0;
+        get_bounding_box(points, min_x, min_y, max_x, max_y);
+
+        for ( long y = min_y; y <= max_y; ++y ) {
+                for ( long x = min_x; x <= max_x; ++x ) {
+                        cout << (grid.contains({ x, y }) ? '#' : ' ');
+                }
+                cout << '\n';
+        }
+}
+
+void
+solve(const vector<Point>& points)
+{
+        auto [time, best_points] = get_best(points);
+        print(best_points);
+        cout << "Part 2: " << time << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto data = read_file("data/day10.txt");
+        solve(data);
+}
diff --git a/2018/src/day11.cpp b/2018/src/day11.cpp
new file mode 100644
index 0000000..1f8f9e2
--- /dev/null
+++ b/2018/src/day11.cpp
@@ -0,0 +1,143 @@
+#include <iostream>
+#include <map>
+
+using namespace std;
+
+namespace {
+
+const int WIDTH  = 300;
+const int HEIGHT = 300;
+
+using Grid = map<tuple<int, int>, int>;
+
+int
+power_level(int x, int y, int serial)
+{
+        auto rack_id = x + 10;
+        auto level   = rack_id * y;
+        level += serial;
+        level *= rack_id;
+        level /= 100;
+        level %= 10;
+        level -= 5;
+        return level;
+}
+
+Grid
+build_grid(int serial)
+{
+        Grid grid;
+        for ( int x = 1; x <= WIDTH; ++x ) {
+                for ( int y = 1; y <= HEIGHT; ++y ) {
+                        grid[{ x, y }] = power_level(x, y, serial);
+                }
+        }
+        return grid;
+}
+
+int
+sum3x3(const Grid& grid, int x, int y)
+{
+        auto sum = 0;
+        for ( int dx = 0; dx != 3; ++dx ) {
+                for ( int dy = 0; dy != 3; ++dy ) {
+                        sum += grid.at({ x + dx, y + dy });
+                }
+        }
+        return sum;
+}
+
+void
+part1(const int serial)
+{
+        auto grid = build_grid(serial);
+
+        auto best_sum = numeric_limits<int>::min();
+        auto best_x   = 0;
+        auto best_y   = 0;
+
+        for ( int x = 1; x <= WIDTH - 2; ++x ) {
+                for ( int y = 1; y <= HEIGHT - 2; ++y ) {
+                        if ( auto sum = sum3x3(grid, x, y); sum > best_sum ) {
+                                best_sum = sum;
+                                best_x   = x;
+                                best_y   = y;
+                        }
+                }
+        }
+
+        cout << "Part 1: " << best_x << ',' << best_y << '\n';
+}
+
+Grid
+pre_process(const Grid& grid)
+{
+        Grid sat;
+
+        for ( int y = 1; y <= HEIGHT; ++y ) {
+                for ( int x = 1; x <= WIDTH; ++x ) {
+                        const auto a = grid.at({ x, y });
+                        const auto b = (x > 1) ? sat.at({ x - 1, y }) : 0;
+                        const auto c = (y > 1) ? sat.at({ x, y - 1 }) : 0;
+                        const auto d = (x > 1 && y > 1) ? sat.at({ x - 1, y - 1 }) : 0;
+
+                        sat[{ x, y }] = a + b + c - d;
+                }
+        }
+
+        return sat;
+}
+
+int
+get_safe(const Grid& grid, int x, int y)
+{
+        return (x < 1 || y < 1) ? 0 : grid.at({ x, y });
+}
+
+int
+square_sum(const Grid& grid, int x, int y, int s)
+{
+        int x2 = x + s - 1;
+        int y2 = y + s - 1;
+
+        return get_safe(grid, x2, y2) - get_safe(grid, x - 1, y2) - get_safe(grid, x2, y - 1) + get_safe(grid, x - 1, y - 1);
+}
+
+void
+part2(const int serial)
+{
+        static const int MAX_SIZE = 100;
+
+        auto grid = pre_process(build_grid(serial));
+
+        auto best_sum = numeric_limits<int>::min();
+        auto best_x   = 0;
+        auto best_y   = 0;
+        auto best_s   = 0;
+
+        for ( int s = 1; s <= MAX_SIZE; ++s ) {
+                for ( int x = 1; x <= WIDTH - s + 1; ++x ) {
+                        for ( int y = 1; y <= HEIGHT - s + 1; ++y ) {
+                                if ( auto sum = square_sum(grid, x, y, s); sum > best_sum ) {
+                                        best_sum = sum;
+                                        best_x   = x;
+                                        best_y   = y;
+                                        best_s   = s;
+                                }
+                        }
+                }
+        }
+
+        cout << "Part 2: " << best_x << ',' << best_y << "," << best_s << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        static const int SERIAL = 7989;
+
+        part1(SERIAL);
+        part2(SERIAL);
+}