[QUIZ] Grid Folding (#63)

[James_Edward_Gray_II]

From: Aditya Mahajan <adityam@umich.edu>
Date: January 22, 2006 5:13:03 AM CST
To: Matthew Moss <matthew.moss.coder@gmail.com>
Cc: james@grayproductions.net
Subject: Re: [QUIZ] Grid Folding (#63)

Hi Guys,

This is my first submission to Ruby Quiz. I have solved it in an obfuscated way of using Arrays and Matrices and moving back and forth between them. I am pretty sure there is a more elegent method, but what the heck, my method works Time taken ~ 4hrs.

The code passes Matthew's tests and also a few that I tried out by hand. Thanks for the super quiz.

Aditya

The first extra credit (handling dimensions other than 16x16) is
pretty darn easy, so you may want to start out on a 2x2 to get yer
basics working and move up. With that in mind, here are a few tests
to help verify your work. The test_2x2 tests all possible folding
combinations.

(NOTE: The 16x16 test below is the result of my own solution. I'm
fairly certain it's correct, but not 100%. So if you run this and
pass the other two tests but fail the 16x16 test, I'd be interested to
see your output and between us figure out what the expected solution
is.)

Oh, and if you have more tests, feel free to share.

require 'test/unit'
require 'test/unit/ui/console/testrunner'

class FoldTest < Test::Unit::TestCase
  def test_2x2
     folds = {"TR" => [4, 2, 1, 3],
              "BR" => [2, 4, 3, 1],
              "TL" => [3, 1, 2, 4],
              "BL" => [1, 3, 4, 2],
              "RT" => [1, 2, 4, 3],
              "RB" => [3, 4, 2, 1],
              "LT" => [2, 1, 3, 4],
              "LB" => [4, 3, 1, 2]}

     folds.each do |cmds,xpct|
        assert_equal xpct, fold(2, 2, cmds)
     end
  end

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

  def test_invalid
     assert_raise(RuntimeError) { fold(2, 2, "LR") } # too many horz folds
     assert_raise(RuntimeError) { fold(2, 2, "TRB") } # too many folds
     assert_raise(RuntimeError) { fold(3, 2, "LR") } # bad input dimensions
  end

end

Test::Unit::UI::Console::TestRunner.run(FoldTest)

--
________________________________________________________
Aditya Mahajan
EECS-Systems 1835 Shirley Lane, #C7
University of Michigan Ann Arbor, MI-48105
Ann Arbor MI (734) 262 4008
http://www.eecs.umich.edu/~adityam
_________________________________________________________

grid.rb (3.17 KB)

···

Begin forwarded message:

<--- On Jan 21, Matthew Moss wrote --->

[Matthew_D_Moss]

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

[Matthew_D_Moss]

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.

Well, I ended up cleaning up my submission a bit anyway. I still have
another approach in mind, but making a few changes to get this was
pretty easy. Now, I basically encode only one kind of fold
(top-to-bottom), and turn the paper a few times before and after the
fold to get the desired results.

I think I saw another approach do something very similar if not the
same, but I swear I didn't cheat! =)

class Integer
   def pow2?
      (self & (self-1)).zero? and not self.zero?
   end

   def even?
      (self & 1).zero?
   end
end

class Array
   def reflect # vertical
      self.reverse
   end

   def turn # 90 deg CCW
      self.transpose.reflect
   end

   def fold # top to bottom
      raise "Invalid fold." unless size.even?
      w, hh = self[0].size, size / 2
      above, below = self[0, hh].reverse, self[hh, hh]
      Array.build_2d(w,hh) { |r,c| above[r][c].reverse.concat below[r][c] }
   end

   def Array.build_2d(w, h)
      Array.new(h) do |r|
         Array.new(w) do |c|
            yield r, c
         end
      end
   end
end

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

   def fold!(cmds)
      cmds.each_byte do |cmd|
         case cmd
         when ?T
            @rows = @rows.fold
         when ?B
            @rows = @rows.turn.turn.fold.turn.turn
         when ?L
            @rows = @rows.turn.turn.turn.fold.turn
         when ?R
            @rows = @rows.turn.fold.turn.turn.turn
         end
      end
      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)
end

[Matthew_D_Moss]

Just realized I now use my Array.reflect in only one place, and it
only does a reverse, so that should be refactored out.

[Matthew_D_Moss]

Actually .... (and I feel like I'm saying this just for my own
benefit, please forgive my rambling) ... now that I put most
operations into Array, the Paper class is mostly pointless, since I
wanted to change mutating fold! to non-mutating fold (esp considering
its return type), and I might as well then just move the dimension
check, iteration and fold processing into the global fold function
anyway.

Silly me.

···

On 1/23/06, Matthew Moss <matthew.moss.coder@gmail.com> wrote:

Just realized I now use my Array.reflect in only one place, and it
only does a reverse, so that should be refactored out.

[Matthew_D_Moss]

On that note (i.e., that I'm talking to myself), here is the final
3-deep nested array version. I won't touch this again.

class Integer
   def pow2?
      (self & (self-1)).zero? and not self.zero?
   end

   def even?
      (self & 1).zero?
   end
end

class Array
   def reflect # vertical
      self.reverse
   end

   def turn # 90 deg CCW
      self.transpose.reflect
   end

   def fold # top to bottom
      raise "Invalid fold." unless size.even?
      w, hh = self[0].size, size / 2
      above, below = self[0, hh].reverse, self[hh, hh]
      Array.new_2d(w,hh) { |r,c| above[r][c].reverse.concat below[r][c] }
   end

   def Array.new_2d(w, h)
      Array.new(h) do |r|
         Array.new(w) do |c|
            yield r, c
         end
      end
   end
end

def fold(w, h, cmds)
   raise "Bad dimensions: #{w}x#{h}" unless w.pow2? and h.pow2?
   paper = Array.new_2d(w, h) { |r,c| [w*r + c + 1] }

   cmds.each_byte do |cmd|
      case cmd
      when ?T
         paper = paper.fold
      when ?R
         paper = paper.turn.fold.turn.turn.turn
      when ?B
         paper = paper.turn.turn.fold.turn.turn
      when ?L
         paper = paper.turn.turn.turn.fold.turn
      end
   end

   raise "Not enough folds!" unless paper[0][0] == paper.flatten
   paper[0][0]
end

[Levin_Alexander1 (Levin Alexander)]

require 'enumerator'
paper = (1..w*h).to_enum(:each_slice, w).to_a

Levin,

···

On 1/23/06, Matthew Moss <matthew.moss.coder@gmail.com> wrote:

   paper = Array.new_2d(w, h) { |r,c| [w*r + c + 1] }

[Paul_Novak]

This was a lot of fun, but I never got to the extra-extra credit.

My Grid holds an array of arrays of Cell objects. Using
Array#transpose it was easy to switch back and forth between an array
of rows or an array of columns to perform a fold operation was either
horizontal (row-wise) or vertical (column-wise).

Each of the fold methods operates on the Cells that lie on the top
surface of the Grid. To start, that is all of them. After a single
L-fold, it would be the (back of) the left half of all the rows.

Since a fold brings facing Cells together, touching Cells are linked
to one another. To find the Cells that are now on the top face, just
follow the chain of links from the appropriate half (left half for an
L-fold, say) to the other end of the chain. Those Cells will form the
new face which is operated on by the next fold instruction, and so on,
until a single Cell remains on the face.

To get the answer, just follow the chain of links from that single
face Cell through all the Cells to the end.

Hopefully, the foregoing makes sense. If not, the code is probably
easier to read...

def fold folds, rows = 16, cols = 16
  validate folds, rows, cols
  grid = Grid.new(rows, cols)
  folds.scan(/./){|op|grid.send(op)}
  return grid.list_values
end

def validate folds, rows, cols
  lr_folds = folds.count("LR")
  tb_folds = folds.count("TB")
  while rows>1
    rows/=2.0
    tb_folds-=1
  end
  while cols>1
    cols/=2.0
    lr_folds-=1
  end
  if rows!=1.0 or cols!=1.0 or tb_folds!=0 or lr_folds!=0
    fail "invalid fold instructions"
  end
end

class Grid
  attr_reader :face_rows, :face_cols
  def initialize (row_count, col_count)
    # set up array of arrays of Cells that can be transposed between
rows or columns
    @face_rows = Array.new(row_count) { |i|
     ((i*col_count+1)..((i+1)*col_count)).map{|v|Cell.new(v)}}.map{|r|r.to_a}
    @face_cols = @face_rows.transpose # this is just too easy
  end
  ## L,R,T,B could probably be refactored into one method, but this works...
  def L
    new_face = []
    @face_rows.each do |a|
      new_row=[]
      while c2 = a.pop
        c1 = a.shift
        new_row << c1.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_row.reverse # since folding flips it over
    end
    @face_rows = new_face
    @face_cols = @face_rows.transpose
  end
  def R
    new_face = []
    @face_rows.each do |a|
      new_row = []
      while c2 = a.pop
        c1 = a.shift
        new_row << c2.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_row
    end
    @face_rows = new_face
    @face_cols = @face_rows.transpose
  end
  def T
    new_face = []
    @face_cols.each do |a|
      new_col=[]
      while c2 = a.pop
        c1 = a.shift
        new_col << c1.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_col.reverse # since folding flips it over
    end
    @face_cols = new_face
    @face_rows = @face_cols.transpose
  end
  def B
    new_face = []
    @face_cols.each do |a|
      new_col=[]
      while c2 = a.pop
        c1 = a.shift
        new_col << c2.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_col
    end
    @face_cols = new_face
    @face_rows = @face_cols.transpose
  end

  def list_values
    @face_rows.flatten.first.get_chain.map{|x|x.value}
  end
end

class Cell

  attr_reader :links, :value
  def initialize value
    @value = value
    @links = []
  end
  def link_to c
    @links << c
  end
  def get_chain start_cell=self
    next_cell = @links.reject{|x|x==start_cell}.last
    next_cell ? [self] + next_cell.get_chain(self) : [self]
  end
  def inspect
    @value
  end
end

gridfolder.rb (2.59 KB)