From 8427e039c3a99d1cb7a543a06f9d63897df9f294 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 22 Dec 2024 17:28:13 +0100
Subject: aoc 2024, day 21

---
 2024/src/day21.cpp | 193 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 193 insertions(+)
 create mode 100644 2024/src/day21.cpp

(limited to '2024')

diff --git a/2024/src/day21.cpp b/2024/src/day21.cpp
new file mode 100644
index 0000000..9dd166a
--- /dev/null
+++ b/2024/src/day21.cpp
@@ -0,0 +1,193 @@
+#undef NDEBUG
+#include <algorithm>
+#include <cassert>
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <numeric>
+#include <string>
+#include <tuple>
+#include <vector>
+using namespace std;
+
+using pos_type = tuple<int, int>;
+using map_type = map<char, pos_type>;
+
+vector<string>
+read_file(string_view filename)
+{
+	fstream        input{ filename };
+	vector<string> lines;
+
+	for ( string line; getline(input, line); ) {
+		lines.emplace_back(line);
+	}
+
+	return lines;
+}
+
+bool
+is_valid_movement(pos_type start, const pos_type dest, string_view movement, const pos_type avoid)
+{
+	static const map_type directions = {
+		{ '^', { 0, -1 } },
+		{ 'v', { 0, 1 } },
+		{ '<', { -1, 0 } },
+		{ '>', { 1, 0 } }
+	};
+
+	for ( const auto key: movement ) {
+		const auto [dx, dy] = directions.at(key);
+
+		get<0>(start) += dx;
+		get<1>(start) += dy;
+
+		if ( start == avoid ) {
+			return false;
+		}
+	}
+
+	assert(start == dest); // NOLINT
+
+	return true;
+}
+
+vector<string>
+get_movements(const pos_type start, const pos_type end, const pos_type avoid)
+{
+	if ( start == end ) {
+		return { "A" };
+	}
+
+	const auto [start_x, start_y] = start;
+	const auto [end_x, end_y]     = end;
+
+	string movement;
+
+	const auto delta_y = end_y - start_y;
+	if ( delta_y < 0 ) {
+		movement.append(size_t(-delta_y), '^');
+	}
+	else if ( delta_y > 0 ) {
+		movement.append(size_t(delta_y), 'v');
+	}
+
+	const auto delta_x = end_x - start_x;
+	if ( delta_x < 0 ) {
+		movement.append(size_t(-delta_x), '<');
+	}
+	else if ( delta_x > 0 ) {
+		movement.append(size_t(delta_x), '>');
+	}
+
+	assert(!movement.empty()); // NOLINT
+
+	vector<string> movements;
+
+	ranges::sort(movement);
+	do {
+		if ( is_valid_movement(start, end, movement, avoid) ) {
+			movements.emplace_back(movement + 'A');
+		}
+	} while ( next_permutation(movement.begin(), movement.end()) );
+
+	assert(!movements.empty()); // NOLINT
+
+	return movements;
+}
+
+size_t
+find_rec(string_view keys, const int depth, const int max_depth)
+{
+	static const map_type keypad_door{
+		{ '7', { 0, 0 } },
+		{ '8', { 1, 0 } },
+		{ '9', { 2, 0 } },
+
+		{ '4', { 0, 1 } },
+		{ '5', { 1, 1 } },
+		{ '6', { 2, 1 } },
+
+		{ '1', { 0, 2 } },
+		{ '2', { 1, 2 } },
+		{ '3', { 2, 2 } },
+
+		{ '0', { 1, 3 } },
+		{ 'A', { 2, 3 } },
+	};
+
+	static const map_type keypad_robot{
+		{ '^', { 1, 0 } },
+		{ 'A', { 2, 0 } },
+
+		{ '<', { 0, 1 } },
+		{ 'v', { 1, 1 } },
+		{ '>', { 2, 1 } }
+	};
+
+	static map<tuple<string, int, int>, size_t> cache;
+
+	if ( cache.contains({ string(keys), depth, max_depth }) ) {
+		return cache.at({ string(keys), depth, max_depth });
+	}
+
+	const auto& keypad = depth == 0 ? keypad_door : keypad_robot;
+	const auto& avoid  = depth == 0 ? pos_type{ 0, 3 } : pos_type{ 0, 0 };
+
+	auto pos = keypad.at('A');
+
+	size_t len = 0;
+	for ( const auto key: keys ) {
+		const auto end = keypad.at(key);
+
+		const auto movements = get_movements(pos, end, avoid);
+
+		if ( depth == max_depth ) {
+			len += ranges::min_element(
+			           movements, [](const auto& lhs, const auto& rhs) -> bool { return lhs.size() < rhs.size(); })
+			           ->size();
+		}
+		else {
+			auto curr_min = numeric_limits<size_t>::max();
+			for ( const auto& movement: movements ) {
+				curr_min = min(curr_min, find_rec(movement, depth + 1, max_depth));
+			}
+			len += curr_min;
+		}
+
+		pos = end;
+	}
+
+	return cache[{ string(keys), depth, max_depth }] = len;
+}
+
+size_t
+find(string_view keys, const int depth)
+{
+	return find_rec(keys, 0, depth);
+}
+
+void
+part1(const vector<string>& lines)
+{
+	cout << accumulate(lines.begin(), lines.end(), 0UL, [](auto init, const auto& line) {
+		return init + find(line, 2) * strtoul(line.c_str(), nullptr, 10);
+	}) << endl;
+}
+
+void
+part2(const vector<string>& lines)
+{
+	cout << accumulate(lines.begin(), lines.end(), 0UL, [](auto init, const auto& line) {
+		return init + find(line, 25) * strtoul(line.c_str(), nullptr, 10);
+	}) << endl;
+}
+
+int
+main()
+{
+	const auto lines = read_file("data/day21.txt");
+	part1(lines);
+	part2(lines);
+}
-- 
cgit v1.3