rustedの日記

■ [ruby][quiz]Grid Folding (#63) 22:29

16×16サイズの紙を指定されたコマンドで半分ずつ折っていく問題(http://www.rubyquiz.com/quiz63.html)。最終的に1×1サイズになったところで、グリッドについていた番号を上から並べて出力する。

この例がわかりやすい。

12

34

fold("RB") => [3, 4, 2, 1]

fold("TL") => [3, 1, 2, 4]

fold("LR") => raise exception for invalid input

コマンドは"T"(上辺を下辺に合わせるように折る。折った後、上辺側が上になる)、"B"(下辺を上辺に～)、"L"(左辺を右辺に～)、"R"(右辺を左辺に～)の4つ。折ったときに上になるほうは並びが反転するけど、下になるほうはそのままなことに注意する必要があるかな。

Extra credit: Make your fold function take an additional input parameter(s), the dimensions of the paper; dimensions should be power-of-2 in order to fold down to one cell.

サイズを指定できるようにするといいらしい。あと最終的に1つのマスにたたみこむために、1辺の長さを2の累乗にするべきとのこと。

今回のソース。

#!/usr/bin/ruby
# Grid Folding (#63)

class Paper
  def initialize(n)
    i = 2
    while i != n
      if i > n
        raise "invalid dimension"
      end
      i *= 2
    end
    @width = n
    @height = n
    @grid = Array.new(n * n)
    i = 0
    while i < @grid.size
      @grid[i] = [ i + 1 ]
      i += 1
    end
  end

  def pos(x, y)
    return x + y * @width
  end

  def to_bottom
    if @height == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = @height / 2
    while y < @height
      while x < @width
        i = pos(x, @height - 1 - y) 
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end    
    @grid.delete_if { |g| g.size != size }
    @height = @height / 2
  end
  
  def to_top
    if @height == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = 0
    while y < @height / 2
      while x < @width
        i = pos(x, @height - 1 - y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @height = @height / 2
  end

  def to_right
    if @width == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = @width / 2
    y = 0
    while y < @height
      while x < @width
        i = pos(@width - 1 - x, y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = @width / 2
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @width = @width / 2
  end
  
  def to_left
    if @width == 1
      raise "invalid input"
    end
    size = @grid[0].size * 2
    x = 0
    y = 0
    while y < @height
      while x < @width / 2
        i = pos(@width - 1 - x, y)
        @grid[i] = @grid[i].reverse
        @grid[pos(x, y)] = @grid[i] + @grid[pos(x, y)]
        x += 1
      end
      x = 0
      y += 1
    end
    @grid.delete_if { |g| g.size != size }
    @width = @width / 2
  end

  def fold(str)
    while str.size > 0
      case str
      when /\AT/o
        to_bottom
      when /\AB/o
        to_top
      when /\AL/o
        to_right
      when /\AR/o
        to_left
      when /\A./o
        raise "invalid input"
      end
      str = $'
    end
    return @grid.first
  end
end

paper = Paper.new((ARGV[1] || 16).to_i)
p paper.fold(ARGV[0] || "")

実行結果。

$ ./grid_folding.rb "RBLT" 4
[2, 3, 15, 14, 13, 16, 4, 1, 5, 8, 12, 9, 10, 11, 7, 6]
$ ./grid_folding.rb "RBLTRT" 8
[19, 22, 46, 43, 42, 47, 23, 18, 10, 15, 55, 50, 51, 54, 14, 11, 12, 13, 53, 52, 
49, 56, 16, 9, 17, 24, 48, 41, 44, 45, 21, 20, 28, 29, 37, 36, 33, 40, 32, 25, 
1, 8, 64, 57, 60, 61, 5, 4, 3, 6, 62, 59, 58, 63, 7, 2, 26, 31, 39, 34, 35, 38, 
30, 27]
$ ./grid_folding.rb "LLLLBBBB" 16
[32, 17, 24, 25, 28, 21, 20, 29, 30, 19, 22, 27, 26, 23, 18, 31, 239, 226, 231, 
234, 235, 230, 227, 238, 237, 228, 229, 236, 233, 232, 225, 240, 160, 145, 152, 
153, 156, 149, 148, 157, 158, 147, 150, 155, 154, 151, 146, 159, 111, 98, 103, 
106, 107, 102, 99, 110, 109, 100, 101, 108, 105, 104, 97, 112, 96, 81, 88, 89, 92, 
85, 84, 93, 94, 83, 86, 91, 90, 87, 82, 95, 175, 162, 167, 170, 171, 166, 163, 
174, 173, 164, 165, 172, 169, 168, 161, 176, 224, 209, 216, 217, 220, 213, 212, 
221, 222, 211, 214, 219, 218, 215, 210, 223, 47, 34, 39, 42, 43, 38, 35, 46, 45, 
36, 37, 44, 41, 40, 33, 48, 64, 49, 56, 57, 60, 53, 52, 61, 62, 51, 54, 59, 58, 
55, 50, 63, 207, 194, 199, 202, 203, 198, 195, 206, 205, 196, 197, 204, 201, 
200, 193, 208, 192, 177, 184, 185, 188, 181, 180, 189, 190, 179, 182, 187, 186, 
183, 178, 191, 79, 66, 71, 74, 75, 70, 67, 78, 77, 68, 69, 76, 73, 72, 65, 80, 
128, 113, 120, 121, 124, 117, 116, 125, 126, 115, 118, 123, 122, 119, 114, 127, 
143, 130, 135, 138, 139, 134, 131, 142, 141, 132, 133, 140, 137, 136, 129, 144, 
256, 241, 248, 249, 252, 245, 244, 253, 254, 243, 246, 251, 250, 247, 242, 255, 
15, 2, 7, 10, 11, 6, 3, 14, 13, 4, 5, 12, 9, 8, 1, 16]

できた？？サイズ4×4ではできているはず。チェック関数も実装する必要があるかな。