#include #include #include #include #include using namespace std; uint8_t shapes[5][4] = { { 0, 0, 0, 0b00011110 }, { 0, 0b00001000, 0b00011100, 0b00001000, }, { 0, 0b00000100, 0b00000100, 0b00011100, }, { 0b00010000, 0b00010000, 0b00010000, 0b00010000, }, { 0, 0, 0b00011000, 0b00011000, }, }; uint8_t signedShift(uint8_t a, int b) { if (0 < b) return a >> b; else return a << -b; } bool collide(vector const& map, int shapeID, int x, int y) { auto &shape = shapes[shapeID]; // y increasing upwards for (int i = 0; i < 4; i++) { uint8_t line = shape[3 - i]; if (signedShift(signedShift(line, x) & 0x7F, -x) != line) // wall coll return true; line = signedShift(line, x); if (!(y + i < map.size())) continue; if (line & map[y + i]) return true; } return false; } void place(vector& map, int shapeID, int x, int y) { auto &shape = shapes[shapeID]; for (int i = 0; i < 4; i++) { uint8_t line = signedShift(shape[3 - i], x); if (line == 0) break; if (!(y + i < map.size())) map.push_back(0); map[y + i] |= line; } } void vis(vector const& map) { char l[9] = {0}; for (int i = map.size() - 1; 0 <= i; i--) { for (int j = 0; j < 8; j++) { l[7 - j] = (map[i] & (1 << j)) ? '#' : '.'; } cout << l << endl; } cout << endl; } int getWind(string const& s, int step) { char c = s[step % s.size()]; if (c == '<') return -1; if (c == '>') return 1; cout << s << endl; throw "bad input"; } /* from nullprogram */ uint32_t lowbias32(uint32_t x) { x ^= x >> 16; x *= 0x7feb352dU; x ^= x >> 15; x *= 0x846ca68bU; x ^= x >> 16; return x; } long sim(string const& input, long blocks) { unordered_map> prev_hash; int step = 0; long heightMod = 0; vector map; map.push_back(0x7F); for (long i = 0; i < blocks; i++) { int shape = i % 5; int x = 0; int y = map.size() + 3; for (;;) { int wind = getWind(input, step++); if (!collide(map, shape, x + wind, y)) { x += wind; } if (collide(map, shape, x, y - 1)) { break; } y--; } place(map, shape, x, y); 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}; } } return map.size() - 1 + heightMod; } int main() { string input; getline(cin, input); cout << sim(input, 2022) << endl; cout << sim(input, 1000000000000) << endl; }