1 files changed, 153 insertions, 0 deletions

diff --git a/2016/src/day24.cpp b/2016/src/day24.cpp
new file mode 100644
index 0000000..936f216
--- /dev/null
+++ b/2016/src/day24.cpp
@@ -0,0 +1,153 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+
+using namespace std;
+
+namespace {
+
+using pos_type    = tuple<size_t, size_t>;
+using grid_type   = map<pos_type, char>;
+using points_type = map<char, pos_type>;
+using dists_type  = map<tuple<char, char>, size_t>;
+
+tuple<grid_type, points_type>
+read_file(const filesystem::path& filename)
+{
+        ifstream file{ filename };
+
+        grid_type   grid;
+        points_type points;
+
+        size_t row = 0;
+        for ( string line; getline(file, line); ) {
+                for ( size_t col = 0; col != line.size(); ++col ) {
+                        auto     chr = line[col];
+                        pos_type pos{ col, row };
+
+                        grid[pos] = chr;
+
+                        if ( isdigit(chr) != 0 ) {
+                                points[chr] = pos;
+                        }
+                }
+
+                ++row;
+        }
+        return { grid, points };
+}
+
+size_t
+bfs(const grid_type& grid, const pos_type src, const pos_type dest)
+{
+        set<pos_type>                  seen;
+        queue<tuple<pos_type, size_t>> queue;
+
+        queue.emplace(src, 0);
+        seen.insert(src);
+
+        while ( !queue.empty() ) {
+                auto [pos, steps] = queue.front();
+                queue.pop();
+
+                if ( pos == dest ) {
+                        return steps;
+                }
+
+                static const pos_type dirs[]{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
+                const auto [x, y] = pos;
+
+                for ( const auto [dx, dy]: dirs ) {
+                        const pos_type new_pos{ x + dx, y + dy };
+
+                        if ( grid.at(new_pos) == '#' || seen.contains(new_pos) ) {
+                                continue;
+                        }
+
+                        seen.insert(new_pos);
+                        queue.emplace(new_pos, steps + 1);
+                }
+        }
+
+        return 0;
+}
+
+dists_type
+build_dists(const grid_type& grid, const points_type& points)
+{
+        dists_type dists;
+
+        for ( auto src = points.begin(); src != points.end(); ++src ) {
+                for ( auto dest = next(src); dest != points.end(); ++dest ) {
+                        const auto dist = bfs(grid, src->second, dest->second);
+
+                        dists[{ src->first, dest->first }] = dist;
+                        dists[{ dest->first, src->first }] = dist;
+                }
+        }
+
+        return dists;
+}
+
+size_t
+shortest_route(const dists_type&  dists,
+               const points_type& points,
+               bool               return_to_start)
+{
+        vector<char> others;
+        for ( const auto& [id, _]: points ) {
+                if ( id != '0' ) {
+                        others.push_back(id);
+                }
+        }
+
+        size_t best = numeric_limits<size_t>::max();
+
+        do {
+                size_t dist    = 0;
+                char   current = '0';
+
+                for ( char next: others ) {
+                        dist += dists.at({ current, next });
+                        current = next;
+                }
+
+                if ( return_to_start ) {
+                        dist += dists.at({ current, '0' });
+                }
+
+                best = min(best, dist);
+        } while ( next_permutation(others.begin(), others.end()) );
+
+        return best;
+}
+
+void
+part1(const grid_type& grid, const points_type& points)
+{
+        auto dists = build_dists(grid, points);
+        auto route = shortest_route(dists, points, false);
+        cout << "Part1: " << route << '\n';
+}
+
+void
+part2(const grid_type& grid, const points_type& points)
+{
+        auto dists = build_dists(grid, points);
+        auto route = shortest_route(dists, points, true);
+        cout << "Part2: " << route << '\n';
+}
+
+} // namespace
+
+int
+main()
+{
+        auto [grid, points] = read_file("data/day24.txt");
+        part1(grid, points);
+        part2(grid, points);
+}