diff options
| -rw-r--r-- | 17.c | 132 |
1 files changed, 125 insertions, 7 deletions
@@ -2,6 +2,7 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <unistd.h> #define arrlen(x) (sizeof(x)/sizeof((x)[0])) @@ -21,6 +22,72 @@ struct rock const rocks[] = { }; +struct cheat { + unsigned long depth; + struct rock rock; + unsigned long num; + unsigned long pos; +}; + + +unsigned long +cheat_numdiff(struct cheat * cheats, int ncheats) +{ + return cheats[0].num - cheats[1].num; +} + + +unsigned long +cheat_posdiff(struct cheat * cheats, int ncheats) +{ + return cheats[0].pos - cheats[1].pos; +} + + +int +cheat_check(struct cheat * cheats, int ncheats, + unsigned long depth, struct rock const * rock, + unsigned long rocknum, unsigned long position) +{ + unsigned long numdiff, posdiff; + int i; + + if (depth < cheats[0].depth) + // Not deep enough. + return 0; + + if (depth == cheats[0].depth + && memcmp(rock, &cheats[0].rock, sizeof(struct rock)) != 0) + // Same depth as previously, but differnt rock, or in different + // position in chamber. + return 0; + + // Rock is either deeper than any previous, or is as deep and is the + // same rock in the same position in the chamber + + fprintf(stderr, "Deepest rock %lu (depth %lu, height %lu)\n", + rocknum, depth, position); + + memmove(cheats + 1, cheats, sizeof(struct cheat) * (ncheats - 1)); + cheats[0].depth = depth; + cheats[0].rock = *rock; + cheats[0].num = rocknum; + cheats[0].pos = position; + + numdiff = cheat_numdiff(cheats, ncheats); + posdiff = cheat_posdiff(cheats, ncheats); + + for (i = 2; i < ncheats; ++i) + if (cheats[i - 1].num - cheats[i].num != numdiff + || cheats[i - 1].pos - cheats[i].pos != posdiff) + // Not all the cheats are the same + return 0; + + // All the cheats are the same! + return 1; +} + + #if 0 void chamber_dump(unsigned char * chamber, int chamberheight, struct rock * rock, int rockheight) @@ -53,16 +120,44 @@ chamber_dump(unsigned char * chamber, int chamberheight, struct rock * rock, int int -main() +main(int argc, char ** argv) { + int docheat = 0; size_t jetsize = 0; char * jets = NULL; unsigned char * chamber = NULL; - int chamberheight = 0, top = 0; - int movement, rocknum, rockheight; + unsigned long chamberheight = 0, top = 0, cheatby = 0; + unsigned long movement, rocknum, rockheight; + unsigned long rocklimit = 2022; + struct cheat cheats[10] = {0}; struct rock rock; int i; + while ((i = getopt(argc, argv, "p:r:c")) != -1) { + switch (i) { + case 'p': + switch (atoi(optarg)) { + case 1: rocklimit = 2022; break; + case 2: rocklimit = 1000000000000; break; + default: + fprintf(stderr, "Bad part: %s\n", optarg); + return -1; + } + break; + + case 'r': + rocklimit = atol(optarg); + break; + + case 'c': + docheat = 1; + break; + + default: + return -1; + } + } + // Read jets. while (1) { void * p; @@ -92,15 +187,16 @@ main() rock = rocks[rocknum]; rockheight = 3; - for (movement = 0; rocknum < 2022; ++movement) { + for (movement = 0; rocknum < rocklimit; ++movement) { int jet; - if (top > chamberheight - 10) { + if (!chamberheight || top > chamberheight - 10) { void * p; if ((p = realloc(chamber, chamberheight + BUFSIZ)) == NULL) { - fprintf(stderr, "Bad realloc(%d)\n", chamberheight + BUFSIZ); + fprintf(stderr, "Bad realloc(%lu)\n", chamberheight + BUFSIZ); free(chamber); + free(jets); return -1; } chamber = p; @@ -149,6 +245,28 @@ main() top = rockheight + i; } + // Check to see if we can cheat + if (docheat + && rocknum > arrlen(rocks) * jetsize + && rockheight < top + && cheat_check(cheats, arrlen(cheats), + top - rockheight, &rock, + rocknum, rockheight)) + { + unsigned long numdiff, posdiff, steps; + + numdiff = cheat_numdiff(cheats, arrlen(cheats)); + posdiff = cheat_posdiff(cheats, arrlen(cheats)); + + steps = (rocklimit - rocknum) / numdiff; + + fprintf(stderr, "Cheating from rock %lu to %lu in %lu steps of %lu rocks/%lu height\n", + rocknum, rocklimit, steps, numdiff, posdiff); + + rocknum += steps * numdiff; + cheatby += steps * posdiff; + } + // Pick next rock. rock = rocks[++rocknum % arrlen(rocks)]; rockheight = top + 4; @@ -163,7 +281,7 @@ main() } } - printf("Height of rocks in chamber: %d\n", top + 1); + printf("Height of rocks in chamber: %lu\n", top + cheatby + 1); free(chamber); free(jets); |