Advent of Code 2022: Day 9
A TypeScript solution for the Advent of Code 2022, Day 9 puzzle: rope physics simulation.
Today’s puzzle asks us to model a rope as a string of knots, where each knot is a coordinate in 2D space, as they follow each other according to some simple movement rules.
The puzzle provides us with example input representing the movement of the head of the rope, which looks like this.
R 4 U 4 L 3 D 1 R 4 D 1 L 5 R 2
We start by parsing the input data into a more usable data structure: a list of movements.
const movements = puzzleInput.split('\n') .map(line => ({ direction: line[0], steps: parseInt(line.slice(2)) }));
Each movement contains a direction
property, which is the first character of the original input string (R, U, L, or D), and a steps
property, which is the number of steps indicated in the original input string converted to an integer using parseInt()
.
Now we define two type aliases: Knot
and Rope
. A Knot
is a tuple (an array with a fixed number of elements) containing two number values, representing the x
and y
coordinates of a single knot in 2D space. A Rope
is an array of Knot
tuples, representing a string of knots in 2D space.
type Knot = readonly [number, number]; type Rope = Knot[];
By defining these type aliases, the code allows for more concise and expressive type annotations, making it easier to understand the data structures used in the program.
Now we implement a function named follow1D()
that takes two number values, head
and tail
, as arguments. The function implements the rules for moving the tail of a rope in one dimension (either the x
or y
dimension) based on the position of the head of the rope.
const follow1D = (head: number, tail: number) => { if (head === tail) return tail; if (head > tail) return tail + 1; else return tail - 1; }
Here is how it works in the X dimension:1
- If the
head
andtail
are at the same position, the function returns thetail
. This means that the tail does not move if the head is at the same position as the tail in the given dimension. - If the
head
is to the right of thetail
(if thex
coordinate of the head is greater than thex
coordinate of the tail), the function returns thetail
plus one. This means that the tail moves one step to the right to follow the head. - If the
head
is to the left of thetail
(if thex
coordinate of the head is less than thex
coordinate of the tail), the function returns thetail
minus one. This means that the tail moves one step to the left to follow the head.
Now we define follow2D()
that takes two Knot
tuples, [headX, headY]
and [tailX, tailY]
, as arguments. The function implements the rules for moving the tail of a rope in two dimensions (the x
and y
dimensions) based on the position of the head of the rope.
const follow2D = ( [headX, headY]: Knot, [tailX, tailY]: Knot ) => { // head and tail still touching; tail doesn't move if (Math.abs(headX - tailX) <= 1 && Math.abs(headY - tailY) <= 1) { return [tailX, tailY] as const; } // otherwise, move the tail closer to the head return [ follow1D(headX, tailX), follow1D(headY, tailY) ] as Knot; }
- The function checks if the
head
andtail
are touching, that is, if thex
andy
coordinates of the head are within one unit of thex
andy
coordinates of the tail. If this is the case, the function returns thetail
as it is. This means that the tail does not move if the head is already touching it. - If the
head
andtail
are not touching, the function usesfollow1D()
(defined previously) to move the tail one step closer to the head in each dimension. This means that the tail moves one step closer to the head in thex
dimension and one step closer to the head in they
dimension.
Finally we implement simulate()
which takes a number value, ropeLength
, as an argument. The function simulates the movement of a rope of the given length according to the movement instructions provided in the movements
array (i.e. the puzzle input).
const simulate = (ropeLength: number) => { let rope = Array(ropeLength).fill([0,0]); const tailPositions = new Set<string>(); for (const { direction, steps } of movements) { Array(steps).fill(0).forEach(() => { let [headX, headY] = rope[0]; switch (direction) { case 'U': headX--; break; case 'D': headX++; break; case 'L': headY--; break; case 'R': headY++; break; } rope = rope.map( (knot, ii) => ii === 0 ? [headX, headY] : follow2D(rope[ii - 1], knot) ); tailPositions.add(rope[rope.length - 1].join(',')); }); } return tailPositions.size; }
Here is how the simulation works:
- The function initializes the rope array with
ropeLength
number of knots, each at position[0, 0]
(the origin). It also initializes atailPositions
set to keep track of the different positions that the tail of the rope reaches during the simulation. - The function loops over the
movements
array, and for each movement, it moves the head of the rope in the specified direction by the specified number of steps. - For each step, the function moves the head of the rope one step in the specified direction based on a
switch
statement. It then updates the positions of all the knots in the rope array by callingfollow2D()
to move each knot one step closer to the previous knot.2 Finally, it adds the new position of the tail of the rope to thetailPositions
set. - After all the movements have been processed, the function returns the number of different positions that the tail of the rope reached, which is the
size
of thetailPositions
set.
Part 1 of the puzzle asks for us to track a rope with 2
knots, a head and a singular tail, of which we track the positions.
const part1 = simulate(2);
Part 2 makes us simulate a longer knot with 1 head plus 9 tails, i.e. a rope of length 10
.
const part2 = simulate(10);
Final Solution
const movements = puzzleInput.split('\n') .map(line => ({ direction: line[0], steps: parseInt(line.slice(2)) })); type Knot = readonly [number, number]; type Rope = Knot[]; const follow1D = (head: number, tail: number) => { if (head === tail) return tail; if (head > tail) return tail + 1; else return tail - 1; } const follow2D = ( [headX, headY]: Knot, [tailX, tailY]: Knot ) => { // head and tail still touching; tail doesn't move if (Math.abs(headX - tailX) <= 1 && Math.abs(headY - tailY) <= 1) { return [tailX, tailY] as const; } // otherwise, move the tail closer to the head return [ follow1D(headX, tailX), follow1D(headY, tailY) ] as Knot; } const simulate = (ropeLength: number) => { let rope = Array(ropeLength).fill([0,0]); const tailPositions = new Set<string>(); for (const { direction, steps } of movements) { Array(steps).fill(0).forEach(() => { let [headX, headY] = rope[0]; switch (direction) { case 'U': headX--; break; case 'D': headX++; break; case 'L': headY--; break; case 'R': headY++; break; } rope = rope.map( (knot, ii) => ii === 0 ? [headX, headY] : follow2D(rope[ii - 1], knot) ); tailPositions.add(rope[rope.length - 1].join(',')); }); } return tailPositions.size; } const part1 = simulate(2); const part2 = simulate(10); console.log("Part 1:", part1); console.log("Part 2:", part2);
Part 1: 6354 Part 2: 2651
Footnotes:
But the Y dimension works too, since follow1D()
is dimension agnostic.
Realising that each knot follows the previous knot, like a game of snake, is what unifies the part 1 and part 2 solutions to one set of rules. Part 1 just happens to be a special case where there is one head and exactly one following tail.