2022 Advent Of Code(day9) – Rope Bridge

最近看到題目會先觀察會不會很麻煩再決定要不要開始寫，這種壞習慣應該要改一改QQ。

Part1

看完題目的描述後，比較要動腦的地方在於怎麼決定尾巴的移動跟是否相鄰的判斷。我這邊是直接寫了簡單的 2-d 向量來做。

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)
    );
  }

註：寫完之後發現其實可以直接求兩點距離，就不需要一個一個比了。

輸入處理

輸入相對簡單，基本上就是把各個方向的移動映射成向量：

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

尾巴的移動邏輯

當繩子的頭移動時，如果尾巴不相鄰的話也會移動。這可以用內積求夾角來算尾巴應該如何移動。用 x 單位向量跟 y 單位向量求夾角就可以知道尾巴應該要怎麼移動。

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);
  }
}

題目是問尾巴有走過哪些點，可以直接用 Set 來完成。完整的程式碼實作如下：

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);
      }
    }
  }
}

想說題目會不會藏個彩蛋，其實尾巴拉出來的形狀會是什麼圖片，所以把繩子的座標也畫了出來。

繩子的移動軌跡

但似乎沒有什麼特別的地方。

Part2

原本只要考慮頭跟尾，但現在繩子的長度有 10，所以移動方式也會不太一樣。不過整體的邏輯還是大致相同的，把原本的 Rope 頭跟尾連在一起後就可以達成。

 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}`
    );
  }
});

Kalan's Blog