diff options
| -rw-r--r-- | 22.17/main.cpp | 57 |
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; } |