Advent of Code 2022 (Day 9) – Rope Bridge

Day 9

Lately, when I see a problem, I tend to check whether it looks tedious before deciding whether to start writing code. I really should break this bad habit :‘(

Part 1

After reading the problem description, the main part that requires some thought is determining how the tail moves and checking whether it is adjacent to the head. I tackled this directly using simple 2D vectors.

function isNeighbor(a, b) {
    return (
      (a.x === b.x ||
        a.x - 1 === b.x ||
        a.x + 1 === b.x) &&
      (a.y === b.y || a.y - 1 === b.y || a.y + 1 === b.y)
    );
  }

Note: After writing this, I realized you could simply calculate the distance between the two points instead of comparing each coordinate one by one.

Input Parsing

Parsing the input is relatively straightforward—essentially mapping each movement direction to a vector:

U: (0, 1)
D: (0, -1)
R: (1, 0)
L: (-1, 0)

Tail Movement Logic

When the rope’s head moves, the tail moves as well if they are no longer adjacent. We can calculate the angle using the dot product to determine how the tail should move. By computing the angle against the x and y unit vectors, we can figure out which direction the tail needs to head.

if (!this.head.isNeighbor(this.tail)) {
  const vec = this.head.vector(this.tail);
  const degree = vec.product(new Point(1, 0)) / vec.length();
  const degree2 = vec.product(new Point(0, 1)) / vec.length();
  if (degree === 0) {
    if (degree2 > 0) {
      this.tail.add(0, 1);
    } else {
      this.tail.add(0, -1);
    }
  } else if (Math.abs(degree) === 1) {
    if (degree === 1) {
      this.tail.add(1, 0);
    } else {
      this.tail.add(-1, 0);
    }
  } else {
    this.tail.add(degree > 0 ? 1 : -1, degree2 > 0 ? 1 : -1);
  }
}

The problem asks for the unique positions visited by the tail, which can be easily tracked using a Set. The full code implementation is as follows:

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  isNeighbor(point) {
    const vec = new Point(point.x - this.x, point.y - this.y);

    return vec.length() <= 1;
  }

  add(x, y) {
    this.x += x;
    this.y += y;
  }

  vector(point) {
    return new Point(this.x - point.x, this.y - point.y);
  }

  length() {
    return Math.sqrt(this.x * this.x + this.y * this.y);
  }

  product(point) {
    return point.x * this.x + point.y * this.y;
  }
}
class Rope {
  constructor(isFirst = false) {
    this.isFirst = isFirst;
    this.head = new Point(0, 0);
    this.tail = new Point(0, 0);
  }

  move(direction) {
    if (this.isFirst) {
      switch (direction) {
        case "U":
          this.head.add(0, 1);
          break;
        case "D":
          this.head.add(0, -1);
          break;

        case "L":
          this.head.add(-1, 0);
          break;

        case "R":
          this.head.add(1, 0);
          break;
      }
    }

    if (!this.head.isNeighbor(this.tail)) {
      // calculate vector
      // move to direction
      const vec = this.head.vector(this.tail);
      const degree = vec.product(new Point(1, 0)) / vec.length();
      const degree2 = vec.product(new Point(0, 1)) / vec.length();
      if (degree === 0) {
        // horizontal, vertial
        if (degree2 > 0) {
          this.tail.add(0, 1);
        } else {
          this.tail.add(0, -1);
        }
      } else if (Math.abs(degree) === 1) {
        if (degree === 1) {
          this.tail.add(1, 0);
        } else {
          this.tail.add(-1, 0);
        }
      } else {
        this.tail.add(degree > 0 ? 1 : -1, degree2 > 0 ? 1 : -1);
      }
    }
  }
}

Wondering if the problem hid an Easter egg—like the tail tracing out a specific image—I plotted the coordinates of the rope.

It looks like there was nothing special after all.

Part 2

Previously, we only had to consider the head and the tail, but now the rope has a length of 10, meaning the movement mechanics change slightly. However, the overall logic remains largely the same: we can achieve this by chaining the head and tail segments together from our original Rope structure.

 const ropes = [
  new Rope(true),
  new Rope(),
  new Rope(),
  new Rope(),
  new Rope(),
  new Rope(),
  new Rope(),
  new Rope(),
  new Rope(),
 ];
const set = new Set();

direction.forEach((dir, ii) => {
  const [d, step] = dir.split(" ");
  for (let i = 0; i < Number(step); i++) {
    ropes.forEach((rope, j) => {
      if (j === 0) {
        rope.move(d);
      } else {
        rope.head = ropes[j - 1].tail;
        rope.move(d);
      }
    });
    set.add(
      `${ropes[ropes.length - 1].tail.x} ${ropes[ropes.length - 1].tail.y}`
    );
  }
});