day14b.cpp (1969B)
1 /* 2 I ran the simulation at 1FPS for a few minutes, staring at the screen and 3 hoping to see a Christmas tree, without luck. But I noticed that the robots 4 formed a strange "vertical" pattern every 103 timesteps, starting at t=30, 5 and a strange "horizontal" pattern every 101 timesteps, starting at t=81. 6 So I solved the diophantine equation 30+103y = 81+101x, and the smallest 7 solution (y=76, x=77) gave the correct answer t=30+103*76=7858 8 */ 9 10 #include <algorithm> 11 #include <cstdint> 12 #include <iostream> 13 #include <map> 14 #include <ranges> 15 #include <set> 16 #include <sstream> 17 #include <string> 18 #include <string_view> 19 #include <unistd.h> 20 #include <vector> 21 using namespace std; 22 23 #define N 101 24 #define M 103 25 #define T 100 26 27 char board[N][M]; 28 29 struct Robot { 30 pair<int64_t, int64_t> p, v; 31 Robot(int64_t p1, int64_t p2, int64_t v1, int64_t v2) : p(p1, p2), v(v1, v2) {} 32 }; 33 34 int quadrant(pair<int64_t, int64_t> p) { 35 if (p.first < N/2 && p.second < M/2) 36 return 1; 37 if (p.first < N/2 && p.second > M/2) 38 return 2; 39 if (p.first > N/2 && p.second < M/2) 40 return 3; 41 if (p.first > N/2 && p.second > M/2) 42 return 4; 43 return 0; 44 } 45 46 pair<int64_t, int64_t> pos(Robot r, int64_t t) { 47 return make_pair((r.p.first + t*(r.v.first+N))%N, 48 (r.p.second + t*(r.v.second+M))%M); 49 } 50 51 void visualize(vector<Robot>& robots, int64_t t) { 52 for (int i = 0; i < N; i++) 53 for (int j = 0; j < M; j++) 54 board[i][j] = ' '; 55 for (const auto& r : robots) { 56 auto [x,y] = pos(r, t); 57 board[x][y] = '*'; 58 } 59 for (int i = 0; i < N; i++) { 60 for (int j = 0; j < M; j++) 61 cout << board[i][j]; 62 cout << endl; 63 } 64 cout << endl; 65 } 66 67 int main() { 68 string line; 69 int64_t p1, p2, v1, v2, q[5] = {0}; 70 vector<Robot> r; 71 while (cin >> p1 >> p2 >> v1 >> v2) 72 r.push_back(Robot(p1, p2, v1, v2)); 73 74 75 /* Starts at the solution */ 76 for (int64_t t = 7858; ; t++) { 77 cout << "visualization of time " << t << ": " << endl; 78 sleep(1); 79 visualize(r, t); 80 } 81 82 cout << q[1] * q[2] * q[3] * q[4] << endl; 83 84 return 0; 85 }