aoc

commit 633104e38f45250289ab245ec16967163b308218
parent 6cbc9b03a74bcb295271de36256318d6945a2963
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sun, 22 Dec 2024 08:54:33 +0100

Day 22 2024, but it's slow

Diffstat:
A
2024/22/Makefile
 | 
11
+++++++++++
A
2024/22/day22a.cpp
 | 
32
++++++++++++++++++++++++++++++++
A
2024/22/day22b.cpp
 | 
84
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 127 insertions(+), 0 deletions(-)
diff --git a/2024/22/Makefile b/2024/22/Makefile
@@ -0,0 +1,11 @@
+CC=g++ -std=c++20 -g -Wall
+
+a:
+	${CC} -o a.out day22a.cpp
+	./a.out
+
+b:
+	${CC} -o b.out day22b.cpp
+	./b.out
+
+.PHONY: a b
diff --git a/2024/22/day22a.cpp b/2024/22/day22a.cpp
@@ -0,0 +1,32 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+int64_t next(int64_t n) {
+	constexpr int64_t M = 16777216;
+	n = ((n*64) ^ n) % M;
+	n = ((n/32) ^ n) % M;
+	n = ((n*2048) ^ n) % M;
+	return n;
+}
+
+int main() {
+	int64_t s;
+	int64_t tot = 0;
+	while (cin >> s) {
+		for (int i = 0; i < 2000; i++)
+			s = next(s);
+		tot += s;
+	}
+	cout << tot << endl;
+	return 0;
+}
diff --git a/2024/22/day22b.cpp b/2024/22/day22b.cpp
@@ -0,0 +1,84 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+class Seq {
+public:
+	int64_t k;
+
+	Seq() : k{0} {}
+
+	Seq(int kk) : k{kk} {}
+	
+	Seq(int64_t a, int64_t b, int64_t c, int64_t d)
+	    : k{(a+9)+19*((b+9)+19*((c+9)+19*(d+9)))} {}
+
+	Seq(const vector<pair<int, int>>& v, int i)
+	    : Seq(v[i-3].second, v[i-2].second, v[i-1].second, v[i].second) {}
+
+	int64_t operator[](int64_t i) const {
+		int64_t d;
+		for (d = k; i > 0; i--)
+			d /= 19;
+		return (d % 19) - 9;
+	}
+
+	bool step() {
+		return (++k) < 19*19*19*19;
+	}
+};
+
+int64_t next(int64_t n) {
+	constexpr int64_t M = 16777216;
+	n = ((n*64) ^ n) % M;
+	n = ((n/32) ^ n) % M;
+	n = ((n*2048) ^ n) % M;
+	return n;
+}
+
+int main() {
+	int64_t s;
+	vector<vector<pair<int, int>>> spc;
+	vector<map<int64_t, int64_t>> tt;
+	set<int64_t> seqs;
+
+	for (int i = 0; cin >> s; i++) {
+		spc.push_back(vector<pair<int, int>>());
+		tt.push_back(map<int64_t, int64_t>());
+
+		for (int j = 0; j < 2000; j++) {
+			int64_t t = next(s);
+			spc[i].push_back({t%10, t%10 - s%10});
+			s = t;
+			if (j >= 3) {
+				auto k = Seq(spc[i], j).k;
+				seqs.insert(k);
+				if (tt[i].count(k) == 0)
+					tt[i][k] = spc[i][j].first;
+			}
+		}
+	}
+
+	Seq seq;
+	int64_t best = 0;
+	for (auto k : seqs) {
+		Seq seq(k);
+		int64_t tot = 0;
+		for (unsigned i = 0; i < spc.size(); i++)
+			tot += tt[i][seq.k];
+		best = max(best, tot);
+	};
+
+	cout << best << endl;
+
+	return 0;
+}