Index: aoc2024.c ================================================================== --- aoc2024.c +++ aoc2024.c @@ -6,37 +6,94 @@ #include #include "aocdailies.h" #include "aocutils.h" /* === aoc202422 ======================================================= -TODO: Part Two ===================================================================== */ static long long unsigned mix(long long unsigned a, long long unsigned b) { long long unsigned tmp = a ^ b; return tmp; } static long long unsigned prune(long long unsigned a) { return a % 16777216; } + +static void nextsecret(long long unsigned sec[2]) { + sec[0] = sec[1]; + sec[1] = prune(mix(sec[0] * 64, sec[0])); + sec[1] = prune(mix(sec[1] / 32, sec[1])); + sec[1] = prune(mix(sec[1] * 2048, sec[1])); +} + +static int deltamatch(int delta[4], int c[4]) { + if (delta[0] != c[0]) return 0; + if (delta[1] != c[1]) return 0; + if (delta[2] != c[2]) return 0; + if (delta[3] != c[3]) return 0; + return 1; +} void aoc202422(char *data, size_t len) { (void)len; // unused argument long long unsigned sum2000 = 0; + long long unsigned secrets[2000] = {0}; + size_t nsecrets = 0; char *key = strtok(data, "\n"); while (key) { - long long unsigned secret; - if (sscanf(key, "%llu", &secret) != 1) break; + long long unsigned secret[2]; + if (sscanf(key, "%llu", secret + 1) != 1) break; + secrets[nsecrets++] = secret[1]; for (int k = 0; k < 2000; k++) { - secret = prune(mix(secret * 64, secret)); - secret = prune(mix(secret / 32, secret)); - secret = prune(mix(secret * 2048, secret)); + nextsecret(secret); } - sum2000 += secret; + sum2000 += secret[1]; key = strtok(NULL, "\n"); } printf("The sum of all 2000th secrets is {%llu}.\n", sum2000); + + int c[4]; + int maxbananas = 0, totalbananas = 0; + for (c[0] = -9; c[0] < 10; c[0]++) { + for (c[1] = -9; c[1] < 10; c[1]++) { + for (c[2] = -9; c[2] < 10; c[2]++) { + for (c[3] = -9; c[3] < 10; c[3]++) { + totalbananas = 0; + for (size_t s = 0; s < nsecrets; s++) { + int bananas = 0; + unsigned long long sec[2] = {0, secrets[s]}; + int delta[4]; + //round0 + nextsecret(sec); + delta[0] = (sec[1] % 10) - (sec[0] % 10); + //round1 + nextsecret(sec); + delta[1] = (sec[1] % 10) - (sec[0] % 10); + //round2 + nextsecret(sec); + delta[2] = (sec[1] % 10) - (sec[0] % 10); + for (int round = 3; round < 2000; round++) { + nextsecret(sec); + delta[3] = (sec[1] % 10) - (sec[0] % 10); + if (deltamatch(delta, c)) { + bananas = sec[1] % 10; + break; + } + delta[0] = delta[1]; + delta[1] = delta[2]; + delta[2] = delta[3]; + } + totalbananas += bananas; + } + if (totalbananas > maxbananas) { + maxbananas = totalbananas; + } + } + } + } + } + printf("Maximum bananas is (%d).\n", maxbananas); } /* === aoc202417 ======================================================= TODO: proper (recursive) solution for Part Two ===================================================================== */ @@ -70,10 +127,40 @@ case 6: r[1] = r[0] / (1 << combo(operand, r)); break; case 7: r[2] = r[0] / (1 << combo(operand, r)); break; } return nextip; } + +static unsigned long long findquine(unsigned *p, unsigned np, + long long unsigned reg[4], unsigned sets3bits) { + reg[0] = reg[3]; + reg[1] = reg[2] = 0; + + unsigned output[100]; + size_t outlen = 0; + unsigned ip = 0; + while (ip + 1 < np) { + ip = instruction(ip, p[ip], p[ip+1], reg, output, &outlen); + } + + if (outlen > np) return 0; + if (outlen == np) { + for (unsigned k = 0; k < np; k++) { + if (output[k] != p[k]) return 0; + } + return 1; + } + unsigned long long saved3 = reg[3]; + for (unsigned k = 0; k < 8; k++) { + reg[3] = (saved3 << 3) + k; + if (findquine(p, np, reg, sets3bits + 1)) { + return 1; + } + reg[3] = saved3; + } + return 0; +} void aoc202417(char *data, size_t len) { (void)len; //unused argument unsigned long long reg[4]; // A, B, and C ... and copy of A for Part Two char *dta = strstr(data, " A: "), *err; @@ -106,11 +193,10 @@ for (unsigned k = 1; k < np; k++) { printf(",%u", p[k]); } printf(")\n"); - reg[3] = 202322936867370; #if 0 // I'm not happy with my "solution". // It wasn't the program who found it. // I found it by studying closer and closer attempts @@ -120,11 +206,17 @@ // I then simply calculated the output with each 3-bit value one-by-one // until I had the whole thing // someday, maybe, I'll try to write a proper recursive solution #else - printf("Start with A = %llu to get the quine.\n", reg[3]); + reg[3] = 202322936867370; + reg[3] = 0; + if (findquine(p, np, reg, 0)) { + printf("Start with A = %llu to get the quine.\n", reg[3]); + } else { + printf("Quine not found :(\n"); + } #endif } /* === aoc202409 ======================================================= WOW! input consists of a 20,000 long string of numbers!