Advent of Code 2023: Day Eleven

More from Advent of Code. Checkout the other posts, or the Git repository.

I didn’t finish Day Ten; I’ll add it to my backlog and maybe go and do the ones I’ve missed when this is all over.

## Part One

We’ve got a map of the cosmos! Galaxies are # characters, and we need to work out the distances between every pair of galaxies. There’s a catch though - completely empty rows or columns are doubled, thanks to universal expansion. Here’s our input:

...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#....

For Part One, I parsed the input, and then transformed the matrix to include the expaned rows and columns:

class Observatory {
	private grid: string[][] = [];
	private expandedGrid: string[][] = [];

	constructor(input: string) {
		this.grid = input.split('\n').map(line => line.split(''));

		this.expandGrid();
	}

	private expandGrid() {
		const columns = Range(0, this.grid[0].length).filter(column => this.grid.every(row => row[column] === '.'));
		const rows = Range(0, this.grid.length).filter(row => this.grid[row].every(column => column === '.'));
		
		columns.forEach((column, index) => {
			this.expandedGrid.map(row => row.splice(column + index, 0, new Array(this.expandedGrid[0].length).fill('.')));
		});
		
		rows.forEach((row, index) => {
			this.expandedGrid.splice(row + index, 0, new Array(this.expandedGrid.length).fill('.'));
		});
	}
}

I’m offsetting the rows and columns by their position in the range to account for the fact that inserting previous columns will alter the indexes.

Then I just get every pair of galaxy, and calculate the distance between them using the Manhattan Distance:

public get shortestPaths(): number {
	const distances = this.pairs.map(pair => this.distanceBetween(pair[0], pair[1]));
	return distances.reduce((sum, distance) => sum + distance, 0);
}

private get pairs(): GalaxyPair[] {
	const galaxies = this.expandedGrid.reduce((galaxies, row, rowIndex) => {
		row.forEach((galaxy, columnIndex) => {
			if (galaxy === '#') {
				galaxies.push([rowIndex, columnIndex]);
			}
		});
		return galaxies;
	}, [] as Position[]);

	return galaxies.reduce((pairs, galaxy, index) => {
		return pairs.withMutations(pairs => {
			galaxies.slice(index + 1).forEach(otherGalaxy => {
				pairs.add([galaxy, otherGalaxy]);
			});
		})
	}, Set<GalaxyPair>()).toArray();
}

public distanceBetween(galaxyOne: Position, galaxyTwo: Position): number {
	return Math.abs(galaxyOne[0] - galaxyTwo[0]) + Math.abs(galaxyOne[1] - galaxyTwo[1]);
}

And that worked! On to Part Two!

Part Two

Oh no, it turns out that the spaces didn’t expand by a single row/column, but in fact by one million!

Obviously, trying to still mutate the array was never going to work, so instead I just store a list of the columns and rows that should be expanded. Then, when comparing the distances, I get all of the expanded columns and rows that sit between the two galaxies, and multiply the total by the amount of expansion. I then add that number to the Manhattan Distance from Part One:

class Observatory {
	private grid: string[][] = [];
	private expandedRows: number[] = [];
	private expandedColumns: number[] = [];
	
	private expandGrid() {
		this.expandedColumns = Range(0, this.grid[0].length).filter(column => this.grid.every(row => row[column] === '.')).toArray();
		this.expandedRows = Range(0, this.grid.length).filter(row => this.grid[row].every(column => column === '.')).toArray();
	}
	
	private range = (a: number, b: number): Seq.Indexed<number> => {
		return Range(Math.min(a, b), Math.max(a, b) + 1);
	}
	
	public distanceBetween(galaxyOne: Position, galaxyTwo: Position): number {
		const expansion = 1_000_000;

		const xRange = this.range(galaxyOne[0], galaxyTwo[0]).filter(row => this.expandedRows.includes(row)).toArray().length;
		const yRange = this.range(galaxyOne[1], galaxyTwo[1]).filter(column => this.expandedColumns.includes(column)).toArray().length;

		const expansions = expansion * (xRange + yRange)

		return Math.abs(galaxyOne[0] - galaxyTwo[0]) + Math.abs(galaxyOne[1] - galaxyTwo[1]) + expansions;
	}
}

I first tested this against the original input and expansion to make sure it worked, and it did! So then I ran it using the expansion value of 1 million aaand… nope. Too high.

After a bit of head-scratching and investigation, I realised I had an off-by-one error. I need to substitute 1 row/column for a million, not add 1 million to it. So, if I reduce my expansion to 999999, everything works!

public distanceBetween(galaxyOne: Position, galaxyTwo: Position): number {
	const expansion = 999_999;

	const xRange = this.range(galaxyOne[0], galaxyTwo[0]).filter(row => this.expandedRows.includes(row)).toArray().length;
	const yRange = this.range(galaxyOne[1], galaxyTwo[1]).filter(column => this.expandedColumns.includes(column)).toArray().length;

	const expansions = expansion * (xRange + yRange)

	return Math.abs(galaxyOne[0] - galaxyTwo[0]) + Math.abs(galaxyOne[1] - galaxyTwo[1]) + expansions;
}

That’s Day Eleven done with!