From cf484b113493ef53b3176d3c3a67d4e0e6fe14ca Mon Sep 17 00:00:00 2001
From: Thomas Schmucker <ts@its1.de>
Date: Sun, 22 Dec 2024 23:24:08 +0100
Subject: aoc 2024, day 22, part 2

---
 2024/src/day22.cpp | 42 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)

(limited to '2024/src')

diff --git a/2024/src/day22.cpp b/2024/src/day22.cpp
index b103986..7fdc40e 100644
--- a/2024/src/day22.cpp
+++ b/2024/src/day22.cpp
@@ -1,6 +1,8 @@
 #include <cstdlib>
 #include <fstream>
 #include <iostream>
+#include <map>
+#include <set>
 #include <vector>
 using namespace std;
 
@@ -20,6 +22,7 @@ read_file(string_view filename)
 unsigned long
 step(unsigned long value)
 {
+	// compiler will optimize these calculations
 	value = (value ^ (value * 64)) % 16777216;
 	value = (value ^ (value / 32)) % 16777216;
 	value = (value ^ (value * 2048)) % 16777216;
@@ -39,9 +42,48 @@ part1(const vector<unsigned long>& values)
 	cout << sum << endl;
 }
 
+void
+part2(const vector<unsigned long>& values)
+{
+	using seq_type = tuple<unsigned long, unsigned long, unsigned long, unsigned long>;
+
+	map<seq_type, unsigned long> total;
+
+	for ( auto value: values ) {
+		vector<unsigned long> list{ value % 10 };
+
+		for ( int i = 0; i != 2000; ++i ) {
+			value = step(value);
+			list.emplace_back(value % 10);
+		}
+
+		set<seq_type> seen;
+
+		for ( size_t idx = 4; idx < list.size(); ++idx ) {
+			const auto a = list[idx - 4];
+			const auto b = list[idx - 3];
+			const auto c = list[idx - 2];
+			const auto d = list[idx - 1];
+			const auto e = list[idx];
+
+			seq_type seq{ b - a, c - b, d - c, e - d };
+
+			if ( seen.contains(seq) ) {
+				continue;
+			}
+			seen.insert(seq);
+
+			total[seq] += e;
+		}
+	}
+
+	cout << ranges::max_element(total, [](const auto& lhs, const auto& rhs) { return lhs.second < rhs.second; })->second << endl;
+}
+
 int
 main()
 {
 	auto data = read_file("data/day22.txt");
 	part1(data);
+	part2(data);
 }
-- 
cgit v1.3