ハノってみた

書いてみた

ハノイの塔
Ruby

def create_counter
  count = 0;
  return Proc.new do
    count += 1;
  end
end

$counter = create_counter()

def hanoi(n, from, work, dest)
  return if n.zero?
  hanoi(n-1, from, dest, work)
  puts "#{"%04d" % $counter.call}: move #{n}, from #{from} to #{dest}"
  hanoi(n-1, work, from, dest)
end

hanoi(4, "A", "B", "C")
# output
0001: move 1, from A to B
0002: move 2, from A to C
0003: move 1, from B to C
0004: move 3, from A to B
0005: move 1, from C to A
0006: move 2, from C to B
0007: move 1, from A to B
0008: move 4, from A to C
0009: move 1, from B to C
0010: move 2, from B to A
0011: move 1, from C to A
0012: move 3, from B to C
0013: move 1, from A to B
0014: move 2, from A to C
0015: move 1, from B to C

解法自体はいくつか解説サイトを見た。理解はできたが、似たような問題をまた見た時にサクッと解けるかは別問題。もう少し慣れが必要だろう。

出力に行番号が欲しかったので少し手を加えた。もっとスマートに出来ないものかなあ。
グローバル変数を使わなくて済むように、こんなのも書いてみた。

class Hanoi
  def initialize
    def create_counter
      count = 0
      return Proc.new do
        count += 1
      end
    end
    @counter = create_counter
  end

  def showAnswer(n, from, work, dest)
    return if n.zero?
    self.showAnswer(n-1, from, dest, work)
    puts "#{"%04d" % @counter.call}: move #{n}, from #{from} to #{dest}"
    self.showAnswer(n-1, work, from, dest)
  end
end

hanoi = Hanoi.new
hanoi.showAnswer(4, "A", "B", "C")

うーん。全くRubyを使いこなせてない気がする。

次の最善手

上記のプログラムが、ハノイの塔の最短解であることは理解している。しかし、任意の状態からの最短解は解けない。
たとえば、ハノイの塔をユーザが解くゲームがあるとする。ユーザがウンウン唸りながら色々と動かしてみた。しかし解けない！もうギブアップだ！そんな時に、「次の最善手」を教えてくれるプログラムはどんなものになるだろうか。
これはちょっと面白いような気がする。とても簡単なプログラムになるのか、あるいはひたすら探索するプログラムになるか、条件分岐を駆使した再帰呼出し関数になるか。
うーむ。うーむ。考えてみよう。。