「ハノイの塔」(ランク A) を円盤を動かさずに解く

# はじめに
[paiza x Qiita のプログラミング問題](https://paiza.jp/pages/campaign/paiza-qiita "paiza x Qiita コラボキャンペーン") の [ハノイの塔](https://paiza.jp/works/mondai/real_event/hanoi "ハノイの塔 (paizaランク A 相当)") をトライしました.

[ハノイの塔](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94 "ハノイの塔 - Wikipedia")は再帰の例として有名です. 私も最初はオーソドックスにハノイの塔の操作をするコードを書き, 指定された回数で操作をやめ, そのときの状態を出力するものを作成しました.

その後, いろいろと考えていくうちに, 円盤を動かす操作をしなくても, 指定された回数から円盤の状態を直接求められることに気付き, それをコードにしてみました.

以下に, 概略を説明します.

# 作戦
## n 番目の円盤の場所を決める
まず塔 A, B, C があり, n 個の円盤が A にあるとします. そして, すべての円盤を C に動かすことを考えます. n 個の円盤を移動させるのに必要な操作回数を $a_n$[^1] とします. 円盤の動かし方は次のようになります.

[^1]:$a_n = 2^n-1$ となります. $a_1 = 1$, $a_{n+1} = 2 a_n + 1$ の数列から計算できます.

1. n-1 個の円盤を A -> B に動かす ($a_{n-1}$ 回の操作)
1. n 番目の円盤を A -> C に動かす (1 回の操作)
1. n-1 個の円盤を B -> C に動かす ($a_{n-1}$ 回の操作)

そのため, 移動回数 $t$ に対して n 番目の円盤の場所は以下のように決めることができます.

- $t \le a_{n-1}$ ; n 番目の円盤は A にある (まだ動いていない)
- $t \gt a_{n-1}$ ; n 番目の円盤は C にある (もう動いた)

## n-1 番目の円盤の場所を決める
次に, n-1 番目の円盤の場所を考えます. $t$ の値によって, 場合分けをします.

### t < a_(n-1) の場合
まず $t \lt a_{n-1}$ の場合です. この場合, n 番目の円盤はまだ A にあり, C に動かそうとしています. そのため n-1 番目の円盤は, B へ動かすことになります. 手順としては次のようになります.

1. n-2 個の円盤を A -> C に動かす ($a_{n-2}$ 回の操作)
1. n-1 番目の円盤を A -> B に動かす (1 回の操作)
1. n-2 個の円盤を C -> B に動かす ($a_{n-2}$ 回の操作)

そのため, n 番目の円盤の時と同様に考えると, 以下のようにして n-1 番目の円盤の場所を決めることができます.

- $t \le a_{n-2}$ ; n-1 番目の円盤は A にある (まだ動いていない)
- $t \gt a_{n-2}$ ; n-1 番目の円盤は B にある (もう動いた)

### t >= a_(n-1) の場合
続いて $t \ge a_{n-1}$ の場合です. このときは n 番目の円盤はすでに C にあり, 1 から n-1 番目の円盤は B から C に移動している途中になります. そのため

- $t - \(a_{n-1} + 1 \) \lt a_{n-2}$ ; n-1 番目の円盤は B にある (まだ動いていない)
- $t - \(a_{n-1} + 1\) \ge a_{n-2}$ ; n-1 番目の円盤は C にある (もう動いた)

# コード
ポイントのみ説明します. 全体のコードは, 末尾の Google Colaboratory へのリンクから確認してください.

## 操作回数の関数定義
操作回数の関数を定義します.

```python:1
# n 個の円盤からなるハノイの塔の操作回数を計算する
def hanoi_trial(n):
  return 2**n - 1
```

続いて, 変数を定義します. 塔の番号は a, b, c の変数に入れますが, 常に

- a ; 円盤の移動元
- b ; バッファの塔
- c : 円盤の移動先

となるようにします.

```python:2
# 変数設定
tower = [[], [], []] # 各塔にある円盤を格納する変数
a = 0 # 塔の番号を表す. 0 -> 最初, 1 -> バッファ, 2 -> 最後
b = 1
c = 2
```

標準入力からデータを読み込みます.
- n ; 円盤の数
- t ; 操作回数

```python:3
# 標準入力からデータを読む
s = input().rstrip().split()
n = int(s[0])
t = int(s[1])
```

続いてメインのコードです. n 番目の円盤から順に, どの塔にいるかを求めていきます.
```python:4
# n 番目の円盤から順に，どの塔にあるかを求めていく
for i in range(n, 0, -1):
  if t <= hanoi_trial(i-1):
    tower[a].append(i)
    b, c = c, b
  else:
    tower[c].append(i)
    t -= (hanoi_trial(i-1)+1)
    a, b = b, a
```

ちょっと説明します. まず, 操作回数 $t$ が前半 ($t \le a_{i-1}$) の場合です (以下の部分). このときは $i$ 番目の円盤は動いていないので, 移動元 (a) のリストに番号を追加 (```tower[a].append(i)```) します. そして次の操作の準備として, 塔の番号を入れ替えます. $i-1$ 番目の円盤はバッファの塔に行ってもらうので, b と c を入れ替えます (```b, c = c, b```). 
```python:4-1
  if t <= hanoi_trial(i-1):
    tower[a].append(i)
    b, c = c, b
```

次に, 操作回数 $t$ が後半 ($t \gt a_{i-1}$) の場合です (以下の部分). このとき, $i$ 番目の円盤は既に動いているので, 移動先 (c) のリストに番号を追加 (```tower[c].append(i)```) します. その後, 次のループの判定を容易にするため, 前半部分の回数を引き算 (```t -= (hanoi_trial(i-1) + 1)```) しておきます. 最後に塔の番号を入れ替えますが, $i-1$ 番目の円盤はバッファ b に行ってもらい, その代わりに a がバッファになるので, a と b を入れ替えます (```a, b = b, a```).

```python:4-2
  else:
    tower[c].append(i)
    t -= (hanoi_trial(i-1)+1)
    a, b = b, a
```
# さいごに
コードを書いてみると, 案外とシンプルなものができました. そのためコードを見ただけでは, 何をしているのかが分かりづらいかもしれません. 考え方そのものは単純なので, ご理解いただけると嬉しいです.

# リンク
- [ハノイの塔_試行レス版.ipynb](https://colab.research.google.com/drive/18qQAQ_wHZkhwkxFq2UXyq9BmL4hEh-9w?usp=sharing, "ハノイの塔_試行レス版.ipynb")
- (参考) [ハノイの塔_提出版.ipynb](https://colab.research.google.com/drive/1yGM_RS5Ni0Lm7NIx0RdtduylWwCM8dhc?usp=sharing, "ハノイの塔_提出版.ipynb") (ハノイの塔の操作をやりながら円盤の配置を求めるコード)