From 54e6dca438215f499637247f818dbeefafeded80 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Fri, 20 Dec 2024 15:18:16 +0100
Subject: aoc 2024, day 20, part 1

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

(limited to '2024/src/day20.cpp')

diff --git a/2024/src/day20.cpp b/2024/src/day20.cpp
new file mode 100644
index 0000000..42a2fba
--- /dev/null
+++ b/2024/src/day20.cpp
@@ -0,0 +1,108 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+#include <tuple>
+#include <vector>
+using namespace std;
+
+using pos_type = tuple<size_t, size_t>;
+
+tuple<pos_type, pos_type, set<pos_type>>
+read_file(string_view filename)
+{
+	fstream       input{ filename };
+	set<pos_type> walls;
+	pos_type      start;
+	pos_type      end;
+
+	size_t yPos = 0;
+	for ( string line; getline(input, line); ) {
+		for ( size_t xPos = 0; xPos != line.size(); ++xPos ) {
+			auto chr = line[xPos];
+			if ( chr == '#' ) {
+				walls.emplace(xPos, yPos);
+			}
+			else if ( chr == 'S' ) {
+				start = { xPos, yPos };
+			}
+			else if ( chr == 'E' ) {
+				end = { xPos, yPos };
+			}
+		}
+		++yPos;
+	}
+
+	return { start, end, walls };
+}
+
+map<pos_type, long>
+bfs(const tuple<pos_type, pos_type, set<pos_type>>& data)
+{
+	const auto& [start, end, walls] = data;
+
+	map<pos_type, long> path;
+
+	set<pos_type> seen;
+
+	queue<tuple<pos_type, long>> queue;
+	queue.push({ start, 0 });
+
+	while ( !queue.empty() ) {
+		auto [pos, dist] = queue.front();
+		queue.pop();
+
+		if ( seen.contains(pos) ) {
+			continue;
+		}
+		seen.insert(pos);
+
+		path[pos] = dist;
+
+		if ( pos == end ) {
+			break;
+		}
+
+		auto [x, y] = pos;
+		for ( const auto& new_pos: vector<pos_type>{ { x - 1, y }, { x, y - 1 }, { x + 1, y }, { x, y + 1 } } ) {
+			if ( walls.contains(new_pos) ) {
+				continue;
+			}
+			queue.push({ new_pos, dist + 1 });
+		}
+	}
+	return path;
+}
+
+void
+part1(const tuple<pos_type, pos_type, set<pos_type>>& data)
+{
+	auto path = bfs(data);
+
+	const auto& [start, end, walls] = data;
+
+	long count = 0;
+	for ( const auto& [pos, dist]: path ) {
+		auto [x, y] = pos;
+
+		for ( const auto& [dx, dy]: vector<pos_type>{ { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } } ) {
+			if ( !walls.contains({ x + dx, y + dy }) ) {
+				continue;
+			}
+			pos_type new_pos{ x + 2 * dx, y + 2 * dy };
+			if ( path.contains(new_pos) && dist < path.at(new_pos) && path.at(new_pos) - dist >= 100 + 2 ) {
+				++count;
+			}
+		}
+	}
+	cout << count << endl;
+}
+
+int
+main()
+{
+	auto data = read_file("data/day20.txt");
+	part1(data);
+}
-- 
cgit v1.3