Time to Read

1分

ハノイの塔も解けないプログラマなんて……、って言われたので解いてみた。

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

require 'logger'
class Hanoi
  def initialize(size=3, options={})
    @logger = Logger.new(STDOUT)
    @options = options
    @bars = {
      :a => [],
      :b => [],
      :c => []
    }
    @size = size.to_i
    @step = 0
 
    if @size < 2
      @bars[:a] += [1]
    else
      @bars[:a] += (1..@size).to_a.reverse
    end
 
    logger.info "A tower has #{@size} disk(s)"
  end
  attr_reader :logger
  private :logger
 
  def hanoi_move(bar1, bar2, size=@size)
    if size < 2
      hanoi_move_one_disc(bar1, bar2, size)
    else
      left = (@bars.keys - [bar1, bar2]).first
      hanoi_move(bar1, left, size - 1) 
      hanoi_move_one_disc(bar1, bar2, size)
      hanoi_move(left, bar2, size - 1)
    end
  end
 
  def hanoi_move_one_disc(bar1, bar2, size)
    @bars[bar2].push(@bars[bar1].pop) 
    logger.info "Disk #{size} is moved to #{bar1.to_s.upcase} to #{bar2.to_s.upcase}"
    if @options[:verbose]
      require 'pp'
      logger.debug @bars.pretty_inspect.chomp
    end
    @step += 1
  end
 
  def finalize
    logger.info "Moved with: #{@step} step(s)"
  end
 
  def self.to_hanoi(size=3, options={})
    hanoi = new(size, options)
    hanoi.hanoi_move(:a, :c)
    hanoi.finalize
  end
end
irb(main):041:0> Hanoi.to_hanoi(4)
I, [2011-06-13T11:22:46.154585 #26427]  INFO -- : A tower has 4 disk(s)
I, [2011-06-13T11:22:46.154799 #26427]  INFO -- : Disk 1 is moved to A to B
I, [2011-06-13T11:22:46.154902 #26427]  INFO -- : Disk 2 is moved to A to C
I, [2011-06-13T11:22:46.154975 #26427]  INFO -- : Disk 1 is moved to B to C
I, [2011-06-13T11:22:46.155037 #26427]  INFO -- : Disk 3 is moved to A to B
I, [2011-06-13T11:22:46.155129 #26427]  INFO -- : Disk 1 is moved to C to A
I, [2011-06-13T11:22:46.155201 #26427]  INFO -- : Disk 2 is moved to C to B
I, [2011-06-13T11:22:46.155292 #26427]  INFO -- : Disk 1 is moved to A to B
I, [2011-06-13T11:22:46.155391 #26427]  INFO -- : Disk 4 is moved to A to C
I, [2011-06-13T11:22:46.155475 #26427]  INFO -- : Disk 1 is moved to B to C
I, [2011-06-13T11:22:46.155538 #26427]  INFO -- : Disk 2 is moved to B to A
I, [2011-06-13T11:22:46.155604 #26427]  INFO -- : Disk 1 is moved to C to A
I, [2011-06-13T11:22:46.155695 #26427]  INFO -- : Disk 3 is moved to B to C
I, [2011-06-13T11:22:46.155805 #26427]  INFO -- : Disk 1 is moved to A to B
I, [2011-06-13T11:22:46.155902 #26427]  INFO -- : Disk 2 is moved to A to C
I, [2011-06-13T11:22:46.156005 #26427]  INFO -- : Disk 1 is moved to B to C
I, [2011-06-13T11:22:46.156100 #26427]  INFO -- : Moved with: 15 step(s)
=> true

see also