#include #include #include #include #include #include #include "aocdailies.h" #include "aocutils.h" /* === aoc202422 ======================================================= ===================================================================== */ 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[2]; if (sscanf(key, "%llu", secret + 1) != 1) break; secrets[nsecrets++] = secret[1]; for (int k = 0; k < 2000; k++) { nextsecret(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]++) { int c0c1 = c[0] + c[1]; if (c0c1 < -9) continue; if (c0c1 > 9) continue; for (c[2] = -9; c[2] < 10; c[2]++) { int c1c2 = c[1] + c[2]; int c0c1c2 = c[0] + c1c2; if (c1c2 < -9) continue; if (c1c2 > 9) continue; if (c0c1c2 < -9) continue; if (c0c1c2 > 9) continue; for (c[3] = -9; c[3] < 10; c[3]++) { int c2c3 = c[2] + c[3]; int c1c2c3 = c1c2 + c[3]; int c0c1c2c3 = c0c1 + c2c3; if (c2c3 < -9) continue; if (c2c3 > 9) continue; if (c1c2c3 < -9) continue; if (c1c2c3 > 9) continue; if (c0c1c2c3 < -9) continue; if (c0c1c2c3 > 9) continue; 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 ===================================================================== */ static unsigned combo(unsigned operand, unsigned long long r[3]) { switch (operand) { default: fprintf(stderr, "Nope!\n"); exit(EXIT_FAILURE); case 0: return 0; case 1: return 1; case 2: return 2; case 3: return 3; case 4: return (unsigned)(r[0] & 0xFFFFFFFF); case 5: return (unsigned)(r[1] & 0xFFFFFFFF); case 6: return (unsigned)(r[2] & 0xFFFFFFFF); } } static unsigned instruction(unsigned ip, unsigned opcode, unsigned operand, unsigned long long r[3], unsigned *out, size_t *outlen) { unsigned nextip = ip + 2; switch (opcode) { default: case 3: if (r[0]) { nextip = operand; } break; case 0: r[0] = r[0] / (1 << combo(operand, r)); break; case 1: r[1] = r[1] ^ operand; break; case 2: r[1] = combo(operand, r) % 8; break; case 4: r[1] = r[1] ^ r[2]; break; case 5: out[*outlen] = combo(operand, r) % 8; *outlen += 1; break; 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; reg[0] = strtoull(dta + 4, &err, 10); dta = strstr(err, " B: "); reg[1] = strtoull(dta + 4, &err, 10); dta = strstr(err, " C: "); reg[2] = strtoull(dta + 4, &err, 10); dta = strstr(err, "Program: ") + 9; unsigned p[100] = {0}, np = 0; while (dta && *dta) { unsigned v = strtoul(dta, &err, 10); p[np++] = v; if (*err == 0) dta = NULL; else dta = err + 1; // skip comma } 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); } printf("Program's output is {%u", output[0]); for (unsigned k = 1; k < outlen; k++) { printf(",%u", output[k]); } printf("}\n"); printf("Program is (%u", p[0]); for (unsigned k = 1; k < np; k++) { printf(",%u", p[k]); } printf(")\n"); #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 // first I noticed that the program work 3 bits at a time, // so, to generate a sequence with 16 numbers it needs 48 bits // 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 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! Make an array of blocks, each with either -1 or the fileid For Part Two: make an array of blocks with the encoded value of (fileid * 10) + length, or, when empty, the negative length ===================================================================== */ void aoc202409(char *data, size_t len) { (void)len; // unused argument int *disk = malloc(512 * sizeof *disk); size_t rdisk = 512; size_t ndisk = 0; int fileid = 0; while (*data) { for (int k = 0; k < *data - '0'; k++) { if (ndisk == rdisk) { // assume it works rdisk = (13*rdisk)/8; disk = realloc(disk, rdisk * sizeof *disk); } disk[ndisk++] = (fileid * 10) + (*data - '0'); // encoded } fileid++; data++; if (*data) { for (int k = 0; k < *data - '0'; k++) { if (ndisk == rdisk) { // assume it works rdisk = (13*rdisk)/8; disk = realloc(disk, rdisk * sizeof *disk); } disk[ndisk++] = -1 * (*data - '0'); // negative length } data++; } } // copy disk for Part Two int *diskcopy = malloc(ndisk * sizeof *disk); memcpy(diskcopy, disk, ndisk * sizeof *disk); int *left = disk, *right = disk + ndisk; for (;;) { while (*left >= 0) left++; if (left >= right) break; while (right[-1] < 0) right--; if (left >= right) break; // swap *left and right[-1] int tmp = *--right; *right = *left; *left++ = tmp; } unsigned long long chksum = 0; size_t index = 0; while (disk[index] >= 0) { chksum += ((size_t)disk[index]/10) * index; index++; } printf("%llu\n", chksum); free(disk); // part 2 for (int filetomove = fileid - 1; filetomove > 0; filetomove--) { int *startoffile = diskcopy; while (*startoffile / 10 != filetomove) { if (*startoffile < 0) startoffile += -*startoffile; else startoffile += *startoffile % 10; } int blocksneeded = *startoffile % 10; int *bigblock = diskcopy; while (bigblock < startoffile) { if (*bigblock < 0) { if (-*bigblock < blocksneeded) { bigblock += -*bigblock; } else { // found a suitable block: move and quit tightest loop int bbsize = -*bigblock; int k; for (k = 0; k < blocksneeded; k++) { int tmp = startoffile[k]; startoffile[k] = bigblock[k]; bigblock[k] = tmp; } for (; k < bbsize; k++) { bigblock[k] += blocksneeded; } break; } } else { bigblock += *bigblock % 10; } } } unsigned long long chksum2 = 0; index = 0; for (index = 0; index < ndisk; index++) { if (diskcopy[index] > 0) { chksum2 += ((size_t)diskcopy[index]/10) * index; } } printf("%llu\n", chksum2); free(diskcopy); } /* === aoc202408 ======================================================= Oh! another square of text! Idea: for all points p with an antenna find all points q>p with a corresponding frequency. For each such pair calculate the 2 antinodes and add the resulting points (if not there already) to an array. The answer to Part One is the number of elements in the array ===================================================================== */ static unsigned *antinode_find(unsigned (*a)[2], size_t n, unsigned col, unsigned row) { for (size_t k = 0; k < n; k++) { if ((a[k][0] == col) && (a[k][1] == row)) return a[k]; } return NULL; } void aoc202408(char *data, size_t len) { (void)len; // unused argument struct TextGrid tg; tg.data = data; tg.cols = strchr(data, '\n') - data + 1; tg.rows = tg.cols - 1; // rows includes the '\n' unsigned anti[512][2]; // locations of antinodes; col at index 0, row at 1 unsigned nanti = 0; unsigned anti2[1024][2]; // locations of antinodes; col at index 0, row at 1 unsigned nanti2 = 0; char *p = data; while (*p) { while ((*p == '.') || (*p == '\n')) p++; if (*p) { // p points to an antenna unsigned prow = TGrow(&tg, p), pcol = TGcol(&tg, p); char *q = strchr(p+1, *p); while (q) { // q points to an antenna of the same type as p unsigned qrow = TGrow(&tg, q), qcol = TGcol(&tg, q); int deltarow = (int)qrow - (int)prow; int deltacol = (int)qcol - (int)pcol; int anticol = (int)pcol - deltacol; int antirow = (int)prow - deltarow; unsigned *ff; if (TGvalid(&tg, (unsigned)anticol, (unsigned)antirow) && (*TGcharptr(&tg, (unsigned)anticol, (unsigned)antirow) != '\n')) { ff = antinode_find(anti, nanti, (unsigned)anticol, (unsigned)antirow); if (!ff) { anti[nanti][0] = (unsigned)anticol; anti[nanti++][1] = (unsigned)antirow; } } anticol = (int)qcol + deltacol; antirow = (int)qrow + deltarow; if (TGvalid(&tg, (unsigned)anticol, (unsigned)antirow) && (*TGcharptr(&tg, (unsigned)anticol, (unsigned)antirow) != '\n')) { ff = antinode_find(anti, nanti, (unsigned)anticol, (unsigned)antirow); if (!ff) { anti[nanti][0] = (unsigned)anticol; anti[nanti++][1] = (unsigned)antirow; } } int k; // q - delta is p; q -2delta is one afterwards, etc // add q - (k)delta to anti2 while valid k = 1; while (TGvalid(&tg, (unsigned)((int)qcol-k*deltacol), (unsigned)((int)qrow-k*deltarow)) && (*TGcharptr(&tg, (unsigned)((int)qcol-k*deltacol), (unsigned)((int)qrow-k*deltarow)) != '\n')) { ff = antinode_find(anti2, nanti2, (unsigned)((int)qcol-k*deltacol), (unsigned)((int)qrow-k*deltarow)); if (!ff) { anti2[nanti2][0] = (unsigned)((int)qcol-k*deltacol); anti2[nanti2++][1] = (unsigned)((int)qrow-k*deltarow); } k++; } // p + delta is q; p +2delta is one afterwards, etc // add p + (k)delta to anti2 while valid k = 1; while (TGvalid(&tg, (unsigned)((int)pcol+k*deltacol), (unsigned)((int)prow+k*deltarow)) && (*TGcharptr(&tg, (unsigned)((int)pcol+k*deltacol), (unsigned)((int)prow+k*deltarow)) != '\n')) { ff = antinode_find(anti2, nanti2, (unsigned)((int)pcol+k*deltacol), (unsigned)((int)prow+k*deltarow)); if (!ff) { anti2[nanti2][0] = (unsigned)((int)pcol+k*deltacol); anti2[nanti2++][1] = (unsigned)((int)prow+k*deltarow); } k++; } // next antenna of this type q = strchr(q+1, *p); } p += 1; } } printf("There are %u antinodes within the map.\n", nanti); printf("There are %u resonant antinodes within the map.\n", nanti2); } /* === aoc202407 ======================================================= Part one looks easy Part two also easy ===================================================================== */ static unsigned long long concat(unsigned long long a, unsigned long long b) { unsigned long long r = a, t = b; while (b) { r *= 10; b /= 10; } return r + t; } static int operatorsrequired(unsigned long long v, unsigned long long *a, size_t n, int minop) { // assumes no unsigned long long overflowing if (n == 1) { if (v == *a) return minop; return 0; } unsigned long long tmp = a[1]; int pplus, pmult, pconcat = 0; a[1] = a[0] + tmp; pplus = operatorsrequired(v, a+1, n-1, 2); a[1] = tmp; a[1] = a[0] * tmp; pmult = operatorsrequired(v, a+1, n-1, 2); a[1] = tmp; if (!pplus && !pmult) { a[1] = concat(a[0], tmp); pconcat = operatorsrequired(v, a+1, n-1, 3); a[1] = tmp; } if (pconcat) return 3; if (pplus || pmult) return (pplus > pmult) ? pplus : pmult; return 0; } void aoc202407(char *data, size_t len) { (void)len; // unused argument unsigned long long calibrationtotal = 0, calibration3total = 0; char *line = strtok(data, "\n"); unsigned long long number[50], nnumber; while (line) { char *err; unsigned long long testvalue = strtoull(line, &err, 10); err += 1; // skip ':' nnumber = 0; while (*err == ' ') { number[nnumber++] = strtoul(err, &err, 10); } switch (operatorsrequired(testvalue, number, nnumber, 0)) { default: break; case 2: calibrationtotal += testvalue; __attribute__((fallthrough)); case 3: calibration3total += testvalue; break; } line = strtok(NULL, "\n"); } printf("The calibration total is {%llu}.\n", calibrationtotal); printf("The calibration total with three operators is {%llu}.\n", calibration3total); } /* === aoc202406 ======================================================= Hmmm, I've done something like this already this year... on day 4 I need rcmap() moved to aocutils ... done; now it's called `linearize2d` Part Two: brute force? It likely is faster than coming up with an algo Let's go: save map, for every available position put in an obstacle, loop around until some place is visited 4? times or area is exited TODO remove linearize2d ===================================================================== */ static bool validpos(unsigned s, int r, int c) { if (r < 0) return false; if (c < 0) return false; if ((unsigned)r >= s - 1) return false; if ((unsigned)c >= s - 1) return false; return true; } static void rightturn(int *drow, int *dcol) { if (*drow) { *dcol = -*drow; *drow = 0; } else { *drow = *dcol; *dcol = 0; } } void aoc202406(char *data, size_t len) { char *savedmap = malloc(len + 1); strcpy(savedmap, data); // assume data is well-formatted and has the same number of rows and columns unsigned size = 1 + strchr(data, '\n') - data; unsigned linear_pos = strchr(data, '^') - data; int row_pos = (int)(linear_pos / size); int col_pos = (int)(linear_pos % size); int deltarow = -1, deltacol = 0; //printf("character at [%u, %u] is '%c'\n", row_pos, col_pos, data[linearize2d(size, row_pos, col_pos)]); unsigned visited = 1; data[linearize2d(size, (unsigned)row_pos, (unsigned)col_pos)] = 'X'; // initial place visited while (validpos(size, row_pos + deltarow, col_pos + deltacol)) { switch (data[linearize2d(size, (unsigned)(row_pos+deltarow), (unsigned)(col_pos+deltacol))]) { default: exit(EXIT_FAILURE); // does not happen case '#': rightturn(&deltarow, &deltacol); break; case '.': visited++; data[linearize2d(size, (unsigned)(row_pos+deltarow), (unsigned)(col_pos+deltacol))] = 'X'; __attribute__((fallthrough)); case 'X': row_pos += deltarow; col_pos += deltacol; break; } } printf("The guard visits %u positions before leaving the area.\n", visited); // Part Two unsigned rowblock = 0, colblock = 0, positions = 0; int row_initial = (int)(linear_pos / size); int col_initial = (int)(linear_pos % size); for (;;) { strcpy(data, savedmap); if (data[linearize2d(size, (unsigned)rowblock, (unsigned)colblock)] == '.') { data[linearize2d(size, (unsigned)rowblock, (unsigned)colblock)] = '#'; // block it row_pos = row_initial; col_pos = col_initial; deltarow = -1; deltacol = 0; data[linearize2d(size, (unsigned)row_pos, (unsigned)col_pos)] = '1'; bool looping = false; while (!looping && validpos(size, row_pos + deltarow, col_pos + deltacol)) { switch (data[linearize2d(size, (unsigned)(row_pos+deltarow), (unsigned)(col_pos+deltacol))]) { default: puts("stepped on default"); exit(EXIT_FAILURE); case '#': if (data[linearize2d(size, (unsigned)(row_pos), (unsigned)(col_pos))] == '4') looping = true; rightturn(&deltarow, &deltacol); break; case '4': looping = true; break; case '.': data[linearize2d(size, (unsigned)(row_pos+deltarow), (unsigned)(col_pos+deltacol))] = '0'; __attribute__((fallthrough)); case '1': case '2': case '3': data[linearize2d(size, (unsigned)(row_pos+deltarow), (unsigned)(col_pos+deltacol))]++; row_pos += deltarow; col_pos += deltacol; break; } } if (looping) positions++; } colblock++; if (colblock == size) { colblock = 0; rowblock++; if (rowblock == size) break; } } printf("You can obstruct %u different positions.\n", positions); free(savedmap); } /* === aoc202405 ======================================================= ===================================================================== */ static int ppcmp(unsigned a, unsigned b, unsigned (*r)[2], size_t nr) { for (size_t k = 0; k < nr; k++) { if ((a == r[k][0]) && (b == r[k][1])) return -1; if ((a == r[k][1]) && (b == r[k][0])) return 1; } return 0; } // can't be bothered to do anything other than bubble sort static void reorder(unsigned *a, size_t na, unsigned (*r)[2], size_t nr) { for (size_t range = na; --range > 0; /*void*/) { for (size_t outer = 0; outer < range; outer++) { if (ppcmp(a[outer], a[outer+1], r, nr) > 0) { unsigned tmp = a[outer]; a[outer] = a[outer+1]; a[outer+1] = tmp; } } } } static const unsigned *vfind(unsigned v, const unsigned *a, size_t n) { for (size_t k = 0; k < n; k++) { if (a[k] == v) return a + k; } return NULL; } void aoc202405(char *data, size_t len) { (void)len; // unused argument unsigned pagepair[1200][2], npp = 0; // 1200 works for me char *line = strtok(data, "\n"); while (strchr(line, '|')) { char *err; pagepair[npp][0] = strtoul(line, &err, 10); err += 1; // skip '|' pagepair[npp][1] = strtoul(err, &err, 10); npp++; line = strtok(NULL, "\n"); } unsigned update[32], nupdates; // 32 works for me unsigned accumsum = 0, accumsum2 = 0; do { nupdates = 0; char *err = line; for (;;) { update[nupdates++] = strtoul(err, &err, 10); if (*err == ',') err++; else break; } if (nupdates % 2 == 0) printf("even number of updates found!\n"); unsigned accum = update[nupdates / 2]; for (size_t k = 0; k < npp; k++) { const unsigned *before = vfind(pagepair[k][0], update, nupdates); if (!before) continue; const unsigned *after = vfind(pagepair[k][1], update, nupdates); if (!after) continue; if (before > after) { accum = 0; // reorder `update` according to `pagepair` reorder(update, nupdates, pagepair, npp); accumsum2 += update[nupdates / 2]; break; } } accumsum += accum; } while ((line = strtok(NULL, "\n")) != NULL); printf("The sum of middle update numbers is {%u}.\n", accumsum); printf("The sum of middle update numbers for newly ordered updates is {%u}.\n", accumsum2); } /* === aoc202404 ======================================================= TODO remove linearize2d ===================================================================== */ static bool masat(char *data, unsigned size, unsigned row, unsigned col, int drow, int dcol) { int maxrow = (int)row + 3*drow; int maxcol = (int)col + 3*dcol; if ((0 <= maxrow) && (maxrow < (int)size) && (0 <= maxcol) && (maxcol < (int)size)) { if (data[linearize2d(size+1, (unsigned)((int)row + drow), (unsigned)((int)col + dcol))] != 'M') return false; if (data[linearize2d(size+1, (unsigned)((int)row + 2*drow), (unsigned)((int)col + 2*dcol))] != 'A') return false; if (data[linearize2d(size+1, (unsigned)((int)row + 3*drow), (unsigned)((int)col + 3*dcol))] != 'S') return false; } else { return false; } return true; } static unsigned xmasat(char *data, unsigned size, unsigned row, unsigned col) { unsigned finds = 0; if (data[linearize2d(size+1, row, col)] != 'X') return 0; if (masat(data, size, row, col, -1, -1)) finds++; if (masat(data, size, row, col, -1, 0)) finds++; if (masat(data, size, row, col, -1, +1)) finds++; if (masat(data, size, row, col, 0, -1)) finds++; if (masat(data, size, row, col, 0, +1)) finds++; if (masat(data, size, row, col, +1, -1)) finds++; if (masat(data, size, row, col, +1, 0)) finds++; if (masat(data, size, row, col, +1, +1)) finds++; return finds; } static bool Xmasat(char *data, unsigned size, unsigned row, unsigned col) { unsigned tmp = 0; if (data[linearize2d(size+1, row, col)] != 'A') return false; if (data[linearize2d(size+1, row-1, col-1)] == 'M') tmp |= 1; if (data[linearize2d(size+1, row-1, col-1)] == 'S') tmp |= 2; if (data[linearize2d(size+1, row-1, col+1)] == 'M') tmp |= 4; if (data[linearize2d(size+1, row-1, col+1)] == 'S') tmp |= 8; if (data[linearize2d(size+1, row+1, col+1)] == 'M') tmp |= 1; if (data[linearize2d(size+1, row+1, col+1)] == 'S') tmp |= 2; if (data[linearize2d(size+1, row+1, col-1)] == 'M') tmp |= 4; if (data[linearize2d(size+1, row+1, col-1)] == 'S') tmp |= 8; return (tmp == 15); } void aoc202404(char *data, size_t len) { (void)len; // unused argument // assume data is well-formatted and has the same number of rows and columns unsigned size = strchr(data, '\n') - data; unsigned xmascount = 0, Xmascount = 0; for (unsigned row = 0; row < size; row++) { for (unsigned col = 0; col < size; col++) { xmascount += xmasat(data, size, row, col); if ((1 <= row) && (row < size - 1) && (1 <= col) && (col < size - 1)) { if (Xmasat(data, size, row, col)) Xmascount++; } } } printf("XMAS appears %u times in the little Elf's word search.\n", xmascount); printf("X-MAS appears %u times in the little Elf's word search.\n", Xmascount); } /* === aoc202403 ======================================================= ===================================================================== */ void aoc202403(char *data, size_t len) { (void)len; // unused argument unsigned sumproducts = 0, sumproducts2 = 0, term[2]; char *rest = data; char *doleft = data; char *dorite = strstr(data + 1, "do()"); char *dontleft = data; char *dontrite = strstr(dontleft + 1, "don't()"); for (;;) { char *mul = strstr(rest, "mul("); if (mul) { // make sure `doleft` and `dorite` are to the left and right of `mul` while (dorite && (mul > dorite)) { doleft = dorite; dorite = strstr(dorite + 1, "do()"); } // also for `dontleft` and `dontrite` while (dontrite && (mul > dontrite)) { dontleft = dontrite; dontrite = strstr(dontrite + 1, "don't()"); } rest = mul + 4; if (isdigit((unsigned char)rest[0])) { char *err; term[0] = strtoul(rest, &err, 10); if (*err == ',') { if (isdigit((unsigned char)err[1])) { rest = err + 1; term[1] = strtoul(rest, &err, 10); if (*err == ')') { sumproducts += term[0] * term[1]; // multiply by 0 if closest conditional to the left is "don't()" sumproducts2 += (doleft >= dontleft) * (term[0] * term[1]); rest = err + 1; } } } } } else { break; } } printf("The sum of the products is {%u}.\n", sumproducts); printf("The sum of the products with conditionals is {%u}.\n", sumproducts2); } /* === aoc202402 ======================================================= ===================================================================== */ static bool safereport(unsigned *v, size_t nv) { int dir = 1; // ascending if (v[0] > v[1]) dir = -1; // descending for (size_t k = 1; k < nv; k++) { if (v[k-1] == v[k]) return false; if (distance(v[k-1], v[k]) > 3) return false; if (dir == -1) { if (v[k-1] < v[k]) return false; } else { if (v[k-1] > v[k]) return false; } } return true; } static bool safereportdamp(unsigned *v, size_t nv) { for (size_t swap = 0; swap < nv; swap++) { // abcd...wx unsigned tmp = v[swap]; // swap(0, 0): abcd...wx v[swap] = v[0]; // swap(1, 0): bacd...wx v[0] = tmp; // swap(2, 0): cabd...wx if (safereport(v + 1, nv - 1)) return true; // ... and so on ... } // swap(n-1, 0): xabc...vw return false; } void aoc202402(char *data, size_t len) { (void)len; // unused argument unsigned safe = 0, safe2 = 0; char *line = strtok(data, "\n"); while (line) { unsigned *arr = NULL; size_t narr = text2array(&arr, line); if (safereport(arr, narr)) { safe += 1; safe2 += 1; } else { safe2 += safereportdamp(arr, narr) ? 1 : 0; } free(arr); line = strtok(NULL, "\n"); } printf("There are %u safe reports.\n", safe); printf("There are %u safe reports with the Problem Dampener.\n", safe2); } /* === aoc202401 ======================================================= ===================================================================== */ static int delta(const void *a, const void *b) { const unsigned *aa = a; const unsigned *bb = b; if (*aa > *bb) return 1; if (*aa < *bb) return -1; return 0; } #ifdef LISTSIZE # error LISTSIZE already defined #endif #define LISTSIZE 1200 void aoc202401(char *data, size_t len) { (void)len; // unused argument unsigned v[2]; // values from data char *err; unsigned list1[LISTSIZE], list2[LISTSIZE]; // the lists size_t n1 = 0, n2 = 0; while ((v[0] = strtoul(data, &err, 10))) { // assume well-formatted data data = err; v[1] = strtoul(data, &err, 10); data = err; list1[n1++] = v[0]; // add v[0] to list1 list2[n2++] = v[1]; // add v[1] to list2 } // redundant check :-) if (n1 != n2) printf("Error: list are not the same size\n"); // sort the lists qsort(list1, n1, sizeof *list1, delta); qsort(list2, n2, sizeof *list2, delta); // part1 unsigned sumdeltas = 0; for (size_t k = 0; k < n1; k++) { sumdeltas += (list1[k] > list2[k]) ? list1[k] - list2[k] : list2[k] - list1[k]; } printf("Total distance between lists is {%u}.\n", sumdeltas); // part2 unsigned similarity = 0; for (size_t k = 0; k < n1; k++) { #if 1 // use the fact lists are sorted: complexity: O(n log n) unsigned leftcount = 1; // number of equal values in list1 while ((k + leftcount < n1) && (list1[k] == list1[k + leftcount])) leftcount++; // find list1 k'ths value in list2 unsigned *p = bsearch(list1 + k, list2, n2, sizeof *list2, delta); if (p) { ptrdiff_t idxl = p - list2; // search backwards and forwards in list2 ptrdiff_t idxr = p - list2; // for the k'th value in list1 while ((idxl > 0) && (list2[idxl - 1] == *p)) idxl -= 1; while ((idxr < (int)n2 - 1) && (list2[idxr + 1] == *p)) idxr += 1; unsigned rightcount = idxr - idxl + 1; // number of repeats in list2 similarity += *p * rightcount * leftcount; } k += leftcount - 1; // adjust loop control variable #else // loop inside loop: complexity O(n^2); don't care lists are sorted unsigned count = 0; for (size_t kk = 0; kk < n2; kk++) { if (list1[k] == list2[kk]) count++; } similarity += list1[k] * count; #endif } printf("Similarity score between lists is {%u}.\n", similarity); } #undef LISTSIZE