【Ruby】ハノイの塔 (paizaランク A 相当)をやってみた

# ハノイの塔の状態を追跡するクラス
class Hanoi
  attr_accessor :rods

  # 初期化メソッド
  def initialize(n)
    @n = n
    @rods = { "A" => (1..n).to_a.reverse, "B" => [], "C" => [] }
  end

  # ディスクの移動メソッド
  def move_disk(from, to)
    disk = @rods[from].pop
    @rods[to].push(disk)
  end

  # ハノイの塔の再帰的な解法
  def solve_hanoi(n, from, to, aux, t, move_count)
    return move_count if move_count >= t

    if n == 1
      move_disk(from, to)
      move_count += 1
      return move_count if move_count >= t
    else
      move_count = solve_hanoi(n - 1, from, aux, to, t, move_count)
      return move_count if move_count >= t

      move_disk(from, to)
      move_count += 1
      return move_count if move_count >= t

      move_count = solve_hanoi(n - 1, aux, to, from, t, move_count)
    end
    move_count
  end

  # ハノイの塔をt回移動させるメソッド
  def simulate(t)
    solve_hanoi(@n, "A", "C", "B", t, 0)
  end

  # 各杭の状態を出力するメソッド
  def print_rods
    @rods.each_value do |rod|
      if rod.empty?
        puts "-"
      else
        puts rod.join(" ")
      end
    end
  end
end

# メイン処理
if __FILE__ == $0
  n, t = gets.split.map(&:to_i)
  hanoi = Hanoi.new(n)
  hanoi.simulate(t)
  hanoi.print_rods
end

解説

1. ハノイの塔の状態を追跡するクラス

   class Hanoi
     attr_accessor :rods
   

   • Hanoiクラスはハノイの塔の状態を追跡します。@rods変数は各杭の状態を保持します。

2. 初期化メソッド

   def initialize(n)
     @n = n
     @rods = { "A" => (1..n).to_a.reverse, "B" => [], "C" => [] }
   end
   

   • 初期化メソッドでは、円盤の数nを設定し、@rodsハッシュに各杭の初期状態を設定します。Aの杭には1からnまでの円盤が大きい順に積まれています。

3. ディスクの移動メソッド

   def move_disk(from, to)
     disk = @rods[from].pop
     @rods[to].push(disk)
   end
   

   • move_diskメソッドは指定された杭fromからtoに円盤を移動します。

4. ハノイの塔の再帰的な解法

   def solve_hanoi(n, from, to, aux, t, move_count)
     return move_count if move_count >= t
     if n == 1
       move_disk(from, to)
       move_count += 1
       return move_count if move_count >= t
     else
       move_count = solve_hanoi(n - 1, from, aux, to, t, move_count)
       return move_count if move_count >= t
       move_disk(from, to)
       move_count += 1
       return move_count if move_count >= t
       move_count = solve_hanoi(n - 1, aux, to, from, t, move_count)
     end
     move_count
   end
   

   • solve_hanoiメソッドはハノイの塔の再帰的な解法です。円盤を目的の回数tまで移動します。move_countは現在の移動回数を追跡します。

5. ハノイの塔をt回移動させるメソッド

   def simulate(t)
     solve_hanoi(@n, "A", "C", "B", t, 0)
   end
   

   • simulateメソッドはsolve_hanoiメソッドを呼び出し、円盤をt回移動させます。

6. 各杭の状態を出力するメソッド

   def print_rods
     @rods.each_value do |rod|
       if rod.empty?
         puts "-"
       else
         puts rod.join(" ")
       end
     end
   end
   

   • print_rodsメソッドは各杭の状態を出力します。空の杭は"-"と表示されます。

7. メイン処理

   if __FILE__ == $0
     n, t = gets.split.map(&:to_i)
     hanoi = Hanoi.new(n)
     hanoi.simulate(t)
     hanoi.print_rods
   end
   

   • メイン処理部分では、標準入力からnとtを取得し、Hanoiクラスを使用して円盤をt回移動させた後、各杭の状態を出力します。