#include <ctype.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "aocdailies.h"
#include "aocutils.h"
/* === aoc202407 =======================================================
Part one looks easy
===================================================================== */
static bool canbetrue(unsigned v, unsigned *a, size_t n) {
// for startes let's assume no overflowing
if (n == 1) return (v == *a);
unsigned tmp = a[1];
a[1] = a[0] + tmp;
if (canbetrue(v, a+1, n-1)) return true;
a[1] = a[0] * tmp;
if (canbetrue(v, a+1, n-1)) return true;
a[1] = tmp;
return false;
}
void aoc202407(char *data, size_t len) {
(void)len; // unused argument
unsigned calibrationtotal = 0;
char *line = strtok(data, "\n");
unsigned number[50], nnumber, maxn = 0;
while (line) {
char *err;
unsigned testvalue = strtoul(line, &err, 10);
err += 1; // skip ':'
nnumber = 0;
while (*err == ' ') {
number[nnumber++] = strtoul(err, &err, 10);
}
if (canbetrue(testvalue, number, nnumber)) calibrationtotal += testvalue;
if (nnumber > maxn) { maxn = nnumber; printf("max: %u\n", maxn); }
line = strtok(NULL, "\n");
}
printf("The calibration total is {%u}.\n", calibrationtotal);
}
/* === 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
===================================================================== */
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';
/*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';
/*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 =======================================================
===================================================================== */
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;
#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[linearize2d(size+1, 0, 0)], data[linearize2d(size+1, 0, 1)],
data[linearize2d(size+1, 1, 0)], data[linearize2d(size+1, 1, 1)],
data[linearize2d(size+1, 2, 0)], data[linearize2d(size+1, 2, 1)]);
printf("ends with %c%c.\n", data[linearize2d(size+1, size-1, size-2)], data[linearize2d(size+1, 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);
}
/* === 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