Change your colour scheme

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:



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;

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;

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!


About the author

My face

I'm Lewis Dale, a software engineer and web developer based in the UK. I write about writing software, silly projects, and cycling. A lot of cycling. Too much, maybe.