From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-01-23T07:11:50+09:00
Subject: Re: [QUIZ] Grid Folding (#63)

Here is my own solution, using 3-deep nested arrays. I could clean
this up a bit more, I think, but I am looking at another approach I
want to try before I summarize later this week.


class Integer
   def pow2?
      (self & (self-1)) == 0
   end
end


class Paper
   def build(w, h)
      Array.new(h) do |r|
         Array.new(w) do |c|
            yield r, c
         end
      end
   end

   def initialize(w, h)
      raise "Bad dimensions: #{w}x#{h}" unless w.pow2? and h.pow2?
      @rows = build(w, h) { |r,c| [w*r + c + 1] }
   end

   def rows
      @rows.dup
   end

   def cols
      build(@rows.size, @rows[0].size) { |c,r| @rows[r][c] }
   end

   def v_fold(i)
      rs = rows
      hh = rs.size / 2
      raise "Too many vertical folds." if hh == 0
      above, below = rs[i*hh, hh].reverse, rs[(1-i)*hh, hh]
      build(above[0].size, above.size) do |r, c|
         above[r][c].reverse.concat below[r][c]
      end
   end

   def h_fold(i)
      cs = cols
      hw = cs.size / 2
      raise "Too many horizontal folds." if hw == 0
      above, below = cs[i*hw, hw].reverse, cs[(1-i)*hw, hw]
      build(above.size, above[0].size) do |c, r|
         above[r][c].reverse.concat below[r][c]
      end
   end

   def fold!(cmds)
      cmds.each_byte do |cmd|
         case cmd
         when ?T
            @rows = v_fold(0)
         when ?B
            @rows = v_fold(1)
         when ?L
            @rows = h_fold(0)
         when ?R
            @rows = h_fold(1)
         end
      end
      self
   end

    def result
      raise "Not enough folds!" unless @rows[0][0] == @rows.flatten
      @rows[0][0]
   end
end


def fold(w, h, cmds)
   Paper.new(w, h).fold!(cmds).result
end