uppgb.c (8265B)
1 #include "common.h" 2 3 #define DEFAULT_BOARD_SIZE 100000000 4 #define TOP_SIZE 16 // experimentally enough 5 #define MAX_NTOPS 20000 6 #define MAXJ 1000000000000L 7 8 #define NO_TOP SIZE_MAX 9 10 typedef struct { 11 size_t nalloc; 12 long cmax; 13 uint8_t *bd; 14 } board; 15 16 typedef struct { 17 size_t height; 18 uint8_t bd[4]; 19 } piece; 20 21 typedef struct { 22 uint8_t bd[TOP_SIZE]; 23 char moves[5 * TOP_SIZE]; 24 size_t midiff; 25 long cmax; 26 } top; 27 28 static top tops[MAX_NTOPS]; 29 static size_t next[MAX_NTOPS] = {0}; 30 static size_t lastnext = SIZE_MAX; 31 static size_t ntops = 0; 32 static size_t cycle_length = 0; 33 static long cycle_height = 0; 34 35 static inline int cmp_top(top a, top b) { 36 size_t i, j; 37 for (i = 0; i < TOP_SIZE; i++) { 38 if (a.bd[i] != b.bd[i]) 39 return 1; 40 for (j = 0; j < 5; j++) { 41 if (a.moves[5 * i + j] != b.moves[5 * i + j]) 42 return 1; 43 } 44 } 45 return 0; 46 } 47 48 static inline top get_top(board *b, char *moves, size_t nmoves, size_t mi, 49 size_t midiff) { 50 top r; 51 size_t i; 52 size_t si = b->cmax >= TOP_SIZE ? b->cmax - TOP_SIZE : 0; 53 for (i = 0; i < TOP_SIZE; i++) { 54 r.bd[i] = b->bd[si + i]; 55 r.moves[i] = moves[(mi + i) % nmoves]; 56 } 57 for (i = 0; i < 5 * TOP_SIZE; i++) { 58 r.moves[i] = moves[(mi + i) % nmoves]; 59 } 60 r.midiff = midiff; 61 return r; 62 } 63 64 static inline int isset(uint8_t row, size_t i) { 65 assert(i < 7); 66 if ((row & (0x40 >> i)) != 0) 67 return 1; 68 return 0; 69 } 70 71 static inline void set(uint8_t *row, size_t i) { 72 assert(i < 7); 73 *row |= (0x40 >> i); 74 } 75 76 void init_board(board *b) { 77 b->nalloc = DEFAULT_BOARD_SIZE; 78 b->cmax = -1; 79 b->bd = calloc(b->nalloc, sizeof(*b->bd)); 80 } 81 82 static inline void print_line(uint8_t v) { 83 size_t j; 84 for (j = 0; j < 7; j++) { 85 if (isset(v, j)) { 86 printf("#"); 87 } else { 88 printf("."); 89 } 90 } 91 } 92 93 void print_piece(piece p) { 94 printf("piece> h = %zu\n", p.height); 95 size_t i; 96 for (i = 0; i < p.height; i++) { 97 print_line(p.bd[i]); 98 printf("\n"); 99 } 100 } 101 102 void print_board(board *b) { 103 int i; 104 printf("+-------+\n"); 105 for (i = 0; i < b->cmax + 2; i++) { 106 printf("|"); 107 print_line(b->bd[i]); 108 printf("|\n"); 109 } 110 } 111 112 void print_top(top t) { 113 int i; 114 printf("+-------+ (%c..%c)\n", t.moves[0], t.moves[TOP_SIZE - 1]); 115 for (i = 0; i < TOP_SIZE; i++) { 116 printf("|"); 117 print_line(t.bd[i]); 118 printf("|\n"); 119 } 120 } 121 122 void print_board_with_piece(board *b, piece *p, long height) { 123 size_t i; 124 printf("+-------+\n"); 125 for (i = 0; i < height + 4; i++) { 126 uint8_t d = 0; 127 if (i < b->nalloc) { 128 d |= b->bd[i]; 129 } 130 if (i >= height && (i - height) < p->height) { 131 d |= p->bd[i - height]; 132 } 133 printf("|"); 134 print_line(d); 135 printf("|\n"); 136 } 137 } 138 139 #define SWAP(x, y) (x ^= y ^= x ^= y) 140 141 void read_pieces(piece *pcs, size_t npcs, char *filename) { 142 char **lines; 143 size_t nlines = readlines(&lines, filename); 144 size_t cp = 0; 145 size_t cpi = 0; 146 size_t i, j; 147 148 for (i = 0; i < npcs; i++) 149 memset(pcs[i].bd, 0, 4); 150 151 for (i = 0; i < nlines; i++) { 152 if (strlen(lines[i]) < 2) { 153 pcs[cp].height = cpi; 154 cp++; 155 cpi = 0; 156 continue; 157 } 158 for (j = 0; j < strlen(lines[i]); j++) { 159 if (lines[i][j] == '#') { 160 set(&(pcs[cp].bd[cpi]), j); 161 } 162 } 163 cpi++; 164 } 165 pcs[cp].height = cpi; 166 167 for (i = 0; i < npcs; i++) { 168 for (j = 0; j < pcs[i].height / 2; j++) { 169 SWAP(pcs[i].bd[j], pcs[i].bd[pcs[i].height - 1 - j]); 170 } 171 for (j = 0; j < pcs[i].height; j++) 172 pcs[i].bd[j] >>= 2; 173 } 174 } 175 176 static inline void r_push_piece(piece *p, board *b, long h) { 177 size_t i; 178 for (i = 0; i < p->height; i++) { 179 if ((p->bd[i] & 0x01) != 0) 180 return; // cannot push 181 if (((p->bd[i] >> 1) & b->bd[h + i]) != 0) 182 return; 183 } 184 185 // pushable 186 for (i = 0; i < p->height; i++) 187 p->bd[i] >>= 1; 188 } 189 190 static inline void l_push_piece(piece *p, board *b, long h) { 191 size_t i; 192 for (i = 0; i < p->height; i++) { 193 if ((p->bd[i] & 0x40) != 0) 194 return; // cannot 195 if (((p->bd[i] << 1) & b->bd[h + i]) != 0) 196 return; 197 } 198 199 // pushable 200 for (i = 0; i < p->height; i++) 201 p->bd[i] <<= 1; 202 } 203 204 static inline int can_move_up(piece *p, board *b, long cheight) { 205 size_t i; 206 if (cheight <= 0) 207 return 0; 208 for (i = 0; i < p->height; i++) { 209 if ((b->bd[i + cheight - 1] & p->bd[i]) != 0) 210 return 0; 211 } 212 return 1; 213 } 214 215 static inline void draw_piece(piece *p, board *b, long height) { 216 size_t i; 217 for (i = 0; i < p->height; i++) { 218 b->bd[i + height] |= p->bd[i]; 219 } 220 long nmax = height + p->height - 1; 221 b->cmax = nmax > b->cmax ? nmax : b->cmax; 222 } 223 224 static inline void try_lr_move(piece *p, board *b, long h, char *moves, 225 size_t nmoves, size_t *i) { 226 if (moves[*i % nmoves] == '>') { 227 r_push_piece(p, b, h); 228 } else { 229 l_push_piece(p, b, h); 230 } 231 (*i)++; 232 } 233 234 static inline size_t add_top(board *b, char *moves, size_t nmoves, size_t *i, 235 size_t midiff, top t) { 236 size_t j; 237 t.midiff = midiff; 238 239 int seen = 0; 240 for (j = 0; j < ntops; j++) { 241 if (cmp_top(t, tops[j]) == 0) { 242 seen = 1; 243 break; 244 } 245 } 246 if (seen) { 247 printf(">> seen top (ntops = %zu)\n", ntops); 248 return j; 249 } else { 250 printf(">> new top (ntops = %zu)\n", ntops); 251 assert(ntops < MAX_NTOPS); 252 tops[ntops] = t; 253 ntops++; 254 } 255 256 return ntops - 1; 257 } 258 259 void drop_piece(board *b, piece p, char *moves, size_t nmoves, size_t *i) { 260 long cheight = b->cmax + 4; 261 try_lr_move(&p, b, cheight, moves, nmoves, i); 262 while (can_move_up(&p, b, cheight)) { 263 cheight--; 264 try_lr_move(&p, b, cheight, moves, nmoves, i); 265 } 266 267 draw_piece(&p, b, cheight); 268 } 269 270 static inline size_t find_top(top *t, board *b, char *moves, size_t nmoves, 271 size_t *mi) { 272 *t = get_top(b, moves, nmoves, *mi, 0); 273 274 print_top(*t); 275 276 printf("next> "); 277 size_t j; 278 for (j = 0; j < ntops; j++) 279 printf("%zu ", next[j]); 280 printf("\n"); 281 282 int seen = 0; 283 for (j = 0; j < ntops; j++) { 284 if (cmp_top(*t, tops[j]) == 0) { 285 seen = 1; 286 break; 287 } 288 } 289 if (seen) { 290 printf(">> seen top (ntops = %zu)\n", ntops); 291 return j; 292 } 293 294 return NO_TOP; 295 } 296 297 void drop_round(board *b, piece *pcs, char *moves, size_t nmoves, size_t *mi) { 298 top t; 299 if (cycle_length == 0) { 300 size_t ti = find_top(&t, b, moves, nmoves, mi); 301 if (ti != NO_TOP) { 302 printf("ti = %zu\n", ti); 303 cycle_length = ntops - ti; 304 cycle_height = b->cmax - tops[ti].cmax; 305 printf("cycle length = %ld\n", cycle_length); 306 printf("cycle height = %ld\n", cycle_height); 307 } 308 } 309 310 size_t last_mi = *mi; 311 size_t i; 312 for (i = 0; i < 5; i++) { 313 drop_piece(b, pcs[i % 5], moves, nmoves, mi); 314 } 315 316 if (cycle_length == 0) { 317 assert(*mi >= last_mi); 318 t.cmax = b->cmax; 319 size_t new_top_idx = add_top(b, moves, nmoves, &i, *mi - last_mi, t); 320 if (lastnext != SIZE_MAX) { 321 next[lastnext] = new_top_idx; 322 lastnext = new_top_idx; 323 } else { 324 lastnext = new_top_idx; 325 } 326 } 327 } 328 329 int main(int argc, char **argv) { 330 char **lines; 331 size_t nlines = readlines(&lines, "input"); 332 printf("#lines: %lu\n", nlines); 333 334 assert(nlines == 1); 335 336 char *moves = lines[0]; 337 size_t nmoves = strlen(moves); 338 if (moves[nmoves - 1] == '\n') 339 nmoves--; 340 341 printf("#moves: %zu\n", nmoves); 342 343 board b; 344 init_board(&b); 345 346 piece pcs[5]; 347 read_pieces(pcs, 5, "pieces"); 348 349 size_t i; 350 for (i = 0; i < 5; i++) { 351 print_piece(pcs[i]); 352 } 353 354 size_t j; 355 size_t mi = 0; 356 i = 0; 357 top t; 358 size_t is[MAX_NTOPS]; 359 long skipval = 0; 360 for (j = MAXJ; j > 0; j--) { 361 drop_piece(&b, pcs[i % 5], moves, nmoves, &mi); 362 363 if (skipval == 0 && i % 5 == 0) { 364 size_t ti = find_top(&t, &b, moves, nmoves, &mi); 365 if (ti == NO_TOP) { 366 is[ntops] = i; 367 add_top(&b, moves, nmoves, &mi, 0, t); 368 } else { 369 printf("ti = %zu\n", ti); 370 long diff = b.cmax - tops[ti].cmax; 371 printf("diff = %ld\n", diff); 372 long idiff = i - is[ti]; 373 printf("idiff = %ld\n", idiff); 374 size_t jold = j; 375 j = j % (i - is[ti]); 376 printf("skipping %ld js\n", (jold - j) / idiff); 377 skipval = ((jold - j) / idiff) * diff; 378 } 379 } 380 i++; 381 } 382 383 printf("%lu\n", skipval + b.cmax + 1); 384 }