Fantastic 🙏 thanks again!

Awesome, thank you!

2-Factor authentication

Click Continue when your authenticator app shows a code with two leading zeroes.

We don’t even have that rule with CVS. Sometimes you have a merge conflict after cvs up, well then you fix it. That’s how it’s supposed to work.

C

Yes, it’s a hash table. Did I pick a language with built in hash tables? Of course I didn’t. Could I have used one of the many libraries implementing one? Sure. But the real question is, can we make do with stuffing things into a few static arrays at nearly zero memory and runtime cost? Yes!

In the spirit of Fred Brooks, it’ll suffice here to show my data structures:

struct slot { char label[8]; int lens; };
struct box { struct slot slots[8]; int nslots; };

static struct box boxes[256];

https://github.com/sjmulder/aoc/blob/master/2023/c/day15.c

That array initialisation is pure poetry! 😄

C

Chose not to do transposing/flipping or fancy indexing so it’s rather verbose, but it’s also clear and (I think) fast. I also tried to limit the number of search steps by keeping two cursors in the current row/col, rather than shooting a ray every time.

Part 2 immediately reminded me of that Tetris puzzle from day 22 last year so I knew how to find and apply the solution. State hashes are stored in an array and (inefficiently) scanned until a loop is found.

One direction of the shift function:

/*
 * Walk two cursors i and j through each column x. The i cursor
 * looks for the first . where an O can go. The j cursor looks
 * ahead for O's. When j finds a # we start again beyond it.
 */
for (x=0; x<w; x++)
for (i=0, j=1; i<h && j<h; )
	if (j <= i) j = i+1;
	else if (g[j][x] == '#') i = j+1;
	else if (g[j][x] != 'O') j++;
	else if (g[i][x] != '.') i++;
	else { g[i++][x] = 'O'; g[j++][x] = '.'; vis14_emit(); }

The main loop:

for (nleft = 1*1000*1000*1000; nleft; nleft--) {
	shift_all();

	if (!period) {
		assert(nhist < (int)LEN(hist));		
		hist[nhist++] = hash_grid();

		for (i=0; i<nhist-1; i++)
			if (hist[i] == hist[nhist-1]) {
				period = nhist-1 - i;
				nleft = nleft % period;
				break;
			}
	}
}

Full solution: https://github.com/sjmulder/aoc/blob/master/2023/c/day14.c

Very pretty again!

C

Implementing part 1 with a bunch of for loops made me wonder about elegant NumPy solutions but then part 2 came along and it was a perfect fit! Just change a flag to a counter and remove the if-match-early-exit.

https://github.com/sjmulder/aoc/blob/master/2023/c/day13.c

int main()
{
	static char g[32][32];
	int p1=0,p2=0, w,h, x,y,i, nmis;
	
	while (!feof(stdin)) {
		for (h=0; ; h++) {
			assert(h < (int)LEN(*g));
			if (!fgets(g[h], LEN(*g), stdin)) break;
			if (!g[h][0] || g[h][0]=='\n') break;
		}

		assert(h>0); w = strlen(g[0])-1;
		assert(w>0);

		for (x=1; x<w; x++) {
			nmis = 0;
			for (i=0; i<x && x+i<w; i++)
			for (y=0; y<h; y++)
				nmis += g[y][x-i-1] != g[y][x+i];
			if (nmis==0) p1 += x; else
			if (nmis==1) p2 += x;
		}

		for (y=1; y<h; y++) {
			nmis = 0;
			for (i=0; i<y && y+i<h; i++)
			for (x=0; x<w; x++)
				nmis += g[y-i-1][x] != g[y+i][x];
			if (nmis==0) p1 += y*100; else
			if (nmis==1) p2 += y*100;
		}
	}

	printf("13: %d %d\n", p1, p2);
	return 0;
}

C

That was something! I quickly settled on the main approach for part 1 but it took some unit testing to get it all right. Then part 2 had me stumped for a bit. It was clear some kind of pruning was necessary, possibly with memoization.

Hashmaps are possible but annoying with C so I was happy to realise that, for my implementation, (num chars, num runs) is a suitable key within the context of a single recursive search. That space is small enough to index with an array 😁

https://github.com/sjmulder/aoc/tree/master/2023/c/day12.c

Don’t forget to set the cbSize of the GETWITTYREPLYEXINFO structure before passing it to GetWittyReplyEx() or you’ll get funny things happening to your stack!

Yes, thank you!

C

Brute forced it, runs in 60 ms or so. Only shortcut is quitting the loop when the distance drops below the record. I didn’t bother with the closed form solution here because a) it ran so fast and b) I was concerned about floats, rounding and off-by-one errors. Will probably implement it later!

GitHub link

Edit: implemented the closed form solution. Feels dirty copying a formula without really understanding it…

GitHub link (closed form)

[C]

My first approach to part 2 was to take the list of ranges, map it to a new list of (possibly split up) ranges, etc, but I realized that would take more memory and bookkeeping than I’d like. Scrapped it and rewrote it with recursion. Much cleaner and the benchmarks are still looking good! (But for how much longer?)

$ bmake bench
day01  0:00.00  1380 Kb  0+78 faults
day02  0:00.00  1660 Kb  0+82 faults
day03  0:00.00  1540 Kb  0+107 faults
day04  0:00.00  1536 Kb  0+80 faults
day05  0:00.00  1668 Kb  0+83 faults

https://github.com/sjmulder/aoc/blob/master/2023/c/day05.c

Edit: I see some people went for looping from 0 to try possible answers. Clever and short but I wanted to go for a more efficient approach.

That’s unfortunate, although it looks good on my instance (SDF). Anything I could do?

Language: C

Another day of parsing, another day of strsep() to the rescue. Today was one of those satisfying days where the puzzle text is complicated but the solution is simple once well understood.

GitHub link

int main()
{
	char line[128], *rest, *tok;
	int nextra[200]={0}, nums[10], nnums;
	int p1=0,p2=0, id,val,nmatch, i;

	for (id=0; (rest = fgets(line, sizeof(line), stdin)); id++) {
		nnums = nmatch = 0;

		while ((tok = strsep(&rest, " ")) && !strchr(tok, ':'))
			;
		while ((tok = strsep(&rest, " ")) && !strchr(tok, '|'))
			if ((val = atoi(tok)))
				nums[nnums++] = val;
		while ((tok = strsep(&rest, " ")))
			if ((val = atoi(tok)))
				for (i=0; i<nnums; i++)
					nmatch += nums[i] == val;

		for (i=0; i<nmatch; i++)
			nextra[id+1+i] += nextra[id]+1;

		p1 += nmatch ? 1 << (nmatch-1) : 0;
		p2 += nextra[id]+1;
	}

	printf("%d %d\n", p1, p2);
	return 0;
}

Still trying to make sense of it but that part two fold is just jummy!

Here’s a tip: if you are using a language / standard library that doesn’t have a map,

Probably meant to write ‘a set’? Good trick though.

Language: C

Part 2 stumped me for a little bit, it wasn’t an obvious extension of part 1. Part 1 was about numbers (with one or more …) while part 2 worked from the symbols (with exactly two …). Going the other way would require more bookkeeping to avoid double counting.

And for the implementation: if you loop over the grid and check surrounding cells for digits you’d have to account for a bunch of cases, e.g. NW/N or N/NE being part of the same number or NW and NE being part of separate numbers. And you’d have to parse the numbers again. But building a graph or reference list of some sort is both unergonomic with C and not necessarily any simpler.

I ended up just writing out the cases, and honestly it didn’t turn out too bad.

GitHub link

int main(int argc, char **argv)
{
	static char G[GSZ][GSZ];
	static int N[GSZ][GSZ];
	int p1=0,p2=0, h=0, x,y, dx,dy, n=0,sym=0,r;
	
	for (h=0; fgets(&G[h+1][1], GSZ-1, stdin); h++)
		assert(h < GSZ);

	/*
	 * Pass 1: parse numbers and solve part 1. For every digit in
	 * G, the full number it is part of is stored in N.
	 */
	for (y=1; y<=h; y++)
	for (x=1; G[y][x]; x++)
		if (isdigit(G[y][x])) {
			n = n*10 + G[y][x]-'0';

			for (dy=-1; dy<2; dy++)
			for (dx=-1; dx<2; dx++)
				sym = sym || (x && y &&
				    G[y+dy][x+dx] != '.' &&
				    ispunct(G[y+dy][x+dx]));
		} else {
			for (dx=-1; isdigit(G[y][x+dx]); dx--)
				N[y][x+dx] = n;
			if (sym)
				p1 += n;
			n = sym = 0;
		}

	/*
	 * Pass 2: solve part 2 by finding all '*', then counting and
	 * multiplying adjecent numbers.
	 *
	 * Horizontal adjecency is trivial but vertical/diagonal has
	 * two situations: if there's a digit directly North of the '+',
	 * it must be a single number: NW and NE would connect to it.
	 * If N isn't a digit, digits in NW and NE belong to separate
	 * numbers.
	 */
	for (y=1; y<=h; y++)
	for (x=1; G[y][x]; x++) {
		if (G[y][x] != '*')
			continue;

		n = 0; r = 1;

		if (N[y][x-1]) { n++; r *= N[y][x-1]; }
		if (N[y][x+1]) { n++; r *= N[y][x+1]; }

		if (N[y-1][x]) { n++; r *= N[y-1][x]; } else {
			if (N[y-1][x-1]) { n++; r *= N[y-1][x-1]; }
			if (N[y-1][x+1]) { n++; r *= N[y-1][x+1]; }
		}

		if (N[y+1][x]) { n++; r *= N[y+1][x]; } else {
			if (N[y+1][x-1]) { n++; r *= N[y+1][x-1]; }
			if (N[y+1][x+1]) { n++; r *= N[y+1][x+1]; }
		}

		if (n == 2)
			p2 += r;
	}

	printf("%d %d\n", p1, p2);
	return 0;
}

That’s a nice golf! Clever use of the hash and nice compact reduce. I got my C both-parts solution down to 210 but it’s not half as nice.