#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aocdailies.h"
#include "aocutils.h"
static void reorder(unsigned *a, size_t na, unsigned (*r)[2], size_t nr) {
}
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;
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], accumsum2 = 0;
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);
}
static size_t rcmap(unsigned size, unsigned row, unsigned col) {
return row * (size + 1) + col;
}
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[rcmap(size, (unsigned)((int)row + drow), (unsigned)((int)col + dcol))] != 'M') return false;
if (data[rcmap(size, (unsigned)((int)row + 2*drow), (unsigned)((int)col + 2*dcol))] != 'A') return false;
if (data[rcmap(size, (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[rcmap(size, 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[rcmap(size, row, col)] != 'A') return false;
if (data[rcmap(size, row-1, col-1)] == 'M') tmp |= 1;
if (data[rcmap(size, row-1, col-1)] == 'S') tmp |= 2;
if (data[rcmap(size, row-1, col+1)] == 'M') tmp |= 4;
if (data[rcmap(size, row-1, col+1)] == 'S') tmp |= 8;
if (data[rcmap(size, row+1, col+1)] == 'M') tmp |= 1;
if (data[rcmap(size, row+1, col+1)] == 'S') tmp |= 2;
if (data[rcmap(size, row+1, col-1)] == 'M') tmp |= 4;
if (data[rcmap(size, 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;
#if 0 // check assumption
printf("data has %u cols, first three rows start with %c%c, %c%c, and %c%c.\n",
size, data[0], data[1],
data[1*(size+1)], data[1*(size+1)+1],
data[2*(size+1)], data[2*(size+1)+1]);
printf("ends with %c%c.\n", data[(size-1)*(size+1) + size-2], data[(size-1)*(size+1)+size-1]);
printf("data has %u cols, first three rows start with %c%c, %c%c, and %c%c.\n",
size, data[rcmap(size, 0, 0)], data[rcmap(size, 0, 1)],
data[rcmap(size, 1, 0)], data[rcmap(size, 1, 1)],
data[rcmap(size, 2, 0)], data[rcmap(size, 2, 1)]);
printf("ends with %c%c.\n", data[rcmap(size, size-1, size-2)], data[rcmap(size, size-1, size-1)]);
#endif
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);
}
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);
}
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);
}
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