Advent of Code 2023: Day Eight

Time for Day Eight! As always, the code is available on Git, and the other posts are under the #AdventOfCode2023 tag

Part One

So, now we have a map that can take us across the desert. The first line is a series of instructions, that are either “R” (for right), or “L” for left. Below that is a list of location names, to the locations the left and right nodes take you to, like this:

RL

AAA = (BBB, CCC)
BBB = (DDD, EEE)
CCC = (ZZZ, GGG)
DDD = (DDD, DDD)
EEE = (EEE, EEE)
GGG = (GGG, GGG)
ZZZ = (ZZZ, ZZZ)

The task is to find out, by following the instructions, how many steps it takes to get from AAA to ZZZ.

At first, I went down the path of creating a tree data structure, because that’s what this sort-of looks like, and then using that. It worked fine for the tests but then fell over, because the actual input had node names that hadn’t already been assigned to a parent, so I couldn’t construct it.

Then I realised I was overcomplicating things, and I could just use Record<string, [string, string]> and brute-force things:

const patternParser = anyCharOf("LR").pipe(manyTill(newline().pipe(exactly(2))));

const nodeNameParser = uniLetter().pipe(or(uniDecimal()), exactly(3), stringify());
const childParser = nodeNameParser.pipe(manySepBy(", "), exactly(2), between("(", ")"));
const nodeParser = nodeNameParser.pipe(then(childParser.pipe(between(" = ", whitespace()))))

const parser = patternParser.pipe(then(nodeParser.pipe(manySepBy(whitespace()))));

type Maybe<T> = T | undefined;

type Instruction = "L" | "R";
type NodeName = string;
type NodeChildren = [Maybe<NodeName>, Maybe<NodeName>];

export class DesertMap {
	private readonly pattern: Instruction[];

	private map: Record<NodeName, NodeChildren> = {};

	constructor(input: string) {
		const [pattern, nodes] = parser.parse(input).value;

		this.pattern = pattern as Instruction[];

		for (const [name, [[leftNode, rightNode]]] of nodes) {
			if (!this.map[name]) {
				this.map[name] = [undefined, undefined];
			}
			const children = [leftNode, rightNode];
			this.map[name] = children as NodeChildren;
		}
	}
	
	public stepsToZ(from: string): number {
		let step = 0;
		let curr = from;

		while (!curr.endsWith('Z')) {
			const instruction = this.pattern[step % this.pattern.length];

			const [left, right] = this.map[curr];

			if (instruction === "L" && left) {
				curr = left;
			} else if (instruction === "R" && right) {
				curr = right;
			}

			if (!curr) return 0;

			step++;
		}
		return step;
	}
}

And that worked nicely - and didn’t even run slowly. On to Part 2!

Part Two

Now things get interesting. Actually, this map is for ghosts 👻! And naturally, ghosts have the power to follow multiple roads at once to find a destination (I must have missed that bit in school)! So any node that ends in the letter A is a starting node, and any that ends in the letter Z is an end-node.

My first pass just tried to brute-force it, like I did with part one:

public isComplete(keys: string[]): boolean {
	return keys.every(k => k.endsWith('Z'));
}

public findCommonSteps(): number {
	 let step = 0;
	let keys = Object.keys(this.map).filter(k => k.endsWith('A'));
	
	while (!this.isComplete(keys)) {
		const instruction = this.pattern[step % this.pattern.length];
		
		keys = keys.map(key => {
			const [left, right] = this.map[key];

			if (instruction === "L" && left) {
				return left;
			} else if (instruction === "R" && right) {
				return right;
			}

			return key;
		})
		step++;
	}
}

This… didn’t work. The tests passed, so I’ve no doubt it would have been eventually correct, but I’d have died of old age before it ended, most likely.

I puzzled for a while on how to do this, but to be honest I was stumped. Luckily, one of my colleagues helpfully pointed me in the direction of using the Lowest Common Multiple of the number of steps, and that worked:

const gcd = (a: number, b: number): number => {
	if (b === 0) return a;
	return gcd(b, a % b);
}

const lcm = (a: number, b: number): number => {
	const product = a * b;
	return product / gcd(a, b);
}

public ghostStepsToZ(): number {
	let keys = Object.keys(this.map).filter(key => key.endsWith('A'));

	return keys.map(key => this.stepsToZ(key)).reduce(lcm);
}

And that’s Day Eight done!