【Ruby】 ハノイの塔を解く

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

ソースコード

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段とかやってみるとおもしろいですよ（なかなか終わらないですが）。

実行結果

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

おわりに

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