paizaラーニングレベルアップ問題集の「ハノイの塔」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[ハノイの塔](https://paiza.jp/works/mondai/real_event/hanoi)をやってみました。
- - -
まずは、実際に手を動かして「やってみました」。

$N=1$
| t | 円盤 | from | to | 杭A | 杭B | 杭C |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 |||| 1 | - | - |
| 1 | 1 | A | C | - | - | 1 |

$N=2$
| t | 円盤 | from | to | 杭A | 杭B | 杭C |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 |||| 2 1 | - | - |
| 1 | 1 | A | B | 2 | 1 | - |
| 2 | 2 | A | C | - | 1 | 2 |
| 3 | 1 | B | C | - | - | 2 1 |

$N=3$
| t | 円盤 | from | to | 杭A | 杭B | 杭C |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 |||| 3 2 1 | - | - |
| 1 | 1 | A | C | 3 2 | - | 1 |
| 2 | 2 | A | B | 3 | 2 | 1 |
| 3 | 1 | C | B | 3 | 2 1 | - |
| 4 | 3 | A | C | - | 2 1 | 3 |
| 5 | 1 | B | A | 1 | 2 | 3 |
| 6 | 2 | B | C | 1 | - | 3 2 |
| 7 | 1 | A | C | - | - | 3 2 1 |

$N=4$
| t | 円盤 | from | to | 杭A | 杭B | 杭C |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 |||| 4 3 2 1 | - | - |
| 1 | 1 | A | B | 4 3 2 | 1 | - |
| 2 | 2 | A | C | 4 3 | 1 | 2 |
| 3 | 1 | B | C | 4 3 | - | 2 1 |
| 4 | 3 | A | B | 4 | 3 | 2 1 |
| 5 | 1 | C | A | 4 1 | 3 | 2 |
| 6 | 2 | C | B | 4 1 | 3 2 | - |
| 7 | 1 | A | B | 4 | 3 2 1 | - |
| 8 | 4 | A | C | - | 3 2 1 | 4 |
| 9 | 1 | B | C | - | 3 2 | 4 1 |
| 10 | 2 | B | A | 2 | 3 | 4 1 |
| 11 | 1 | C | A | 2 1 | 3 | 4 |
| 12 | 3 | B | C | 2 1 | - | 4 3 |
| 13 | 1 | A | B | 2 | 1 | 4 3 |
| 14 | 2 | A | C | - | 1 | 4 3 2 |
| 15 | 1 | B | C | - | - | 4 3 2 1 |

ここで、$N=4$の手順を見ると
- 1～7手目（$1\le t\le 7$）：3個の円盤をAの杭からBの杭に移動
- 8手目：1個の円盤（4番の円盤）をAの杭からCの杭に移動
- 9～15手目（$9\le t\le 15$）：3個の円盤をBの杭からCの杭に移動

一般の$N$に対して
- $1\le t\le 2^{N-1}-1$：$N-1$個の円盤をAの杭からBの杭に移動
- $2^{N-1}$手目：$1$個の円盤（$N$番の円盤）をAの杭からCの杭に移動
- $2^{N-1}+1\le t\le 2^N-1$：$N-1$個の円盤をBの杭からCの杭に移動

となります。大枠部分をプログラムにすると
```
hanoi(n, from, to, tmp){
    if(n=1){
        //杭fromの一番上の円盤を杭toの一番上に動かす
        to.push(from.pop())
        //移動回数をカウント
        
    }else{
        //n-1個の円盤をfromからtmpに動かす
        hanoi(n-1, from, tmp, to)
        //1個の円盤（n番の円盤）をfromからtoに動かす
        hanoi(1, from, to, tmp)
        //n-1個の円盤をtmpからtoに動かす
        hanoi(n-1, tmp, to, from)
    }
}

main(){
    n=入力値を整数に変換
    t=入力値を整数に変換 //一旦無視
    杭A={n,n-1,...,2,1} //下から上
    杭B={}
    杭C={}
    hanoi(n, 杭A, 杭C, 杭B)
}
```
あとは移動回数について考慮しなければなりません。

入力値`t`を引数で渡したり、移動回数をグローバルで宣言する方法もありますが、今回は、クラスを作ってみましょう。引数をずーっと渡し続ける必要がなくなり、グローバル変数への予期せぬアクセス・更新を防げます。
```
class Hanoi{
    N: int
    towers: List[] //リストの配列。配列の要素数は3。
    T: int
    count: int
    
    private print(){
        for(tower:towers){
            if(towの要素数==0){
                "-"を出力
            }else{
                towの要素を半角空白区切りで出力
            }
        }
    }

    private hanoi(n,src,dst,tmp){
        if(count>=T)return
        if(n==1){
            dst.push(src.pop())
            count++
            if(count==T){
                print()
                return
            }
        }else{
            hanoi(n-1,src,tmp,dst)
            hanoi(1,src,dst,tmp)
            hanoi(n-1,tmp,src,dst)
        }
    }

    public hanoi(){
        hanoi(this.N,towers[0],towers[2],towers[1])
    }
    
    public Hanoi(n,t){
        this.N=n
        towers={{n,n-1,...,2,1},{},{}}
        this.T=t
        count=0
    }
}

main(){
    n=入力値を整数に変換
    t=入力値を整数に変換
    hanoi=new Hanoi(n,t)
    hanoi.hanoi()
    return 0
}
```
今回は、Javaで清書してみます。
```java
import java.util.*;

class Hanoi {
    // 円盤の数
	private int n;

    // 各杭の状態（スタックを用いています）
	private Stack<Integer>[] towers;

    // 指定回数
	private int times;

    // 移動回数
	private int count;

    // 各杭に積み上がっている円盤を出力する
	private void print() {
		for (Stack<Integer> tower : towers) {
			if (tower.empty()) {
                // 1つも円盤がない杭の行には「-」と出力
				System.out.println("-");
			} else {
				for (int i = 0; i < tower.size(); i++) {
                    // 各行の一番左を杭の一番下として半角空白区切りで出力
					if (i > 0)
						System.out.print(' ');
					System.out.print(tower.get(i));
				}
				System.out.println();
			}
		}
	}

    // n枚の円盤を杭srcから杭dstへ動かす
	private void hanoi(int n, Stack<Integer> src, Stack<Integer> dst, Stack<Integer> tmp) {
		if (this.count >= this.times) { // 終了
			return;
		}
		if (n == 1) {
            // 円盤を動かす
			dst.push(src.pop());

			if (++this.count == this.times) {
                // 指定回数動かした時点の各杭に積み上がっている円盤を出力
                print();
				return;
			}
		} else {
            // n-1枚の円盤を杭srcから杭tmpへ動かす
			hanoi(n - 1, src, tmp, dst);

            // n-1枚の円盤を杭srcから杭dstへ動かす
			hanoi(1, src, dst, tmp);

            // n-1枚の円盤を杭tmpから杭dstへ動かす
			hanoi(n - 1, tmp, dst, src);
		}
	}

	public void hanoi() {
		hanoi(this.n, towers[0], towers[2], towers[1]);
	}

	@SuppressWarnings("unchecked")
    // コンストラクタ
	public Hanoi(int n, int t) {
		this.n = n;

        // 杭を準備
		towers = (Stack<Integer>[]) new Stack<?>[3];
		for (int i = 0; i < towers.length; i++) {
			towers[i] = new Stack<Integer>();
		}

        // 杭Aの初期状態
		for (int i = n; i > 0; i--) {
			towers[0].add(i);
		}

        // 指定回数
		this.times = t;

        // 移動回数を初期化
		this.count = 0;
	}
}

public class Main {
	public static void main(String[] args) {
        // 入力を受け取る
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int t = sc.nextInt();
		sc.close();

        // ハノイの塔
		Hanoi hanoi = new Hanoi(n, t);
		hanoi.hanoi();
	}
}
```