Work: Windows + Rider/WebStorm/etc (I used the IdeaVim plugin before but found there were too many rough edges)

Home: Debian or OpenBSD + vi or Pluma. I deliberately keep it simple. A terminal, an editor Ctrl+Z, make, fg, that kind of thing. I’m tired of fighting IDEs to get out of my way. Let me type!

What are we calling brute force here? Continuing to go through the pair list and merging groups? Is there any other way?

the trap

Re. what connections to process or not? That seems to be like one of those that’s either completely obvious when you implement your solution one way, and a nasty pitfall when you do it another. In this case, pre-computing the list of pairs to process vs. finding the next one when you need it.

C

Got stuck for a bit on part 1 on a silly mistake in the group (circuit) merging code, where the nodes from one group are reassigned to the other:

for (i=0; i < nnodes; i++)
        if (nodes[i].group == pair->b->group)
                nodes[i].group = pair->a->group;

At some point in the loop pair->b.group itself is updated, from then on the check is against the new group value. Oops.

In the end, my solution’s runtime on my (10 year old!) PC is about 160 ms for both parts, which is more than I would like, so maybe I’ll look into better set representations.

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <assert.h>

#define LEN(a)		(sizeof(a)/sizeof(*(a)))
#define NPAIRS(x)	((x)*((x)-1)/2)

#define MAXN	1024

struct node { int x,y,z, group; };
struct pair { struct node *a, *b; int64_t dist_sq; };
struct group { int count; };

static struct node nodes[MAXN];
static struct pair pairs[NPAIRS(MAXN)];
static struct group groups[MAXN];

static int nnodes;
static int ngroups;

static int64_t
node_dist_sq(const struct node *a, const struct node *b)
{
	return
	    (int64_t)(a->x - b->x) * (a->x - b->x) +
	    (int64_t)(a->y - b->y) * (a->y - b->y) +
	    (int64_t)(a->z - b->z) * (a->z - b->z);
}

static int
cmp_pairs(const void *va, const void *vb)
{
	const struct pair *a = va;
	const struct pair *b = vb;

	return
	    a->dist_sq < b->dist_sq ? -1 :
	    a->dist_sq > b->dist_sq ?  1 : 0;
}

static int
cmp_groups_asc(const void *va, const void *vb)
{
	const struct group *a = va;
	const struct group *b = vb;

	return b->count - a->count;
}

static void
merge_groups(int group_a, int group_b)
{
	int i;

	if (group_a == group_b)
		return;

	groups[group_a].count += groups[group_b].count;
	groups[group_b].count = 0;

	for (i=0; i<nnodes; i++)
		if (nodes[i].group == group_b)
			nodes[i].group = group_a;
	
	ngroups--;
}

int
main()
{
	int p1=0,p2=0, p1_limit, i,j, n,p;

	for (; ; nnodes++) {
		assert(nnodes < MAXN);
		n = scanf(" %d,%d,%d",
		    &nodes[nnodes].x,
		    &nodes[nnodes].y,
		    &nodes[nnodes].z);
		if (n < 3)
			break;
		nodes[nnodes].group = nnodes;
		groups[nnodes].count = 1;
	}

	ngroups = nnodes;

	for (p=0, i=0; i<nnodes-1; i++)
	for (j=i+1; j<nnodes; j++, p++) {
		pairs[p].a = &nodes[i];
		pairs[p].b = &nodes[j];
		pairs[p].dist_sq = node_dist_sq(&nodes[i], &nodes[j]);
	}

	qsort(pairs, NPAIRS(nnodes), sizeof(*pairs), cmp_pairs);

	p1_limit = nnodes <= 100 ? 10 : 1000;

	for (i=0; ngroups > 1; i++) {
		merge_groups(pairs[i].a->group, pairs[i].b->group);

		if (ngroups == 1)
			p2 = pairs[i].a->x * pairs[i].b->x;

		if (i == p1_limit) {
			qsort(groups, LEN(groups), sizeof(*groups),
			    cmp_groups_asc);

			p1 = groups[0].count *
			     groups[1].count *
			     groups[2].count;
		}
	}

	printf("08: %d %d\n", p1, p2);
}

If I understand correctly, your visualization shows up to to 256 unique paths then?

In this one, every time the beam passes a splitter, the other side is put on a queue, so eventually all possible paths are traced, breadth first. Initially I worked through the options recursively, but that depth-first filling out was boring to look at.

Well it uses the input of course but I found that if you make it truly random, the lines mostly go down in a straight line, all bunching up in the middle, which isn’t very pleasing. So now the beams have a “current direction” which has a 25% of flipping at every splitter

In 16-bit real mode assembly, as a hybrid DOS .COM program and BIOS-bootable disk image. With bonus palette animations! I had the hybrid thing going on before (see the repo), but this is the first time getting something animated.

Repo | day07.com (12 KB) | full video

Ahh I knew there would be some simple combined representation like this but couldn’t be bothered. Nice!

C

Accidentally solved part 2 first but had the foresight to save the code. Otherwise my solution looks similar to what other people are doing, just with more code 😅

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <assert.h>

#define GW 148
#define GH 74

static char g[GH][GW];
static uint64_t dp[2][GW];
static int w,h;

/* recursively traces beam for part 1, marking visited splitters with 'X' */
static uint64_t
solve_p1(int x, int y)
{
	if (x<0 || x>=w || y<0 || y>=h || g[y][x] == 'X')
		return 0;
	else if (g[y][x] != '^')
		return solve_p1(x, y+1);
	else {
		g[y][x] = 'X';
		return 1 + solve_p1(x-1, y) + solve_p1(x+1, y);
	}
}

/* DP for part 2 */
static uint64_t
solve_p2(void)
{
	int x,y, odd;

	for (y=h-1; y>=0; y--)
	for (x=1; x<w-1; x++) {
		/* only two rows relevant at a time, so don't store any more */
		odd = y&1;

		if (g[y][x] == 'S') {
			printf("\n");
			return dp[!odd][x] + 1;
		}

		dp[odd][x] = g[y][x] == '^' || g[y][x] == 'X'
		    ? dp[!odd][x-1] + dp[!odd][x+1] + 1
		    : dp[!odd][x];
	}

	return 0;
}

int
main()
{
	int x,y, sx,sy;

	for (h=0; ; ) {
		/* one bottom row of padding */
		assert(h < GH-1);
		/* input already side padded, plus we have \n\0 */
		if (!fgets(g[h], GW, stdin))
			break;
		/* skip empty rows */
		for (x=0; g[h][x]; x++)
			if (g[h][x] == 'S' || g[h][x] == '^')
				{ h++; break; }
	}

	w = strlen(g[0])-1; /* strip \n */

	for (y=0; y<h; y++)
	for (x=0; x<w; x++)
		if (g[y][x] == 'S')
			{ sx=x; sy=y; break; }

	printf("07: %"PRIu64" %"PRIu64"\n", solve_p1(sx,sy), solve_p2());
}

C

Well so much for reading a grid of ints in part 1! For part 2, initially I reworked the parsing to read into a big buffer, but then thought it would be fun to try and use memory-mapped I/O as not to use any more memory than strictly necessary for the final version:

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <assert.h>
#include <sys/mman.h>
#include <unistd.h>
#include <err.h>

#define GH	5

int
main()
{
	char *data, *g[GH], *p;
	uint64_t p1=0,p2=0, acc;
	int len, h=0, i, x,y, val;
	char op;

	if ((len = (int)lseek(0, 0, SEEK_END)) == -1)
		err(1, "<stdin>");
	if (!(data = mmap(NULL, len, PROT_READ, MAP_SHARED, 0, 0)))
		err(1, "<stdin>");
	for (i=0; i<len; i++)
		if (!i || data[i-1]=='\n') {
			assert(h < GH);
			g[h++] = data+i;
		}

	for (x=0; g[h-1]+x < data+len; x++) {
		if ((op = g[h-1][x]) != '+' && op != '*')
			continue;

		for (acc = op=='*', y=0; y<h-1; y++) {
			val = atoi(&g[y][x]);
			acc = op=='+' ? acc+val : acc*val;
		}

		p1 += acc;

		for (acc = op=='*', i=0; ; i++) {
			for (val=0, y=0; y<h-1; y++) {
				p = &g[y][x+i];
				if (p < g[y+1] && isdigit(*p))
					val = val*10 + *p-'0';
			}
			if (!val)
				break;
			acc = op=='+' ? acc+val : acc*val;
		}

		p2 += acc;
	}

	printf("06: %"PRIu64" %"PRIu64"\n", p1, p2);
}

C

Repo

Sweet one. Glad the merge could be done with one n²/2 scan and no sorting or moving, which will make the assembly port a bit easier. Speaking of which, I’m still at day 3 there, fighting not the puzzles but the 64K .COM file limit!

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#define MR	256

#define MIN(a,b)	((a)<(b)?(a):(b))
#define MAX(a,b)	((a)>(b)?(a):(b))

struct range { uint64_t lo, hi; };

static struct range rs[MR];
static int nrs;

int
main()
{
	uint64_t p1=0,p2=0, val;
	int i,j;
	char buf[64];

        for (; fgets(buf, sizeof(buf), stdin); nrs++) {
                assert(nrs < MR);
                if (sscanf(buf, "%lu-%lu", &rs[nrs].lo, &rs[nrs].hi) != 2)
                        break;
        }

	for (i=0; i<nrs-1; i++)
	for (j=i+1; j<nrs; j++)
		if (rs[i].lo <= rs[j].hi && rs[i].hi >= rs[j].lo) {
			rs[j].lo = MIN(rs[i].lo, rs[j].lo);
			rs[j].hi = MAX(rs[i].hi, rs[j].hi);
			rs[i].lo = rs[i].hi = 0;
		}

	while (scanf("%lu", &val) == 1)
		for (i=0; i<nrs; i++)
			if (val >= rs[i].lo && val <= rs[i].hi)
				{ p1++; break; }
	
	for (i=0; i<nrs; i++)
		if (rs[i].lo)
			p2 += rs[i].hi - rs[i].lo + 1;
	
	printf("05: %lu %lu\n", p1, p2);
}

C

For loops!

#include <stdio.h>

#define GZ 144

static char g[GZ][GZ];

int
main()
{
	int p1=0,p2=0, nc=0, x,y;

	for (y=1; fgets(g[y]+1, GZ-2, stdin); y++)
		;

	for (y=1; y<GZ-1; y++)
	for (x=1; x<GZ-1; x++)
		p1 += g[y][x] == '@' &&
		      (g[y-1][x-1] == '@') +
		      (g[y-1][x  ] == '@') +
		      (g[y-1][x+1] == '@') +
		      (g[y  ][x-1] == '@') +
		      (g[y  ][x+1] == '@') +
		      (g[y+1][x-1] == '@') +
		      (g[y+1][x  ] == '@') +
		      (g[y+1][x+1] == '@') < 4;

	do {
		nc = 0;

		for (y=1; y<GZ-1; y++)
		for (x=1; x<GZ-1; x++)
			if (g[y][x] == '@' &&
			    (g[y-1][x-1] == '@') +
			    (g[y-1][x  ] == '@') +
			    (g[y-1][x+1] == '@') +
			    (g[y  ][x-1] == '@') +
			    (g[y  ][x+1] == '@') +
			    (g[y+1][x-1] == '@') +
			    (g[y+1][x  ] == '@') +
			    (g[y+1][x+1] == '@') < 4) {
				nc++;
				p2++;
				g[y][x] = '.';
			}
	} while (nc);

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

Repo

For my x86-16 version, the 20K input is pushing it over the 64K .COM limit, so I’ll need to implement some better compression first.

DOS + BIOS boot (hybrid binary)

Repo | day02.asm | .COM download

Got the x86-16 assembly implementation working at last! Here, 64-bit integer math, especially lots of divisions by power of 10, wasn’t going to do so the code instead operates on fixed-width, zero-padded numeric strings. Lots of time lost to debugging control flow/logic mistakes this time. I need to make printf() a priority!

Short input so no space issues, sitting comfortably at 45K, well below the 64K COM limit! Sadly no time yet to add animations or anything cool.

C

Surprise, O(n^12) solutions don’t scale! But then it was delightful when the realization hit that the solution is actually very simple to implement - just keep removing the first digit that is followed by a higher one.

static uint64_t joltage(char *s, int len, int target) {
	int i;

	for (; len > target; len--) {
		for (i=0; i<len-1 && s[i] >= s[i+1]; i++) ;
		memmove(s+i, s+i+1, len-i);
	}

	return strtoul(s, NULL, 10);
}

int main() {
	char buf[1024];
	uint64_t p1=0,p2=0;
	int len;

	while (fgets(buf, sizeof(buf), stdin)) {
		for (len=0; isdigit(buf[len]); len++) ;
		buf[len] = '\0';
		p2 += joltage(buf, len, 12);
		p1 += joltage(buf, 12, 2);
	}

	printf("03: %lu %lu\n", p1, p2);
}

Repo link

I’m still having to finish yesterday’s x86-16 assembly implementation, for which I had to write some support code to deal with large numbers as strings. That will come in useful today, too!

I deny all the cookie banners

Awesome! I was looking for this type of solution and made some progress but couldn’t get to it

C

There are interesting analytical observations to be made about the problem to sidestep most of the actual iteration, but I wasn’t up to working it all out and the runtime was pretty much instant anyway.

Here’s my original solution with ints, using divions with powers of 10 to do the splitting: day02-u64.c

But I’m only doing the C implementations to prototype my assembly solutions, and dealing with 64-bit numbers, especially divisions, on x86-16 is painful, so I rewrote the solution using a fixed-length string “numbers” instead: day02.c

Still working on the assembly version

Assembly update: have part 1 working now! It’s dog slow on DOSBox, but on QEMU it’s good: day02.asm

DOS + BIOS boot (hybrid binary)

Repo | day01.asm | day01.c (prototype) | .COM download

Written in x86-16 assembly. Works as a DOS program but also as disk image for older PCs with BIOS support (or older VMs). Getting this setup to work was tricky, especially since when I started this, I had only basic x86-16 experience! Needless to say I’ve spent much time staring at hex numbers.

The very start of the file determines if it’s running in DOS or as a bootloader, in which case it’ll have to load the remainder of the file from disk and rearrange the memory layout to emulate the DOS situation.

Right now this is using just one segment of memory (64K). Input data is compressed using a custom run-length encoding scheme. The compressed background image is directly decoded into the VGA framebuffer, after which it is overwritten with the decompressed input file. Space is tight!

My main goal is to finish a few days at least with one or more game consoles supported (GameBoy Advance would be cool) and to do some cool palette tricks, like a day/night transition or animated water and stars.

I did end up creating a backup account on programming.dev but I’m glad SDF is back! Any word on what happened?

I’ve been working on a multi-ROM, a hybrid multi-system cartridge/disk image. Mostly got DOS+MBR working except something is still going wrong in my BIOS disk reading code. The read succeeds, but the system hangs when the function returns. Really want to get that sorted because I want to get GameBoy code in there!

Capital “I”? Heathen!