summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authordzwdz2022-12-17 13:59:40 +0100
committerdzwdz2022-12-17 13:59:40 +0100
commitccc7912daa19de575f2f248520a3ca947281c97e (patch)
tree07f037becfb20d268275acdc92da3cc5ac24b4de
parent9ce37081a57b5eaa4ef6a94296a8a6037721e8ee (diff)
day 17 part 2
-rw-r--r--22.17/main.cpp57
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;
}