Hung-Yi's LogoHung-Yi’s Journal

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 and tail are at the same position, the function returns the tail. 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 the tail (if the x coordinate of the head is greater than the x coordinate of the tail), the function returns the tail 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 the tail (if the x coordinate of the head is less than the x coordinate of the tail), the function returns the tail 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 and tail are touching, that is, if the x and y coordinates of the head are within one unit of the x and y coordinates of the tail. If this is the case, the function returns the tail as it is. This means that the tail does not move if the head is already touching it.
  • If the head and tail are not touching, the function uses follow1D() (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 the x dimension and one step closer to the head in the y 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 a tailPositions 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 calling follow2D() 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 the tailPositions 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 the tailPositions 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:

1

But the Y dimension works too, since follow1D() is dimension agnostic.

2

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.