ushumpei’s blog

生活で気になったことを随時調べて書いていきます。

ハノイの塔

なんだか久しぶりにjavascriptハノイの塔を解いて見ました。以下の関数は、number枚のハノイの塔をtime回操作した時の状態を計算するものです。特に目新しいものではないと思います。

const hanoiSnapshot = (number, time) => {
  // 円盤の移動が完了した以降の操作はエラーを表示(良いやり方かどうかは悩む)
  if (time > Math.pow(2, number) - 1) throw new Error(`${Math.pow(2, number) - 1}回目の操作時点ですでに塔は完成しています`);

  // 三本柱の配列データを定義
  hanoi = [[], [], []];

  // 1~number番目の円盤それぞれの場所を計算して柱に格納して行く
  for (let i = 1; i <= number; i++) {

    // 移動する方向
    const direction = Math.pow(-1, number + i + 1);

    // 移動した回数
    const moveCount = Math.floor((Math.pow(2, i - 1) + time) / Math.pow(2, i));

    // 1番目の柱を位置0とした時の円盤の絶対位置
    const absolutePosition = moveCount % 3;

    // 方向を加味して場所を0~2に正規化して決定
    const position = (direction * absolutePosition < 0) ? (3 + direction * absolutePosition) % 3 : absolutePosition;

    // 柱に円盤を追加する
    hanoi[position].unshift(i);
  }

  return hanoi;
}

感想

イメージとしては円盤は方向と速度を持っていて、3つの柱を移動しつつ、くるくる回って行る感じです。数学で三乗根の乗算を考えるときに書くような図をイメージするとわかりやすい気がします。