13 files changed, 745 insertions, 76 deletions

diff --git a/compile_flags.txt b/compile_flags.txt
index 966e06b..0000d86 100644
--- a/compile_flags.txt
+++ b/compile_flags.txt
@@ -5,3 +5,4 @@
 -Wdouble-promotion
 -pedantic
 -std=c++20
+-I/usr/local/include
diff --git a/makefile b/makefile
index a54e3aa..1849790 100644
--- a/makefile
+++ b/makefile
@@ -20,7 +20,11 @@ all: bin/day01 \
          bin/day18 \
          bin/day19 \
          bin/day20 \
-         bin/day21
+         bin/day21 \
+         bin/day22 \
+         bin/day23 \
+         bin/day24 \
+         bin/day25
 
 bin:
         mkdir $@
@@ -28,6 +32,9 @@ bin:
 bin/%: src/%.cpp | bin
         c++ $(CPPFLAGS) $^ -o $@
 
+bin/day24: src/day24.cpp | bin
+        c++ $(CPPFLAGS) -Wno-sign-conversion -I/usr/local/include $^ -L/usr/local/lib -lz3 -o $@
+
 clean:
         rm -rf bin
 
diff --git a/src/day04.cpp b/src/day04.cpp
index 8afcb2c..0d3e552 100644
--- a/src/day04.cpp
+++ b/src/day04.cpp
@@ -1,4 +1,3 @@
-#include <cctype>
 #include <fstream>
 #include <iostream>
 #include <set>
@@ -25,8 +24,8 @@ read_file(string_view filename)
 vector<string>
 split(const string& line, char sep)
 {
-        vector<string> parts{};
         stringstream   input{ line };
+        vector<string> parts;
 
         for ( string part; getline(input, part, sep); ) {
                 parts.emplace_back(part);
@@ -49,13 +48,12 @@ read_ints(const string& line)
         return container;
 }
 
-vector<unsigned long>
-build_data_set()
+auto
+build_data_set(string_view filename)
 {
-        const auto            lines = read_file("data/day04.txt");
-        vector<unsigned long> values{};
+        vector<unsigned long> values;
 
-        for ( const auto& line: lines ) {
+        for ( const auto& line: read_file(filename) ) {
                 const auto cards   = split(line, ':');
                 const auto numbers = split(cards[1], '|');
 
@@ -75,10 +73,10 @@ build_data_set()
 }
 
 void
-pass1()
+pass1(const vector<unsigned long>& values)
 {
         auto sum = 0U;
-        for ( auto value: build_data_set() ) {
+        for ( auto value: values ) {
                 if ( value != 0 ) {
                         sum += (1U << (value - 1));
                 }
@@ -88,10 +86,9 @@ pass1()
 }
 
 void
-pass2()
+pass2(const vector<unsigned long>& values)
 {
-        const auto values = build_data_set();
-        auto       count  = 0U;
+        auto count = 0U;
 
         function<void(size_t, size_t)> process = [&](size_t start, size_t end) -> void {
                 for ( ; start != end; ++start ) {
@@ -111,6 +108,7 @@ pass2()
 int
 main()
 {
-        pass1();
-        pass2();
+        const auto values = build_data_set("data/day04.txt");
+        pass1(values);
+        pass2(values);
 }
diff --git a/src/day05.cpp b/src/day05.cpp
index 92e39fc..42fda29 100644
--- a/src/day05.cpp
+++ b/src/day05.cpp
@@ -49,7 +49,7 @@ read_file(string_view filename)
 vector<string>
 split(const string& line, char sep)
 {
-        vector<string> parts{};
+        vector<string> parts;
         stringstream   input{ line };
 
         for ( string part; getline(input, part, sep); ) {
@@ -60,10 +60,8 @@ split(const string& line, char sep)
 }
 
 void
-part1()
+part1(const vector<string>& lines)
 {
-        auto lines = read_file("data/day05.txt");
-
         auto read_ints = [](const string& line) {
                 stringstream iss{ line };
                 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
@@ -71,8 +69,8 @@ part1()
 
         auto seeds = read_ints(lines[0].substr(6));
 
-        map<string, string>        category_mapping{};
-        map<string, vector<Entry>> range_mapping{};
+        map<string, string>        category_mapping;
+        map<string, vector<Entry>> range_mapping;
 
         // read blocks
         for ( size_t idx = 1; idx < lines.size(); ) {
@@ -84,7 +82,7 @@ part1()
 
                 category_mapping[parts[0]] = parts[2];
 
-                vector<Entry> mapping{};
+                vector<Entry> mapping;
 
                 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
                         auto values = read_ints(lines[idx]);
@@ -117,10 +115,8 @@ part1()
 }
 
 void
-part2()
+part2(const vector<string>& lines)
 {
-        auto lines = read_file("data/day05-sample1.txt");
-
         auto read_ints = [](const string& line) {
                 stringstream iss{ line };
                 return vector<long>{ istream_iterator<long>{ iss }, istream_iterator<long>{} };
@@ -128,8 +124,8 @@ part2()
 
         auto seeds = read_ints(lines[0].substr(6));
 
-        map<string, string>        category_mapping{};
-        map<string, vector<Entry>> range_mapping{};
+        map<string, string>        category_mapping;
+        map<string, vector<Entry>> range_mapping;
 
         // read blocks
         for ( size_t idx = 1; idx < lines.size(); ) {
@@ -141,7 +137,7 @@ part2()
 
                 category_mapping[parts[0]] = parts[2];
 
-                vector<Entry> mapping{};
+                vector<Entry> mapping;
 
                 for ( ; idx < lines.size() && !lines[idx].empty(); ++idx ) {
                         auto values = read_ints(lines[idx]);
@@ -181,6 +177,7 @@ part2()
 int
 main()
 {
-        part1();
-        part2();
+        auto lines = read_file("data/day05.txt");
+        part1(lines);
+        part2(lines);
 }
diff --git a/src/day09.cpp b/src/day09.cpp
index 0019d05..4b30e6e 100644
--- a/src/day09.cpp
+++ b/src/day09.cpp
@@ -45,10 +45,8 @@ solve_rec(const vector<T>& values)
 }
 
 void
-part1()
+part1(const vector<string>& lines)
 {
-        auto lines = read_file("data/day09.txt");
-
         long sum = 0;
         for ( const auto& line: lines ) {
                 sum += solve_rec(read_ints(line));
@@ -57,10 +55,10 @@ part1()
 }
 
 void
-part2()
+part2(const vector<string>& lines)
 {
         long sum = 0;
-        for ( const auto& line: read_file("data/day09.txt") ) {
+        for ( const auto& line: lines ) {
                 auto values = read_ints(line);
                 reverse(values.begin(), values.end());
                 sum += solve_rec(values);
@@ -71,6 +69,7 @@ part2()
 int
 main()
 {
-        part1();
-        part2();
+        auto lines = read_file("data/day09.txt");
+        part1(lines);
+        part2(lines);
 }
diff --git a/src/day10.cpp b/src/day10.cpp
index 5591290..264e111 100644
--- a/src/day10.cpp
+++ b/src/day10.cpp
@@ -38,8 +38,7 @@ find_start_pos(const puzzle_t& puzzle)
 bool
 predict_direction(const puzzle_t& puzzle, pos_t& current, char& direction)
 {
-        auto x = get<0>(current); // NOLINT
-        auto y = get<1>(current); // NOLINT
+        auto [x, y] = current;
 
         if ( direction == 'S' ) {
                 ++y;
@@ -115,10 +114,8 @@ predict_direction(const puzzle_t& puzzle, pos_t& current, char& direction)
 };
 
 void
-part1()
+part1(const puzzle_t& puzzle)
 {
-        const auto puzzle = read_file("data/day10.txt");
-
         const auto start_pos = find_start_pos(puzzle);
 
         auto max_steps = 0;
@@ -163,10 +160,8 @@ flood_fill(puzzle_t& puzzle, size_t x, size_t y)
 };
 
 void
-part2()
+part2(const puzzle_t& puzzle_original)
 {
-        const auto puzzle_original = read_file("data/day10.txt");
-
         puzzle_t puzzle{ puzzle_original.size(), string(puzzle_original[0].size(), ' ') };
 
         const auto start_pos = find_start_pos(puzzle_original);
@@ -176,8 +171,7 @@ part2()
                 auto current_pos       = start_pos;
 
                 for ( ;; ) {
-                        auto x = get<0>(current_pos); // NOLINT
-                        auto y = get<1>(current_pos); // NOLINT
+                        auto [x, y] = current_pos;
 
                         puzzle[y][x] = puzzle_original[y][x];
 
@@ -216,6 +210,7 @@ part2()
 int
 main()
 {
-        part1();
-        part2();
+        const auto puzzle = read_file("data/day10.txt");
+        part1(puzzle);
+        part2(puzzle);
 }
diff --git a/src/day12.cpp b/src/day12.cpp
index 31a2739..11bd80b 100644
--- a/src/day12.cpp
+++ b/src/day12.cpp
@@ -1,5 +1,6 @@
 #include <fstream>
 #include <iostream>
+#include <map>
 #include <sstream>
 #include <string>
 #include <vector>
@@ -69,9 +70,9 @@ count_groups(string_view str)
 }
 
 long
-brute_force(string_view puzzle, const vector<long>& nums)
+brute_force(string_view springs, const vector<long>& groups)
 {
-        long counts = count_if(puzzle.begin(), puzzle.end(), [](char chr) { return chr == '?'; });
+        long counts = count_if(springs.begin(), springs.end(), [](char chr) { return chr == '?'; });
 
         string test_pattern;
 
@@ -79,7 +80,7 @@ brute_force(string_view puzzle, const vector<long>& nums)
         for ( size_t counter = 0; counter != (1U << size_t(counts)); ++counter ) {
                 auto bit_pattern = counter;
 
-                for ( char chr: puzzle ) {
+                for ( char chr: springs ) {
                         if ( chr == '?' ) {
                                 if ( (bit_pattern & 1U) != 0U ) {
                                         test_pattern += '.';
@@ -93,7 +94,7 @@ brute_force(string_view puzzle, const vector<long>& nums)
                                 test_pattern += chr;
                         }
                 }
-                if ( nums == count_groups(test_pattern) ) {
+                if ( groups == count_groups(test_pattern) ) {
                         arrangements++;
                 }
 
@@ -103,18 +104,71 @@ brute_force(string_view puzzle, const vector<long>& nums)
         return arrangements;
 }
 
+long
+count(const string& springs, const vector<long>& groups)
+{
+        map<tuple<string, vector<long>>, long> cache;
+
+        function<long(string, const vector<long>&)> count_rec = [&](string springs, const vector<long>& groups) -> long {
+                auto cached_value = cache.find(make_tuple(springs, groups));
+                if ( cached_value != cache.end() ) {
+                        return cached_value->second;
+                }
+
+                springs.erase(0, springs.find_first_not_of('.'));
+
+                if ( springs.empty() ) {
+                        return groups.empty() ? 1 : 0;
+                }
+
+                if ( groups.empty() ) {
+                        return springs.find('#') == string_view::npos ? 1 : 0;
+                }
+
+                if ( springs[0] == '#' ) {
+                        auto gidx = size_t(groups[0]);
+                        if ( springs.length() < gidx || springs.substr(0, gidx).find('.') != string_view::npos || springs[gidx] == '#' ) {
+                                return 0;
+                        }
+
+                        return count_rec(springs.substr(gidx + 1), { groups.begin() + 1, groups.end() });
+                }
+
+                auto value = count_rec(string("#") + springs.substr(1), groups) + count_rec(springs.substr(1), groups);
+
+                cache[make_tuple(springs, groups)] = value;
+
+                return value;
+        };
+
+        return count_rec(springs + ".", groups);
+}
+
 void
-part1()
+part1(const vector<string>& input)
 {
-        const auto input = read_file("data/day12.txt");
+        auto sum = 0L;
+        for ( const auto& line: input ) {
+                auto parts   = split(line, ' ');
+                auto springs = parts[0];
+                auto groups  = read_ints(parts[1]);
 
+                sum += brute_force(springs, groups);
+                // sum += count(springs, groups);
+        }
+        cout << sum << endl;
+}
+
+void
+part2(const vector<string>& input)
+{
         auto sum = 0L;
         for ( const auto& line: input ) {
-                auto parts  = split(line, ' ');
-                auto puzzle = parts[0];
-                auto nums   = read_ints(parts[1]);
+                auto parts   = split(line, ' ');
+                auto springs = parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0] + "?" + parts[0];
+                auto groups  = read_ints(parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1] + "," + parts[1]);
 
-                sum += brute_force(puzzle, nums);
+                sum += count(springs, groups);
         }
         cout << sum << endl;
 }
@@ -122,5 +176,7 @@ part1()
 int
 main()
 {
-        part1();
+        const auto input = read_file("data/day12.txt");
+        part1(input);
+        part2(input);
 }
diff --git a/src/day14.cpp b/src/day14.cpp
index 2b7a5b8..8816ce1 100644
--- a/src/day14.cpp
+++ b/src/day14.cpp
@@ -21,10 +21,8 @@ read_file(string_view filename)
 }
 
 void
-part1()
+part1(const vector<string>& lines)
 {
-        const auto lines = read_file("data/day14.txt");
-
         auto start = chrono::steady_clock::now();
 
         size_t sum = 0;
@@ -182,10 +180,9 @@ tilt_east(vector<string>& lines)
 void
 tilt(vector<string>& lines)
 {
-        tilt_north(lines);
-        tilt_west(lines);
-        tilt_south(lines);
-        tilt_east(lines);
+        for ( auto tilt: { tilt_north, tilt_west, tilt_south, tilt_east } ) {
+                tilt(lines);
+        }
 }
 
 size_t
@@ -201,16 +198,14 @@ calc(const vector<string>& lines)
 }
 
 void
-part2()
+part2(vector<string> lines)
 {
-        auto lines = read_file("data/day14.txt");
-
         auto                      start = chrono::steady_clock::now();
         map<vector<string>, long> cache;
 
         const long dest = 1'000'000'000;
 
-        for ( long index = 0; true; ++index ) {
+        for ( long index = 0;; ++index ) {
                 auto iter = cache.find(lines);
                 if ( iter != cache.end() ) {
                         auto offset       = iter->second;
@@ -238,6 +233,7 @@ part2()
 int
 main()
 {
-        part1();
-        part2();
+        const auto lines = read_file("data/day14.txt");
+        part1(lines);
+        part2(lines);
 }
diff --git a/src/day16.cpp b/src/day16.cpp
index c2cd365..93c7479 100644
--- a/src/day16.cpp
+++ b/src/day16.cpp
@@ -44,9 +44,7 @@ solve(const vector<string>& lines, tuple<size_t, size_t, unsigned int> start)
         positions.emplace(start);
 
         while ( !positions.empty() ) {
-                auto row = get<0>(positions.front());
-                auto col = get<1>(positions.front());
-                auto dir = get<2>(positions.front());
+                auto [row, col, dir] = positions.front();
                 positions.pop();
 
                 while ( true ) {
diff --git a/src/day22.cpp b/src/day22.cpp
new file mode 100644
index 0000000..1afb994
--- /dev/null
+++ b/src/day22.cpp
@@ -0,0 +1,157 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <string>
+#include <vector>
+using namespace std;
+
+struct piece {
+        int x1, y1, z1;
+        int x2, y2, z2;
+};
+
+vector<piece>
+read_file(string_view filename)
+{
+        static const regex pattern{ R"((\d+),(\d+),(\d+)~(\d+),(\d+),(\d+))" };
+
+        fstream       input{ filename };
+        vector<piece> data;
+
+        for ( string line; getline(input, line); ) {
+                smatch matches;
+                if ( regex_search(line, matches, pattern) ) {
+                        data.emplace_back(piece{
+                            stoi(matches[1]),
+                            stoi(matches[2]),
+                            stoi(matches[3]),
+                            stoi(matches[4]),
+                            stoi(matches[5]),
+                            stoi(matches[6]) });
+                }
+        }
+        sort(data.begin(), data.end(), [](const auto& lhs, const auto& rhs) { return lhs.z1 < rhs.z1; });
+
+        return data;
+}
+
+void
+part1(vector<piece> puzzle)
+{
+        map<int, map<int, int>> grid;
+
+        map<size_t, vector<size_t>> supported_by;
+        map<size_t, vector<size_t>> supports;
+
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                auto& piece = puzzle[idx];
+
+                int max_z = 0;
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                max_z = max(max_z, grid[x][y]);
+                        }
+                }
+
+                auto height = piece.z2 - piece.z1 + 1;
+
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                grid[x][y] = max_z + height;
+                        }
+                }
+
+                piece.z1 = max_z + 1;
+                piece.z2 = max_z + height;
+
+                for ( size_t idx2 = idx; idx2-- > 0; ) {
+                        if ( piece.x1 > puzzle[idx2].x2 || puzzle[idx2].x1 > piece.x2 ) {
+                                continue;
+                        }
+                        if ( piece.y1 > puzzle[idx2].y2 || puzzle[idx2].y1 > piece.y2 ) {
+                                continue;
+                        }
+                        if ( puzzle[idx].z1 == puzzle[idx2].z2 + 1 ) {
+                                supports[idx2].emplace_back(idx);
+                                supported_by[idx].emplace_back(idx2);
+                        }
+                }
+        }
+
+        long number = 0;
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                if ( all_of(supports[idx].begin(), supports[idx].end(), [&](const auto& idx2) { return supported_by[idx2].size() > 1; }) ) {
+                        ++number;
+                }
+        }
+        cout << number << endl;
+}
+
+void
+part2(vector<piece> puzzle)
+{
+        map<int, map<int, int>> grid;
+
+        for ( auto& piece: puzzle ) {
+                int max_z = 0;
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                max_z = max(max_z, grid[x][y]);
+                        }
+                }
+
+                auto height = piece.z2 - piece.z1 + 1;
+
+                for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                        for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                grid[x][y] = max_z + height;
+                        }
+                }
+
+                piece.z1 = max_z + 1;
+                piece.z2 = max_z + height;
+        }
+
+        int num = 0;
+        for ( size_t idx = 0; idx != puzzle.size(); ++idx ) {
+                map<int, map<int, int>> grid;
+
+                for ( size_t idx2 = 0; idx2 != puzzle.size(); ++idx2 ) {
+                        if ( idx == idx2 ) {
+                                continue;
+                        }
+
+                        const auto& piece = puzzle[idx2];
+
+                        int max_z = 0;
+                        for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                                for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                        max_z = max(max_z, grid[x][y]);
+                                }
+                        }
+
+                        auto height = piece.z2 - piece.z1 + 1;
+
+                        for ( auto x = piece.x1; x <= piece.x2; ++x ) {
+                                for ( auto y = piece.y1; y <= piece.y2; ++y ) {
+                                        grid[x][y] = max_z + height;
+                                }
+                        }
+
+                        if ( piece.z1 != max_z + 1 ) {
+                                ++num;
+                        }
+                }
+        }
+        cout << num << endl;
+}
+
+int
+main()
+{
+        const auto puzzle = read_file("data/day22.txt");
+        part1(puzzle);
+        part2(puzzle);
+}
diff --git a/src/day23.cpp b/src/day23.cpp
new file mode 100644
index 0000000..d8c20d3
--- /dev/null
+++ b/src/day23.cpp
@@ -0,0 +1,152 @@
+#include <algorithm>
+#include <array>
+#include <fstream>
+#include <functional>
+#include <iostream>
+#include <iterator>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+#include <vector>
+using namespace std;
+
+using position_t = tuple<size_t, size_t>;
+
+vector<string>
+read_file(string_view filename)
+{
+        fstream        input{ filename };
+        vector<string> data;
+
+        for ( string line; getline(input, line); ) {
+                data.emplace_back(line);
+        }
+
+        return data;
+}
+
+set<position_t>
+get_neighbours(const vector<string>& maze, position_t possition)
+{
+        static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
+
+        static const auto SYM_UP    = '^';
+        static const auto SYM_RIGHT = '>';
+        static const auto SYM_DOWN  = 'v';
+        static const auto SYM_LEFT  = '<';
+
+        const auto [row, col] = possition;
+
+        switch ( maze[row][col] ) {
+        case SYM_UP:
+                return { make_tuple(row - 1, col) };
+        case SYM_RIGHT:
+                return { make_tuple(row, col + 1) };
+        case SYM_DOWN:
+                return { make_tuple(row + 1, col) };
+        case SYM_LEFT:
+                return { make_tuple(row, col - 1) };
+        }
+
+        set<position_t> positions;
+
+        for ( const auto& delta: deltas ) {
+                const auto new_row = row + get<0>(delta);
+                const auto new_col = col + get<1>(delta);
+
+                if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
+                        continue;
+                }
+
+                if ( maze[new_row][new_col] == '#' ) {
+                        continue;
+                }
+
+                if ( new_row < row && maze[new_row][new_col] == SYM_DOWN ) {
+                        continue;
+                }
+                if ( new_row > row && maze[new_row][new_col] == SYM_UP ) {
+                        continue;
+                }
+                if ( new_col < col && maze[new_row][new_col] == SYM_RIGHT ) {
+                        continue;
+                }
+                if ( new_col > col && maze[new_row][new_col] == SYM_LEFT ) {
+                        continue;
+                }
+
+                positions.emplace(new_row, new_col);
+        }
+
+        return positions;
+}
+
+set<position_t>
+get_neighbours2(const vector<string>& maze, position_t possition)
+{
+        static const position_t deltas[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // NOLINT
+
+        const auto [row, col] = possition;
+
+        set<position_t> positions;
+
+        for ( const auto& delta: deltas ) {
+                const auto new_row = row + get<0>(delta);
+                const auto new_col = col + get<1>(delta);
+
+                if ( new_row >= maze.size() || new_col >= maze[0].size() ) {
+                        continue;
+                }
+
+                if ( maze[new_row][new_col] == '#' ) {
+                        continue;
+                }
+
+                positions.emplace(new_row, new_col);
+        }
+
+        return positions;
+}
+
+void
+solve(const vector<string>& maze, function<set<position_t>(const vector<string>&, position_t)> neighbours)
+{
+        const position_t start = { 0, maze[0].find('.') };
+        const position_t end   = { maze.size() - 1, maze[maze.size() - 1].find('.') };
+
+        vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size()));
+
+        function<long(position_t, long)> find_longest_path = [&](position_t position, long current) -> long {
+                const auto [row, col] = position;
+
+                if ( visited[row][col] ) {
+                        return 0;
+                }
+
+                if ( position == end ) {
+                        return current;
+                }
+
+                long value = 0;
+
+                visited[row][col] = true;
+                for ( const auto& neighbour: neighbours(maze, position) ) {
+                        value = max(value, find_longest_path(neighbour, current + 1));
+                }
+                visited[row][col] = false;
+
+                return value;
+        };
+
+        auto value = find_longest_path(start, 0);
+        cout << value << endl;
+}
+
+int
+main()
+{
+        const auto maze = read_file("data/day23.txt");
+        solve(maze, get_neighbours);
+        solve(maze, get_neighbours2);
+}
diff --git a/src/day24.cpp b/src/day24.cpp
new file mode 100644
index 0000000..76f459b
--- /dev/null
+++ b/src/day24.cpp
@@ -0,0 +1,173 @@
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <limits>
+#include <map>
+#include <string>
+#include <tuple>
+#include <vector>
+#include <z3++.h>
+
+using namespace std;
+
+using line_type   = tuple<double, double, double, double, double, double>;
+using point_type  = tuple<double, double>;
+using puzzle_type = vector<line_type>;
+
+template<typename T>
+int
+sgn(T val)
+{
+        return (T(0) < val) - (val < T(0));
+}
+
+puzzle_type
+read_file(string_view filename)
+{
+        fstream     input{ filename };
+        puzzle_type result;
+
+        for ( string line; getline(input, line); ) {
+                const auto NFIELDS = 6;
+
+                double x, y, z, dx, dy, dz; // NOLINT
+
+                if ( sscanf(line.data(), "%lf, %lf, %lf @ %lf, %lf, %lf", &x, &y, &z, &dx, &dy, &dz) != NFIELDS ) {
+                        continue;
+                }
+
+                result.emplace_back(make_tuple(x, y, z, dx, dy, dz));
+        }
+
+        return result;
+}
+
+point_type
+get_direction(line_type line)
+{
+        const auto [x, y, z, dx, dy, dz] = line;
+
+        return make_tuple(sgn(dx), sgn(dy));
+}
+
+point_type
+get_direction(line_type from, point_type to)
+{
+        const auto [x, y, z, dx, dy, dz] = from;
+        const auto [to_x, to_y]          = to;
+
+        return make_tuple(sgn(to_x - x), sgn(to_y - y));
+}
+
+bool
+lint(line_type stone_a, line_type stone_b, point_type& cross_point)
+{
+        const auto p_1 = make_tuple(get<0>(stone_a), get<1>(stone_a));
+        const auto p_2 = make_tuple(get<0>(stone_a) + get<3>(stone_a), get<1>(stone_a) + get<4>(stone_a));
+
+        const auto p_3 = make_tuple(get<0>(stone_b), get<1>(stone_b));
+        const auto p_4 = make_tuple(get<0>(stone_b) + get<3>(stone_b), get<1>(stone_b) + get<4>(stone_b));
+
+        const auto a_1 = get<1>(p_2) - get<1>(p_1);
+        const auto b_1 = get<0>(p_1) - get<0>(p_2);
+        const auto c_1 = a_1 * (get<0>(p_1)) + b_1 * (get<1>(p_1));
+
+        const auto a_2 = get<1>(p_4) - get<1>(p_3);
+        const auto b_2 = get<0>(p_3) - get<0>(p_4);
+        const auto c_2 = a_2 * (get<0>(p_3)) + b_2 * (get<1>(p_3));
+
+        const auto determinant = a_1 * b_2 - a_2 * b_1;
+
+        if ( determinant == 0 ) {
+                return false;
+        }
+
+        auto p_x = (b_2 * c_1 - b_1 * c_2) / determinant;
+        auto p_y = (a_1 * c_2 - a_2 * c_1) / determinant;
+
+        cross_point = make_tuple(p_x, p_y);
+
+        return true;
+}
+
+void
+part1(const puzzle_type& input)
+{
+        const auto in_range = [](point_type point) -> bool {
+                static const auto lower_limit = 200000000000000.0;
+                static const auto upper_limit = 400000000000000.0;
+
+                const auto [x, y] = point;
+
+                return x > lower_limit && x < upper_limit && y > lower_limit && y < upper_limit;
+        };
+
+        const auto in_future = [](line_type stone, point_type point) -> bool {
+                const auto sgn_stone = get_direction(stone);
+                const auto sgn_point = get_direction(stone, point);
+
+                return sgn_stone == sgn_point;
+        };
+
+        long sum = 0;
+        for ( size_t idx = 0; idx != input.size(); ++idx ) {
+                const auto& stone_a = input[idx];
+
+                for ( size_t idx2 = idx + 1; idx2 < input.size(); ++idx2 ) {
+                        const auto& stone_b = input[idx2];
+
+                        point_type cross_point;
+                        if ( lint(stone_a, stone_b, cross_point) && in_range(cross_point) && in_future(stone_a, cross_point) && in_future(stone_b, cross_point) ) {
+                                ++sum;
+                        }
+                }
+        }
+        cout << sum << endl;
+}
+
+void
+part2(const puzzle_type& input)
+{
+        auto config  = z3::config();
+        auto context = z3::context(config);
+        auto solver  = z3::solver(context);
+
+        const auto px = context.int_const("px");
+        const auto py = context.int_const("py");
+        const auto pz = context.int_const("pz");
+        const auto vx = context.int_const("vx");
+        const auto vy = context.int_const("vy");
+        const auto vz = context.int_const("vz");
+
+        for ( size_t i = 0; i != input.size(); ++i ) {
+                const auto& stone = input[i];
+
+                const auto pxn = context.int_val(int64_t(get<0>(stone)));
+                const auto pyn = context.int_val(int64_t(get<1>(stone)));
+                const auto pzn = context.int_val(int64_t(get<2>(stone)));
+                const auto vxn = context.int_val(int64_t(get<3>(stone)));
+                const auto vyn = context.int_val(int64_t(get<4>(stone)));
+                const auto vzn = context.int_val(int64_t(get<5>(stone)));
+                const auto tn  = context.int_const(to_string(i+1).c_str());
+
+                solver.add(tn >= 0);
+                solver.add(pxn + vxn * tn == px + vx * tn);
+                solver.add(pyn + vyn * tn == py + vy * tn);
+                solver.add(pzn + vzn * tn == pz + vz * tn);
+        }
+
+        solver.check();
+
+        auto model = solver.get_model();
+
+        cout << model.eval(px).as_int64() + model.eval(py).as_int64() + model.eval(pz).as_int64() << endl;
+}
+
+int
+main()
+{
+        const auto input = read_file("data/day24.txt");
+
+        part1(input);
+        part2(input);
+}
diff --git a/src/day25.cpp b/src/day25.cpp
new file mode 100644
index 0000000..1d5e19e
--- /dev/null
+++ b/src/day25.cpp
@@ -0,0 +1,140 @@
+#include <algorithm>
+#include <array>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <random>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+using graph_type = map<string, set<string>>;
+
+vector<string>
+split(const string& line, char sep)
+{
+        vector<string> parts;
+        stringstream   input{ line };
+
+        for ( string part; getline(input, part, sep); ) {
+                parts.emplace_back(part);
+        }
+
+        return parts;
+}
+
+graph_type
+read_file(string_view filename)
+{
+        fstream    input{ filename };
+        graph_type graph;
+
+        for ( string line; getline(input, line); ) {
+                const auto components = split(line.erase(line.find(':'), 1), ' ');
+
+                for ( size_t i = 1; i < components.size(); ++i ) {
+                        graph[components[0]].insert(components[i]);
+                        graph[components[i]].insert(components[0]);
+                }
+        }
+
+        return graph;
+}
+
+bool
+bfs(graph_type graph, const string& source, const string& dest, function<void(const string&, const string&)> visit) // NOLINT
+{
+        set<string> visited;
+
+        queue<string> queue;
+        queue.emplace(source);
+
+        while ( !queue.empty() ) {
+                auto candidate = queue.front();
+                queue.pop();
+
+                if ( candidate == dest ) {
+                        return true;
+                }
+
+                for ( const auto& neighbour: graph[candidate] ) {
+                        if ( !visited.contains(neighbour) ) {
+                                queue.emplace(neighbour);
+
+                                visit(candidate, neighbour);
+                                visited.emplace(neighbour);
+                        }
+                }
+        }
+        return false;
+}
+
+auto
+random_node(const graph_type& graph)
+{
+        static random_device dev;
+        static mt19937       generator(dev());
+
+        uniform_int_distribution<graph_type::size_type> distribute(0, graph.size()-1);
+
+        auto iter = graph.begin();
+        advance(iter, distribute(generator));
+        return iter->first;
+}
+
+void
+part1(graph_type graph)
+{
+        map<tuple<string, string>, int> frequencies;
+        for ( size_t idx = 0; idx != 2; ++idx ) {
+                for ( const auto& second: graph ) {
+                        bfs(graph, random_node(graph), second.first, [&](const string& candidate, const string& neighbour) {
+                                if ( candidate < neighbour ) {
+                                        frequencies[make_tuple(candidate, neighbour)]++;
+                                }
+                                else {
+                                        frequencies[make_tuple(neighbour, candidate)]++;
+                                }
+                        });
+                }
+        }
+
+        vector<tuple<tuple<string, string>, int>> sorted_frequencies{ frequencies.begin(), frequencies.end() };
+
+        sort(sorted_frequencies.begin(), sorted_frequencies.end(), [](const auto& lhs, const auto& rhs) {
+                return get<1>(lhs) > get<1>(rhs);
+        });
+
+        sorted_frequencies.erase(sorted_frequencies.begin() + 3, sorted_frequencies.end());
+
+        for ( const auto& link: sorted_frequencies ) {
+                const auto [left, right] = get<0>(link);
+
+                graph[left].erase(right);
+                graph[right].erase(left);
+        }
+
+        auto reachable = [&graph](const string& start_node) {
+                set<string> nodes;
+                bfs(graph, start_node, "", [&nodes](const string& candidate, const string& neighbour) {
+                        nodes.insert(candidate);
+                        nodes.insert(neighbour);
+                });
+                return nodes.size();
+        };
+
+        const auto [left, right] = get<0>(sorted_frequencies[0]);
+
+        cout << reachable(left) * reachable(right) << endl;
+}
+
+int
+main()
+{
+        auto graph = read_file("data/day25.txt");
+        part1(graph);
+}