From 3f1e9844dbe58428e3b9528e9418c363266ceae4 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 19 Nov 2025 23:18:20 +0100
Subject: aoc 2018, days 13 & 14

---
 2018/src/day13.cpp | 217 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 217 insertions(+)
 create mode 100644 2018/src/day13.cpp

(limited to '2018/src/day13.cpp')

diff --git a/2018/src/day13.cpp b/2018/src/day13.cpp
new file mode 100644
index 0000000..c764f7f
--- /dev/null
+++ b/2018/src/day13.cpp
@@ -0,0 +1,217 @@
+#include <filesystem>
+#include <fstream>
+#include <iostream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+namespace {
+
+enum class Direction : uint8_t {
+	Up,
+	Right,
+	Down,
+	Left
+};
+
+struct Cart {
+	size_t        x;
+	size_t        y;
+	Direction     direction;
+	unsigned long intersection{};
+};
+
+using Grid  = vector<string>;
+using Carts = vector<Cart>;
+
+tuple<Grid, Carts>
+read_file(const filesystem::path& filename)
+{
+	ifstream file{ filename };
+
+	Grid  data;
+	Carts carts;
+
+	size_t y = 0;
+	for ( string line; getline(file, line); ) {
+		for ( size_t x = 0; x != line.size(); ++x ) {
+			using enum Direction;
+
+			const char chr = line[x];
+			if ( chr == '^' || chr == 'v' ) {
+				carts.emplace_back(x, y, chr == '^' ? Up : Down);
+			}
+			else if ( chr == '<' || chr == '>' ) {
+				carts.emplace_back(x, y, chr == '<' ? Left : Right);
+			}
+		}
+		data.emplace_back(line);
+		++y;
+	}
+
+	return { data, carts };
+}
+
+void
+sort_carts(Carts& carts)
+{
+	ranges::sort(carts,
+	             [](auto& lhs, auto& rhs) {
+		             return tie(lhs.y, lhs.x) < tie(rhs.y, rhs.x);
+	             });
+}
+
+void
+move_cart(Cart& cart)
+{
+	using enum Direction;
+
+	switch ( cart.direction ) {
+	case Up:
+		--cart.y;
+		break;
+	case Right:
+		++cart.x;
+		break;
+	case Down:
+		++cart.y;
+		break;
+	case Left:
+		--cart.x;
+		break;
+	}
+}
+
+void
+apply_direction_rules(const Grid& grid, Cart& cart)
+{
+	using enum Direction;
+
+	const char chr = grid[cart.y][cart.x];
+	switch ( chr ) {
+	case '/':
+		if ( cart.direction == Up ) {
+			cart.direction = Right;
+		}
+		else if ( cart.direction == Right ) {
+			cart.direction = Up;
+		}
+		else if ( cart.direction == Down ) {
+			cart.direction = Left;
+		}
+		else if ( cart.direction == Left ) {
+			cart.direction = Down;
+		}
+		break;
+	case '\\':
+		if ( cart.direction == Up ) {
+			cart.direction = Left;
+		}
+		else if ( cart.direction == Right ) {
+			cart.direction = Down;
+		}
+		else if ( cart.direction == Down ) {
+			cart.direction = Right;
+		}
+		else if ( cart.direction == Left ) {
+			cart.direction = Up;
+		}
+		break;
+	case '+':
+		switch ( cart.intersection++ % 3 ) {
+		case 0:
+			cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 3) % 4);
+			break;
+		case 2:
+			cart.direction = static_cast<Direction>((static_cast<int>(cart.direction) + 1) % 4);
+			break;
+		default:
+			break;
+		};
+		break;
+	default:
+		break;
+	}
+}
+
+void
+part1(const Grid& grid, Carts carts)
+{
+	while ( true ) {
+		sort_carts(carts);
+
+		for ( size_t i = 0; i != carts.size(); ++i ) {
+			auto& cart = carts[i];
+
+			move_cart(cart);
+			apply_direction_rules(grid, cart);
+
+			for ( size_t j = 0; j != carts.size(); ++j ) {
+				if ( i == j ) {
+					continue;
+				}
+
+				const auto& other = carts[j];
+
+				if ( cart.x == other.x && cart.y == other.y ) {
+					cout << "Part 1: " << cart.x << ',' << cart.y << '\n';
+					return;
+				}
+			}
+		}
+	}
+}
+
+void
+part2(const Grid& grid, Carts carts)
+{
+	while ( true ) {
+		sort_carts(carts);
+
+		vector<size_t> carts_to_be_removed;
+
+		for ( size_t i = 0; i != carts.size(); ++i ) {
+			auto& cart = carts[i];
+
+			move_cart(cart);
+			apply_direction_rules(grid, cart);
+
+			for ( size_t j = 0; j != carts.size(); ++j ) {
+				if ( i == j ) {
+					continue;
+				}
+
+				const auto& other = carts[j];
+
+				if ( cart.x == other.x && cart.y == other.y ) {
+					carts_to_be_removed.emplace_back(i);
+					carts_to_be_removed.emplace_back(j);
+				}
+			}
+		}
+
+		// remove carts
+		ranges::sort(carts_to_be_removed);
+		ranges::reverse(carts_to_be_removed);
+
+		for ( auto num: carts_to_be_removed ) {
+			carts.erase(carts.begin() + static_cast<long>(num));
+		}
+
+		if ( carts.size() == 1 ) {
+			cout << "Part 2: " << carts[0].x << ',' << carts[0].y << '\n';
+			return;
+		}
+	}
+}
+
+} // namespace
+
+int
+main()
+{
+	auto [grid, carts] = read_file("data/day13.txt");
+	part1(grid, carts);
+	part2(grid, carts);
+}
-- 
cgit v1.3