From ae1e96f10b399266825e275ca4a8100ceede9cad Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Thu, 23 Oct 2025 19:28:20 +0200
Subject: days 19-25, aoc 2016

---
 2016/src/day24.cpp | 153 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 153 insertions(+)
 create mode 100644 2016/src/day24.cpp

(limited to '2016/src/day24.cpp')

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