#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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