はじめに
モチベーション
筆者は大学時代や会社でシェルを使いこなす人間を見て「かっこいい……やりたい……」と思い続けていたが本を買うだけ買ってほとんど読むことがなく日々をダラダラ過ごすしがないエンジニアである。
これは、コラボキャンペーンにかこつけてBashの経験を積んだ気になる自己満足のための記事である。
この記事の目的
- 読者がハノイの塔の解き方を理解する
- Bashに興味を持ってもらう
問題
概要
ハノイの塔というパズルがあります。
3つの杭があり、左から順にA,B,Cの杭とします。
杭Aに円盤が下から大きい順に n 個重なって置かれています。
この円盤は必ず1つ上の円盤は下の円盤より小さくなくてはいけないルールがあります。
このルールを守りながらAの杭からCの杭へ円盤を動かす操作をするパズルです。
例えば3つの円盤が入力として与えられる場合、その時の最短手順は以下の通りになります。
この時、円盤の数に寄らず最短手順は常に一意に決まります。
円盤の数 n が与えられます。1つも動かしていない状態を t = 0 とし、円盤を動かした回数を t とします。
円盤の数 n と、円盤を動かした回数 t が与えられるので n 個の円盤を最短手順で動かしていった時に円盤を動かした回数 t の状態を出力してください。
入力される値
入力は以下のフォーマットで与えられます。
n t
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。
期待する出力
n 個の円盤を最短手順で動かして行った時、 t 回動かした時点の各杭に積み上がっている円盤を出力してください。
1行目を杭A、2行目を杭B、3行目を杭Cとし、各行の一番左を杭の一番下として円盤の大きさを 1 から n の数字でスペース区切りで出力して下さい。
1つも円盤がない杭の行には「-」と出力して下さい。
条件
すべてのテストケースにおいて、以下の条件をみたします。
1 ≦ n ≦ 16
1 ≦ t ≦ 2^n - 1
入力例1
3 4
出力例1
-
2 1
3
入力例2
4 6
出力例2
4 1
3 2
-
解き方
入力
まずは競プロの導入でお馴染み、入力を読み込む必要がある。
bashでは入力を読み込むときreadコマンドを使用する。
今回はnとtの値を読み取るため、下記のようなコードになる
read n t
初期状態を設定
まずは状態を初期化する。
今回、杭ABCにどのくらい円盤があるかを配列を使って表現していく。
bashで配列を宣言するにはdeclare -aと書く。
- declareコマンド
- 変数の属性を設定する
- -aオプション
- 配列
そして、初期状態では全ての円盤がAにある。
なのでfor文を使ってAの配列にnまでの数の円盤を入れる。
この時、円盤は必ず1つ上の円盤は下の円盤より小さくなくてはいけないルールに従うため、nから配列に挿入する。
declare -a A B C
for ((i=n; i>=1; i--)); do
A+=($i)
done
ハノイの塔の動作
ここがこの問題のおそらく肝の部分のはず。
ハノイの塔を今回は再帰的に表現していく。
これから作るmove関数は、再起的に呼び出されることによって指定された回数分円盤を動かす。
変数について
- count (グローバル変数)
- 移動回数を保持するための変数
- num_disks (ローカル変数)
- 移動する円盤の数
- from (ローカル変数)
- 移動元の杭
- to (ローカル変数)
- 移動先の杭
- aux (ローカル変数)
- 移動に使う杭
-
終了条件のチェック
再帰関数には必ず終了条件というのが存在する。
今回、num_disksには移動したい円盤の数が入る。
この円盤が0の場合、再帰呼び出しを終了する。 -
動かしたい一つ前までの全ての円盤を移動に使う杭に動かす。
ここから問題にあったgifの動きを再現していく。
gifの1がcに移動した後の場所からの動きを実現する。
まずは一番下の円盤を目的の杭に動かすために邪魔な残り全ての円盤を移動に使う杭に動かす。 -
一番下の円盤を移動先に動かす
まず初めに移動回数がtに達している時これ以上の動作は不要であるため関数処理を終了する。
ここで登場するevalが分かりずらいと思うので詳しく説明していく。ここではまず杭の一番上の円盤を取り出している。
[-1]はfrom配列の最後の要素を示しており、diskにAの最後の要素を格納している。eval "disk=\${${from}[-1]}"次にform配列の最後の要素を削除する。
${from}[@]は配列全体を表しており、${#${from}[@]}は配列の要素数を意味する。
${${from}[@]:0:${#${from}[@]}-1}はスライス操作を行っている。
from配列を0から現在のfrom配列の要素数-1まで切り出したものに再代入している。eval "${from}=(\"\${${from}[@]:0:\${#${from}[@]}-1}\")"最後に最上部の円盤を移動先の杭に追加する。
diskに格納していた要素をto配列の最後尾(最上部)に追加する。eval "${to}+=($disk)"そして移動が終わった後に再度移動回数をチェックする。
-
2の時に動かした円盤を移動した一番下の円盤の上に動かす
declare -i count=0
move() {
local num_disks=$1
local from=$2
local to=$3
local aux=$4
# 1でやっている動き
if (( num_disks == 0 )); then
return
fi
# 2でやっている動き
move $((num_disks - 1)) $from $aux $to
# 3でやっている動き
if (( count == t )); then
return
fi
eval "disk=\${${from}[-1]}"
eval "${from}=(\"\${${from}[@]:0:\${#${from}[@]}-1}\")"
eval "${to}+=($disk)"
count=$((count + 1))
if (( count == t )); then
return
fi
# 4でやっている動き
move $((num_disks - 1)) $aux $to $from
}
今回はn個の円盤を杭Aから杭Cまで杭Bを使って動かしたいので下記のように呼び出していく
move $n A C B
evalについて
他のプログラミング言語を主流としている人の中にはなぜevalというものを使って変数に値を格納しているか疑問に思った人はいないだろうか。
このevalというのは変数を動的に評価するために必要になる。
配列のn番目などにアクセスする場合、fromという変数を解釈した後に[0]などが解釈される。
これが他の言語で成立するのはfromが動的に自動で解釈されるからであり、bashでこのような操作をするにはevalなど別の手段を使う必要がある。
結果の出力
もし要素数が0だったら"-"、そうでないなら配列を出力するように出力するprint_peg関数を作成し、それを使って結果を出力していく。
print_peg() {
peg=("$@")
if [ ${#peg[@]} -eq 0 ]; then
echo "-"
else
echo "${peg[@]}"
fi
}
print_peg "${A[@]}"
print_peg "${B[@]}"
print_peg "${C[@]}"
プログラム全体
#!/bin/bash
read n t
declare -a A B C
for ((i=n; i>=1; i--)); do
A+=($i)
done
declare -i count=0
move() {
local num_disks=$1
local from=$2
local to=$3
local aux=$4
if (( num_disks == 0 )); then
return
fi
move $((num_disks - 1)) $from $aux $to
# Step 2: 最下層の円盤を from から to へ移動
if (( count == t )); then
return
fi
eval "disk=\${${from}[-1]}"
eval "${from}=(\"\${${from}[@]:0:\${#${from}[@]}-1}\")"
eval "${to}+=($disk)"
count=$((count + 1))
if (( count == t )); then
return
fi
move $((num_disks - 1)) $aux $to $from
}
move $n A C B
print_peg() {
peg=("$@")
if [ ${#peg[@]} -eq 0 ]; then
echo "-"
else
echo "${peg[@]}"
fi
}
print_peg "${A[@]}"
print_peg "${B[@]}"
print_peg "${C[@]}"
追記(8/4)
evalを使わない方法をコメントにて教えてもらったのでご覧あれ。
bashのベストプラクティスとしてはevalは使わない方が良さそう。
参考記事