【Ruby】 ハノイの塔を解く

Rubyでハノイの塔を解いてみます。

ソースコード

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

class Hanoi   def initialize(disk_num)     @disk_num = disk_num     @poles = [       {:name => "A", :disks => @disk_num.times.to_a},       {:name => "B", :disks => []},       {:name => "C", :disks => []}     ]     puts self     printf "\e[#{@disk_num + 2}A"; STDOUT.flush; #sleep 0.1   end     def to_s     "\n" << 3.times.map do       "#{" " * (@disk_num + 1)}\e[47m \e[0m#{" " * (@disk_num + 1)}"     end.join("") << "\n" <<     @disk_num.times.map do |n|       3.times.map do |i|         if @poles[i][:disks].size - @disk_num + n > -1           d = @poles[i][:disks][@poles[i][:disks].size - @disk_num + n]           "\e[46m#{" " * (d + 1)}\e[0m".rjust(10 + @disk_num, " ") <<           "\e[46m \e[0m" <<           "\e[46m#{" " * (d + 1)}\e[0m".ljust(10 + @disk_num, " ")         else           "#{" " * (@disk_num + 1)}\e[47m \e[0m#{" " * (@disk_num + 1)}"         end       end.join("")     end.join("\n")   end     def start     hanoi(@disk_num, *@poles.map { |pole| pole[:name] })     puts self   rescue Interrupt     exit 0   end     def hanoi(n, from, tmp, to)     return if n == 0     hanoi(n-1, from, to, tmp)     # puts "move #{n} from #{from} to #{to}"     move(from, to)     hanoi(n-1, tmp, from, to)   end     def move(from, to)     from_pole = @poles.find{ |pole| pole[:name] == from }     to_pole = @poles.find{ |pole| pole[:name] == to }     to_pole[:disks].unshift from_pole[:disks].shift     puts self     printf "\e[#{@disk_num + 2}A"; STDOUT.flush; #sleep 0.1   end end   hanoi = Hanoi.new(11) hanoi.start

実際に解いているのはhanoiメソッドで再帰している部分（38行目〜44行目あたり）だけで、それ以外はアルゴリズムと関係ない、途中経過を表示するためだけの処理です。

Hanoiクラスのインスタンスを生成するときに与える引数が、ハノイの塔の段数です。今回の例では11段にしてみましたが、20段とか30段とかやってみるとおもしろいですよ（なかなか終わらないですが）。

実行結果

円盤の動きはわかり辛いですが、こう、バーっと表示すると解いてる感あって楽しいですよね。

おわりに

落書きスクリプトシリーズ。
アルゴリズムの説明は詳しく解説しているサイトがたくさんあるので…。