2022 Advent Of Code(day9) – Rope Bridge

Day9

最近は問題を見ると、まず面倒くさそうかどうかを観察してから書き始めるかを決めるようになってしまっている。こういう悪い癖は直さないといけないなQQ。

Part1

問題の説明を読んだ後、頭を使う必要があったのは尾の移動方法と隣接判定をどう決めるかという点だった。僕のほうでは単純な2Dベクトルを直接書いて実装した。

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

注：書き終えた後に気づいたが、実際には2点間の距離を直接求めれば、1つずつ比較する必要はなかった。

入力の処理

入力は比較的シンプルで、基本的には各方向の移動をベクトルにマッピングするだけだ：

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