From 82478551ad59a6ff7ac095f16775077981b1e14a Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Wed, 11 Dec 2024 17:54:37 +0100
Subject: aoc 2024, day 11, part 2

---
 2024/src/day11.cpp | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)

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

diff --git a/2024/src/day11.cpp b/2024/src/day11.cpp
index f31e30b..ee8f57b 100644
--- a/2024/src/day11.cpp
+++ b/2024/src/day11.cpp
@@ -1,6 +1,8 @@
 #include <fstream>
 #include <iostream>
 #include <iterator>
+#include <map>
+#include <numeric>
 #include <vector>
 using namespace std;
 
@@ -37,9 +39,45 @@ part1(vector<long> data)
 	cout << data.size() << endl;
 }
 
+void
+part2(const vector<long>& data)
+{
+	static const int MAX_DEPTH = 75;
+
+	map<tuple<long, int>, long> cache;
+
+	function<long(long, int)> count = [&](long value, int depth) -> long {
+		if ( cache.contains({ value, depth }) ) {
+			return cache[{ value, depth }];
+		}
+
+		if ( depth == MAX_DEPTH ) {
+			return 1;
+		}
+
+		if ( value == 0 ) {
+			return cache[{ value, depth }] = count(1, depth + 1);
+		}
+
+		auto str = to_string(value);
+		if ( str.size() % 2 == 0 ) {
+			auto len = str.size() / 2;
+			auto lhs = stol(str.substr(0, len));
+			auto rhs = stol(str.substr(len));
+
+			return cache[{ value, depth }] = count(lhs, depth + 1) + count(rhs, depth + 1);
+		}
+
+		return cache[{ value, depth }] = count(value * 2024, depth + 1);
+	};
+
+	cout << accumulate(data.begin(), data.end(), 0L, [&](long init, long value) { return init + count(value, 0); }) << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day11.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3