もっとハノってみた

ハノイの塔が途中経過状態でも解を出せるように改良してみた。

state = [[5, 3, 1], [4], [2]]
hanoi(5, state, "A", "B", "C")

で、何がしたいのかは分かるでしょ。

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

$counter = create_counter()

def hanoi(n, state, from, work, dest)
  return if n.zero?

  # Get index
  index = 0
  state.each_with_index do |item, idx|
    index = idx if item.include? n
  end

  case index
  when 0
    from_state, work_state, dest_state = state
    
    # Move obstacle
    if work_state.include? n-2
      hanoi(item, [work_state, from_state, dest_state], work, from, dest)
    end
    
    hanoi(n-1, [from_state, dest_state, work_state], from, dest, work)

    # Move obstacle
    if dest_state.include? n-2
      hanoi(item, [dest_state, from_state, work_state], dest, from, work)
    end

    puts "#{"%04d" % $counter.call}: move #{n}, from #{from} to #{dest}"

    dest_state.push(from_state.pop)
    hanoi(n-1, [work_state, from_state, dest_state], work, from, dest)
  when 1
    from_state, work_state, dest_state = state
    hanoi(n, [work_state, from_state, dest_state], work, from, dest)    
  when 2
    hanoi(n-1, state, from, work, dest)
  end
end

state = [[5, 3, 1], [4], [2]]
hanoi(5, state, "A", "B", "C")

# Output
0001: move 1, from A to C
0002: move 3, from A to B
0003: move 1, from C to A
0004: move 2, from C to B
0005: move 1, from A to B
0006: move 5, from A to C
0007: move 1, from B to A
0008: move 2, from B to C
0009: move 1, from A to C
0010: move 3, from B to A
0011: move 1, from C to B
0012: move 2, from C to A
0013: move 1, from B to A
0014: move 4, from B to C
0015: move 1, from A to C
0016: move 2, from A to B
0017: move 1, from C to B
0018: move 3, from A to C
0019: move 1, from B to A
0020: move 2, from B to C
0021: move 1, from A to C

まあ解けてるみたいなんですが、問題は

• 「これが最短解である証明」
• 「どの場合でもこのプログラムで解けるかのテストを通過していない」

の二点です。ていうかホントにあってんのかコレ。

あと、相変わらずRubyっぽい書き方になっていないような気がする。
コードをスマートに書き、可読性を高めるための道具が色々と揃っているってのが、初心者から見たRubyの大きな魅力。
メタプロ等を可能にする柔軟性や言語設計のセンスの高さなどを実感するにはまだまだ修行が足りない。
まずは「Rubyらしい書き方」を身に着けたい。自分のコードは「Cを部分的にRubyに置き換えただけ」な感が拭えない。