day 17 part 2

1 files changed, 47 insertions, 10 deletions

diff --git a/22.17/main.cpp b/22.17/main.cpp
index 6a5c0cb..a0046fc 100644
--- a/22.17/main.cpp
+++ b/22.17/main.cpp
@@ -1,5 +1,7 @@
 #include <cassert>
 #include <iostream>
+#include <unordered_map>
+#include <utility>
 #include <vector>
 using namespace std;
 
@@ -93,33 +95,68 @@ getWind(string const& s, int step)
 	throw "bad input";
 }
 
-int
-main()
+/* from nullprogram */
+uint32_t
+lowbias32(uint32_t x)
 {
-	string input;
-	getline(cin, input);
+    x ^= x >> 16;
+    x *= 0x7feb352dU;
+    x ^= x >> 15;
+    x *= 0x846ca68bU;
+    x ^= x >> 16;
+    return x;
+}
 
+long
+sim(string const& input, long blocks)
+{
+	unordered_map<uint32_t, pair<int, int>> prev_hash;
 	int step = 0;
+	long heightMod = 0;
 	vector<uint8_t> map;
 	map.push_back(0x7F);
-	for (int i = 0; i < 2022; i++) {
+	for (long i = 0; i < blocks; i++) {
 		int shape = i % 5;
 		int x = 0;
 		int y = map.size() + 3;
 		for (;;) {
-			int wind;
-			wind = getWind(input, step++);
+			int wind = getWind(input, step++);
 			if (!collide(map, shape, x + wind, y)) {
 				x += wind;
 			}
-			// cout << x << "," << y << endl;
 			if (collide(map, shape, x, y - 1)) {
 				break;
 			}
 			y--;
 		}
 		place(map, shape, x, y);
-		// vis(map);
+		if (heightMod == 0 && i % (input.size() * 5) == 0) {
+			uint32_t sh = 10;
+			for (int i = 0; i < 50; i++) {
+				if (map.size() - i - 1 < 0) continue;
+				int el = map[map.size() - i - 1];
+				sh = lowbias32(sh * (el + 1));
+			}
+			if (prev_hash.count(sh) != 0) {
+				long blockRate = i - prev_hash[sh].first;
+				long heightRate = map.size() - 1 - prev_hash[sh].second;
+				long times = (blocks - i) / blockRate;
+				i += times * blockRate;
+				heightMod += times * heightRate;
+				assert(i <= blocks);
+				cerr << "skipped " << times << ", now " << i << "," << heightMod << endl;
+			}
+			prev_hash[sh] = {i, map.size() - 1};
+		}
 	}
-	cout << map.size() - 1 << endl;
+	return map.size() - 1 + heightMod;
+}
+
+int
+main()
+{
+	string input;
+	getline(cin, input);
+	cout << sim(input, 2022) << endl;
+	cout << sim(input, 1000000000000) << endl;
 }