なんだか久しぶりに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つの柱を移動しつつ、くるくる回って行る感じです。数学で三乗根の乗算を考えるときに書くような図をイメージするとわかりやすい気がします。