2022 Advent Of Code（day9）– ロープブリッジ

最近、問題を見てから面倒くさいかどうかを見てから書くか決めるようにしていますが、このような悪い習慣は改めるべきですね。

Part1

問題の説明を読んだ後、考えるべき点は、テールの移動方法と隣接の判定です。私はここでは単純な2次元ベクトルを使って実装しました。

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

カランのブログ