common.c (10907B)
1 #include "common.h" 2 3 static inline size_t ceil_div(const size_t x, const size_t y) { 4 assert(y > 0); 5 return (x + y - 1) / y; 6 } 7 8 static inline size_t bitvector_len(const bitvector *b) { 9 return ceil_div(b->n, 8 * sizeof(*b->v)); 10 } 11 12 static inline size_t bitvector_remainder_bits(const bitvector *b) { 13 size_t remainder = b->n % (8 * sizeof(*b->v)); 14 return remainder == 0 ? (8 * sizeof(*b->v)) : remainder; 15 } 16 17 void bitvector_init(bitvector *b, const size_t n) { 18 b->n = n; 19 b->v = calloc(bitvector_len(b), sizeof(*b->v)); 20 } 21 22 void bitvector_clear(bitvector *b) { 23 free(b->v); 24 b->n = 0; 25 } 26 27 static inline void rotshift_r(bitvector *out, const bitvector *in) { 28 assert(out != in); 29 assert(out->n = in->n); 30 31 size_t i, l = bitvector_len(in); 32 uint64_t remainder = 0; 33 34 assert(l > 0); 35 36 for (i = 0; i < l - 1; i++) { 37 out->v[i] = remainder ? HEADBIT_U64 | (in->v[i] >> 1) : in->v[i] >> 1; 38 remainder = in->v[i] & 0x01; 39 } 40 41 const uint64_t last_remainder = 42 in->v[l - 1] & (HEADBIT_U64 >> (bitvector_remainder_bits(in) - 1)); 43 out->v[l - 1] = remainder ? HEADBIT_U64 | (in->v[l - 1] >> 1) : in->v[i] >> 1; 44 if (last_remainder) 45 out->v[0] |= HEADBIT_U64; 46 } 47 48 void rotshift_l(bitvector *out, const bitvector *in) { 49 size_t i, l = bitvector_len(in); 50 for (i = 0; i < l - 1; i++) { 51 out->v[i] = (in->v[i] << 1); 52 if ((HEADBIT_U64 & in->v[i + 1]) != 0) { 53 out->v[i]++; 54 } 55 } 56 57 out->v[l - 1] = (in->v[i] << 1); 58 if ((HEADBIT_U64 & in->v[0]) != 0) { 59 out->v[l - 1] |= (HEADBIT_U64 >> (bitvector_remainder_bits(in) - 1)); 60 } 61 } 62 63 static inline void bitvector_set(bitvector *b, const size_t n, 64 const uint64_t v) { 65 assert(v == 0 || v == 1); 66 assert(n < b->n); 67 68 const size_t i = n / (8 * sizeof(*b->v)); 69 const size_t m = n % (8 * sizeof(*b->v)); 70 71 if (v == 0) { 72 b->v[i] &= (UINT64_MAX ^ (HEADBIT_U64 >> m)); 73 } else { 74 b->v[i] |= (HEADBIT_U64 >> m); 75 } 76 } 77 78 static inline int bitvector_get(const bitvector *b, const size_t n) { 79 assert(n < b->n); 80 81 const size_t i = n / (8 * sizeof(*b->v)); 82 const size_t m = n % (8 * sizeof(*b->v)); 83 84 if ((b->v[i] & (HEADBIT_U64 >> m)) != 0) { 85 return 1; 86 } 87 return 0; 88 } 89 90 static inline void bitvector_or(bitvector *out, const bitvector *a, 91 const bitvector *b) { 92 size_t l = bitvector_len(a); 93 assert(l == bitvector_len(b)); 94 assert(l == bitvector_len(out)); 95 96 size_t i; 97 for (i = 0; i < l; i++) { 98 out->v[i] = a->v[i] | b->v[i]; 99 } 100 } 101 102 void bitvector_print(const bitvector *b) { 103 size_t i, j, l = bitvector_len(b); 104 105 for (i = 0; i < l - 1; i++) { 106 for (j = 0; j < 64; j++) { 107 if ((b->v[i] & (HEADBIT_U64 >> j)) != 0) { 108 printf("1"); 109 } else { 110 printf("0"); 111 } 112 } 113 } 114 115 const size_t remainder = bitvector_remainder_bits(b); 116 for (j = 0; j < remainder; j++) { 117 if ((b->v[l - 1] & (HEADBIT_U64 >> j)) != 0) { 118 printf("1"); 119 } else { 120 printf("0"); 121 } 122 } 123 } 124 125 static inline void parse_row(board *out, const size_t row, const char **lines, 126 const size_t nlines) { 127 assert(row < nlines - 2); 128 const char *line = lines[row + 1]; 129 130 bitvector first_rs, first_ls; 131 bitvector_init(&first_rs, out->w); 132 bitvector_init(&first_ls, out->w); 133 134 size_t i; 135 for (i = 1; i < out->w + 1; i++) { 136 if (line[i] == '>') { 137 bitvector_set(&first_rs, i - 1, 1); 138 } else if (line[i] == '<') { 139 bitvector_set(&first_ls, i - 1, 1); 140 } else { 141 assert(line[i] == '.' || line[i] == '^' || line[i] == 'v'); 142 } 143 } 144 145 bitvector trs, tls; 146 bitvector_init(&trs, out->w); 147 bitvector_init(&tls, out->w); 148 149 for (i = 0; i < out->w; i += 2) { 150 bitvector_or(&(out->row_mask[row][i]), &first_rs, &first_ls); 151 rotshift_r(&trs, &first_rs); 152 rotshift_l(&tls, &first_ls); 153 if (i + 1 < out->w) { 154 bitvector_or(&(out->row_mask[row][i + 1]), &trs, &tls); 155 rotshift_r(&first_rs, &trs); 156 rotshift_l(&first_ls, &tls); 157 } 158 } 159 160 bitvector_clear(&trs); 161 bitvector_clear(&tls); 162 bitvector_clear(&first_rs); 163 bitvector_clear(&first_ls); 164 } 165 166 static inline void parse_col(board *out, const size_t col, const char **lines, 167 const size_t nlines) { 168 assert(col < out->w); 169 170 bitvector first_rs, first_ls; 171 bitvector_init(&first_rs, out->h); 172 bitvector_init(&first_ls, out->h); 173 174 size_t i; 175 for (i = 1; i < out->h + 1; i++) { 176 if (lines[i][col + 1] == 'v') { 177 bitvector_set(&first_rs, i - 1, 1); 178 } else if (lines[i][col + 1] == '^') { 179 bitvector_set(&first_ls, i - 1, 1); 180 } else { 181 assert(lines[i][col + 1] == '.' || lines[i][col + 1] == '>' || 182 lines[i][col + 1] == '<'); 183 } 184 } 185 186 bitvector trs, tls; 187 bitvector_init(&trs, out->h); 188 bitvector_init(&tls, out->h); 189 190 for (i = 0; i < out->h; i += 2) { 191 bitvector_or(&(out->col_mask[col][i]), &first_rs, &first_ls); 192 rotshift_r(&trs, &first_rs); 193 rotshift_l(&tls, &first_ls); 194 if (i + 1 < out->h) { 195 bitvector_or(&(out->col_mask[col][i + 1]), &trs, &tls); 196 rotshift_r(&first_rs, &trs); 197 rotshift_l(&first_ls, &tls); 198 } 199 } 200 201 bitvector_clear(&trs); 202 bitvector_clear(&tls); 203 bitvector_clear(&first_rs); 204 bitvector_clear(&first_ls); 205 } 206 207 int intersects(const board *b, const uint64_t x, const uint64_t y, 208 const size_t r) { 209 assert(y < b->h); 210 assert(x < b->w); 211 212 return bitvector_get(&(b->row_mask[y][r % b->w]), x) || 213 bitvector_get(&(b->col_mask[x][r % b->h]), y); 214 } 215 216 board parse(char **lines, size_t nlines) { 217 board b; 218 b.h = nlines - 2; 219 b.w = strlen(lines[0]) - 3; 220 221 b.row_mask = malloc(b.h * sizeof(*b.row_mask)); 222 b.col_mask = malloc(b.w * sizeof(*b.col_mask)); 223 224 size_t i, j; 225 for (i = 0; i < b.h; i++) { 226 b.row_mask[i] = malloc(b.w * sizeof(*b.row_mask[0])); 227 for (j = 0; j < b.w; j++) { 228 bitvector_init(&b.row_mask[i][j], b.w); 229 } 230 } 231 232 for (i = 0; i < b.w; i++) { 233 b.col_mask[i] = malloc(b.h * sizeof(*b.col_mask[0])); 234 for (j = 0; j < b.h; j++) { 235 bitvector_init(&b.col_mask[i][j], b.h); 236 } 237 } 238 239 for (i = 0; i < b.h; i++) { 240 parse_row(&b, i, (const char **)lines, nlines); 241 } 242 243 for (i = 0; i < b.w; i++) { 244 parse_col(&b, i, (const char **)lines, nlines); 245 } 246 247 return b; 248 } 249 250 void bestfinder(board *b, uint64_t *best, uint64_t *bestend, set *s, 251 uint64_t endx, uint64_t endy) { 252 uint64_t i, r, x, y, nr, cb; 253 254 while (s->n != 0) { 255 i = 0; 256 while (s->d[i] == 0) 257 i++; 258 s->d[i] = 0; 259 s->n--; 260 261 x = i % (b->w); 262 y = (i / b->w) % b->h; 263 r = i / (b->w * b->h); 264 nr = (r + 1) % b->lcm; 265 cb = best[r * (b->w * b->h) + y * b->w + x]; 266 267 if (!intersects(b, x, y, nr) && 268 best[nr * (b->w * b->h) + y * b->w + x] > cb + 1) { 269 best[nr * (b->w * b->h) + y * b->w + x] = cb + 1; 270 if (s->d[nr * (b->w * b->h) + y * b->w + x] == 0) { 271 s->d[nr * (b->w * b->h) + y * b->w + x] = 1; 272 s->n++; 273 } 274 } 275 276 if (x > 0 && !intersects(b, x - 1, y, nr) && 277 best[nr * (b->w * b->h) + y * b->w + (x - 1)] > cb + 1) { 278 best[nr * (b->w * b->h) + y * b->w + (x - 1)] = cb + 1; 279 if (s->d[nr * (b->w * b->h) + y * b->w + (x - 1)] == 0) { 280 s->d[nr * (b->w * b->h) + y * b->w + (x - 1)] = 1; 281 s->n++; 282 } 283 } 284 285 if (x < b->w - 1 && !intersects(b, x + 1, y, nr) && 286 best[nr * (b->w * b->h) + y * b->w + (x + 1)] > cb + 1) { 287 best[nr * (b->w * b->h) + y * b->w + (x + 1)] = cb + 1; 288 if (s->d[nr * (b->w * b->h) + y * b->w + (x + 1)] == 0) { 289 s->d[nr * (b->w * b->h) + y * b->w + (x + 1)] = 1; 290 s->n++; 291 } 292 } 293 294 if (y > 0 && !intersects(b, x, y - 1, nr) && 295 best[nr * (b->w * b->h) + (y - 1) * b->w + x] > cb + 1) { 296 best[nr * (b->w * b->h) + (y - 1) * b->w + x] = cb + 1; 297 if (s->d[nr * (b->w * b->h) + (y - 1) * b->w + x] == 0) { 298 s->d[nr * (b->w * b->h) + (y - 1) * b->w + x] = 1; 299 s->n++; 300 } 301 } 302 303 if (y < b->h - 1 && !intersects(b, x, y + 1, nr) && 304 best[nr * (b->w * b->h) + (y + 1) * b->w + x] > cb + 1) { 305 best[nr * (b->w * b->h) + (y + 1) * b->w + x] = cb + 1; 306 if (s->d[nr * (b->w * b->h) + (y + 1) * b->w + x] == 0) { 307 s->d[nr * (b->w * b->h) + (y + 1) * b->w + x] = 1; 308 s->n++; 309 } 310 } 311 312 if (y == endy && x == endx) { 313 size_t j; 314 for (j = 0; j < b->lcm; j++) { 315 bestend[(nr + j) % b->lcm] = bestend[(nr + j) % b->lcm] < cb + j 316 ? bestend[(nr + j) % b->lcm] 317 : cb + j; 318 } 319 } 320 } 321 } 322 323 void play(char **lines, size_t nlines) { 324 board b = parse(lines, nlines); 325 b.lcm = 700; 326 // b.lcm = 12; 327 328 set s; 329 s.n = 0; 330 s.nalloc = b.lcm * b.h * b.w; 331 s.d = calloc(s.nalloc, sizeof(*s.d)); 332 333 uint64_t *best = malloc(s.nalloc * sizeof(*best)); 334 memset(best, 0xff, s.nalloc * sizeof(*best)); 335 336 uint64_t i, r, x, y, nr, cb; 337 uint64_t bestend[b.lcm]; 338 339 for (i = 0; i < b.lcm; i++) { 340 bestend[i] = UINT64_MAX; 341 if (!intersects(&b, 0, 0, i + 1)) { 342 best[i * (b.w * b.h)] = i + 1; 343 s.d[i * (b.w * b.h)] = 1; 344 s.n++; 345 } 346 } 347 348 bestfinder(&b, best, bestend, &s, b.w - 1, b.h - 1); 349 350 uint64_t pb[b.lcm]; 351 352 uint64_t min = UINT64_MAX; 353 for (i = 0; i < b.lcm; i++) { 354 printf("best[%llu, %zu, %zu] = %llu\n", i, b.w - 1, b.h - 1, 355 best[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)]); 356 printf("bestend[%llu] = %llu\n", i, bestend[i]); 357 if (bestend[i] < min) { 358 min = bestend[i]; 359 } 360 } 361 printf("min = %llu\n", min); 362 363 memset(best, 0xff, s.nalloc * sizeof(*best)); 364 for (i = 0; i < b.lcm; i++) { 365 uint64_t t = bestend[i]; 366 bestend[i] = UINT64_MAX; 367 if (!intersects(&b, b.w - 1, b.h - 1, i + 1)) { 368 best[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)] = t + 1; 369 s.d[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)] = 1; 370 s.n++; 371 } 372 } 373 374 bestfinder(&b, best, bestend, &s, 0, 0); 375 376 min = UINT64_MAX; 377 for (i = 0; i < b.lcm; i++) { 378 printf("best[%llu, %zu, %zu] = %llu\n", i, 0UL, 0UL, best[i * (b.w * b.h)]); 379 printf("bestend[%llu] = %llu\n", i, bestend[i]); 380 if (bestend[i] < min) { 381 min = bestend[i]; 382 } 383 } 384 printf("min = %llu\n", min); 385 386 memset(best, 0xff, s.nalloc * sizeof(*best)); 387 for (i = 0; i < b.lcm; i++) { 388 uint64_t t = bestend[i]; 389 bestend[i] = UINT64_MAX; 390 if (!intersects(&b, 0, 0, i + 1)) { 391 best[i * (b.w * b.h)] = t + 1; 392 s.d[i * (b.w * b.h)] = 1; 393 s.n++; 394 } 395 } 396 397 bestfinder(&b, best, bestend, &s, b.w - 1, b.h - 1); 398 399 min = UINT64_MAX; 400 for (i = 0; i < b.lcm; i++) { 401 printf("best[%llu, %zu, %zu] = %llu\n", i, b.w - 1, b.h - 1, 402 best[i * (b.w * b.h) + ((b.h - 1) * b.w) + (b.w - 1)]); 403 printf("bestend[%llu] = %llu\n", i, bestend[i]); 404 if (bestend[i] < min) { 405 min = bestend[i]; 406 } 407 } 408 printf("min = %llu\n", min); 409 }