#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aocdailies.h"
#include "aocutils.h"
/* === 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;
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;
if (TGvalid(&tg, (unsigned)anticol, (unsigned)antirow) && (*TGcharptr(&tg, (unsigned)anticol, (unsigned)antirow) != '\n')) {
unsigned *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')) {
unsigned *ff = antinode_find(anti, nanti, (unsigned)anticol, (unsigned)antirow);
if (!ff) {
anti[nanti][0] = (unsigned)anticol;
anti[nanti++][1] = (unsigned)antirow;
}
}
q = strchr(q+1, *p); // next antenna of this type
}
p += 1;
}
}
printf("There are %u antinodes within the map.\n", nanti);
}
/* === 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