From fc3cc642c620221cafed36c8c07da34bfb566843 Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sat, 14 Dec 2024 11:27:04 +0100
Subject: aoc 2024, day 14

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

diff --git a/2024/src/day14.cpp b/2024/src/day14.cpp
new file mode 100644
index 0000000..97e5fab
--- /dev/null
+++ b/2024/src/day14.cpp
@@ -0,0 +1,181 @@
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <regex>
+#include <set>
+#include <tuple>
+#include <vector>
+using namespace std;
+
+using pos_type  = tuple<long, long>;
+using velo_type = tuple<long, long>;
+
+vector<tuple<pos_type, velo_type>>
+read_file(string_view filename)
+{
+	static const regex pattern{ R"(^p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)$)" };
+
+	fstream input{ filename };
+
+	vector<tuple<pos_type, velo_type>> data;
+	for ( string line; getline(input, line); ) {
+		smatch matches;
+
+		if ( regex_search(line, matches, pattern) ) {
+			data.push_back({ { stoi(matches[1]), stoi(matches[2]) },
+			                 { stoi(matches[3]), stoi(matches[4]) } });
+		}
+	}
+	return data;
+}
+
+/*
+void
+print(const vector<tuple<pos_type, velo_type>>& robots, long width, long height)
+{
+    map<pos_type, long> map;
+
+    for ( const auto& [pos, velo]: robots ) {
+        map[pos]++;
+    }
+
+    for ( long y = 0; y != height; ++y ) {
+        for ( long x = 0; x != width; ++x ) {
+            auto pos = map.find({ x, y });
+            if ( pos != map.end() ) {
+                cout << pos->second;
+            }
+            else {
+                cout << '.';
+            }
+        }
+        cout << '\n';
+    }
+    cout << endl;
+}
+*/
+
+/*
+void
+print_pic(const vector<tuple<pos_type, velo_type>>& robots, long width, long height)
+{
+    map<pos_type, long> map;
+
+    for ( const auto& [pos, velo]: robots ) {
+        map[pos]++;
+    }
+
+    for ( long y = 0; y != height; ++y ) {
+        for ( long x = 0; x != width; ++x ) {
+            auto pos = map.find({ x, y });
+            cout << (pos != map.end() ? 'X' : ' ');
+        }
+        cout << '\n';
+    }
+    cout << endl;
+}
+*/
+
+long
+count(const vector<tuple<pos_type, velo_type>>& robots, long width, long height)
+{
+	map<pos_type, long> map;
+
+	const auto width_half  = width / 2;
+	const auto height_half = height / 2;
+
+	for ( const auto& [pos, velo]: robots ) {
+		const auto [x, y] = pos;
+		if ( x == width_half || y == height_half ) {
+			continue;
+		}
+		map[{ x / (width_half + 1), y / (height_half + 1) }]++;
+	}
+
+	long result = 1;
+	for ( const auto& [pos, count]: map ) {
+		result *= count;
+	}
+	return result;
+}
+
+void
+move(vector<tuple<pos_type, velo_type>>& robots, long width, long height)
+{
+	for ( auto& [pos, velo]: robots ) {
+		auto& [x, y]  = pos;
+		auto [vx, vy] = velo;
+
+		x = (x + width + vx) % width;
+		y = (y + height + vy) % height;
+	}
+}
+
+void
+part1(vector<tuple<pos_type, velo_type>> robots, long width, long height)
+{
+	for ( long second = 0; second != 100; ++second ) {
+		move(robots, width, height);
+	}
+
+	cout << count(robots, width, height) << endl;
+}
+
+void
+part2(vector<tuple<pos_type, velo_type>> robots, long width, long height)
+{
+	auto min_result   = numeric_limits<long>::max();
+	long second_found = 0;
+
+	for ( long second = 0; second != 100000; ++second ) {
+		auto result = count(robots, width, height);
+
+		if ( result < min_result ) {
+			second_found = second;
+			min_result   = result;
+		}
+
+		move(robots, width, height);
+	}
+	cout << second_found << endl;
+}
+
+void
+part2_alternative(vector<tuple<pos_type, velo_type>> robots, long width, long height)
+{
+	set<pos_type> seen;
+
+	for ( long second = 0; second != 100000; ++second ) {
+		seen.clear();
+
+		bool overlap = false;
+		for ( const auto& [pos, velo]: robots ) {
+			if ( seen.contains(pos) ) {
+				overlap = true;
+				break;
+			}
+			seen.insert(pos);
+		}
+
+		if ( !overlap ) {
+			cout << second << endl;
+			break;
+		}
+
+		move(robots, width, height);
+	}
+}
+
+int
+main()
+{
+#if 0
+	auto robots = read_file("data/day14-sample1.txt");
+	part1(robots, 11, 7);
+#else
+	auto robots = read_file("data/day14.txt");
+	part1(robots, 101, 103);
+	part2(robots, 101, 103);
+	part2_alternative(robots, 101, 103);
+#endif
+}
-- 
cgit v1.3