Advent of Code 2022: Day 14
A TypeScript solution for the Advent of Code 2022, Day 14 puzzle: constructing walls and simulating falling sand physics.
Today’s puzzle asks us to simulate grains of sand and some simple physics rules that govern how they settle into piles, given a landscape filled with generated walls and platforms.
The example input looks like this.
498,4 -> 498,6 -> 496,6 503,4 -> 502,4 -> 502,9 -> 494,9
The comma-separated numbers represent coordinates, and the arrows represent connections to other coordinates. Together, they form lines that represent the walls and platforms that interrupt and block the flow of sand.
We start by defining some types that represent the data that we’re working with.
type Cell = "#" | "o"; type Coord = [number, number]; type Wall = Coord[]; type Cave = Map<string, Cell>;
- A
Cell
represents the value at a position, either#
(a wall block) oro
(a grain of sand) Coord
is a tuple of two numbers that represent a position[x, y]
- A
Wall
is defined by multipleCoord
points that are connected together - And the
Cave
represent the whole 2D space by mapping stringified coordinate keys toCell
values at each position
Now we can parse the puzzle input into an array of walls.
const WALLS: Wall[] = puzzleInput .split("\n") .map( (line) => line .split(" -> ") .map((coord) => coord.split(",")) .map(([x, y]) => [Number(x), Number(y)]), );
And to make our simulation easier later, we can calculate the max depth (highest y
value) that the walls go to. This also happens to be our world boundary for part 1.
const WALL_MAX_DEPTH = Math.max( ...WALLS.flatMap((w) => w).map(([, y]) => y), );
Recall that a Wall
is defined by a series of sparse coordinates that are connected by lines, so we still need to interpolate all the individual points that lie in between those wall coordinates. To do this, we implement a function called expand()
that takes a Wall
and outputs an array of coordinates that represent every point in that wall.
// Expands a wall definition into a full list of coordinates const expand = (wall: Wall) => { return wall.slice(1).reduce( (coords, [x2, y2], ii) => { const [x1, y1] = wall[ii]; return coords.concat( x1 === x2 ? Array(Math.abs(y1 - y2) + 1) .fill(Math.min(y1, y2)) .map((y, i) => [x1, y + i]) : Array(Math.abs(x1 - x2) + 1) .fill(Math.min(x1, x2)) .map((x, i) => [x + i, y1]), ); }, [] as Coord[], ); };
Now we should consider the Cave
structure and how it can be used to solve the puzzle.
To store the Cell
values in the Cave
positions, we somehow need to convert coordinates [x,y]
into a string
type that can be uniquely keyed in a Map<string,Cell>
. This is simply achieved by concatenating the x
and y
coordinates with a comma separator.
// Encodes an [x,y] coordinate to a string for use in hash map const encodeCoord = (x: number, y: number) => `${},${}`;
Next, we need some functions to manipulate the cell values at any given cave position.
// Get the cell contents of a cave at [x,y] const check = (cave: Cave, x: number, y: number, floor?: number) => y === floor ? "#" : cave.get(encodeCoord(x, y)); // Settle a grain of sand at [x,y] const settle = (cave: Cave, x: number, y: number) => cave.set(encodeCoord(x, y), "o");
And finally, we can write our simulate()
function.
// Simulate falling sand with or without a floor function simulate(hasFloor: boolean) { const floor = hasFloor ? WALL_MAX_DEPTH + 2 : undefined; const abyss = floor ?? WALL_MAX_DEPTH; const cave: Cave = new Map<string, Cell>( WALLS .flatMap(expand) .map(([x, y]) => [encodeCoord(x, y), "#"]), ); let sand = 0; while (true) { let [x, y] = [500, 0]; while (y < abyss) { if (!check(cave, x, y + 1, floor)) { y++; // fall down } else if (!check(cave, x - 1, y + 1, floor)) { y++; x--; // fall left } else if (!check(cave, x + 1, y + 1, floor)) { y++; x++; // fall right } else { settle(cave, x, y); break; } } // stop counting if sand starts leaking if (y >= abyss) break; sand++; // stop if last grain of sand blocks source if (x === 500 && y === 0) break; } return sand; }
The function does the following:
- Depending on whether we have a floor or not, define the depth of the
floor
and the out-of-bounds depth, which we callabyss
. - Construct the cave by populating it with wall blocks for all the
WALLS
, which we parsed out earlier. - With two
while
loops, generate grains of sand and make them fall, respectively. Theif/else if/else if/else
block controls which direction the grain falls in, and whether it is forced to settle in a position in theCave
. - If the sand falls past the
abyss
depth, stop counting grains of sand, break out of the loop, and return the answer. - If the current grain of sand has settled at the source
[500,0]
then theCave
is full, so stop the simulation and return the answer.
For part 1, the simulation has no floor, and for part 2, the simulation has a floor which is 2 units deeper than the maximum depth of the walls.
const part1 = simulate(false); const part2 = simulate(true);
Final Solution
type Cell = "#" | "o"; type Coord = [number, number]; type Wall = Coord[]; type Cave = Map<string, Cell>; const WALLS: Wall[] = puzzleInput .split("\n") .map( (line) => line .split(" -> ") .map((coord) => coord.split(",")) .map(([x, y]) => [Number(x), Number(y)]), ); const WALL_MAX_DEPTH = Math.max( ...WALLS.flatMap((w) => w).map(([, y]) => y), ); // Expands a wall definition into a full list of coordinates const expand = (wall: Wall) => { return wall.slice(1).reduce( (coords, [x2, y2], ii) => { const [x1, y1] = wall[ii]; return coords.concat( x1 === x2 ? Array(Math.abs(y1 - y2) + 1) .fill(Math.min(y1, y2)) .map((y, i) => [x1, y + i]) : Array(Math.abs(x1 - x2) + 1) .fill(Math.min(x1, x2)) .map((x, i) => [x + i, y1]), ); }, [] as Coord[], ); }; // Encodes an [x,y] coordinate to a string for use in hash map const encodeCoord = (x: number, y: number) => `${},${}`; // Get the cell contents of a cave at [x,y] const check = (cave: Cave, x: number, y: number, floor?: number) => y === floor ? "#" : cave.get(encodeCoord(x, y)); // Settle a grain of sand at [x,y] const settle = (cave: Cave, x: number, y: number) => cave.set(encodeCoord(x, y), "o"); // Simulate falling sand with or without a floor function simulate(hasFloor: boolean) { const floor = hasFloor ? WALL_MAX_DEPTH + 2 : undefined; const abyss = floor ?? WALL_MAX_DEPTH; const cave: Cave = new Map<string, Cell>( WALLS .flatMap(expand) .map(([x, y]) => [encodeCoord(x, y), "#"]), ); let sand = 0; while (true) { let [x, y] = [500, 0]; while (y < abyss) { if (!check(cave, x, y + 1, floor)) { y++; // fall down } else if (!check(cave, x - 1, y + 1, floor)) { y++; x--; // fall left } else if (!check(cave, x + 1, y + 1, floor)) { y++; x++; // fall right } else { settle(cave, x, y); break; } } // stop counting if sand starts leaking if (y >= abyss) break; sand++; // stop if last grain of sand blocks source if (x === 500 && y === 0) break; } return sand; } const part1 = simulate(false); const part2 = simulate(true); console.log("Part 1:", part1); console.log("Part 2:", part2);
Part 1: 644 Part 2: 27324