From: Paul Novak <novakps@...>
Date: 2006-01-24T12:00:23+09:00
Subject: Re: [QUIZ] Grid Folding (#63)

------=_Part_3182_26150165.1138071587515
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

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 =3D 16, cols =3D 16
  validate folds, rows, cols
  grid =3D Grid.new(rows, cols)
  folds.scan(/./){|op|grid.send(op)}
  return grid.list_values
end

def validate folds, rows, cols
  lr_folds =3D folds.count("LR")
  tb_folds =3D folds.count("TB")
  while rows>1
    rows/=3D2.0
    tb_folds-=3D1
  end
  while cols>1
    cols/=3D2.0
    lr_folds-=3D1
  end
  if rows!=3D1.0 or cols!=3D1.0 or tb_folds!=3D0 or lr_folds!=3D0
    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 =3D 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 =3D @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 =3D []
    @face_rows.each do |a|
      new_row=3D[]
      while c2 =3D a.pop
        c1 =3D 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 =3D new_face
    @face_cols =3D @face_rows.transpose
  end
  def R
    new_face =3D []
    @face_rows.each do |a|
      new_row =3D []
      while c2 =3D a.pop
        c1 =3D a.shift
        new_row << c2.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_row
    end
    @face_rows =3D new_face
    @face_cols =3D @face_rows.transpose
  end
  def T
    new_face =3D []
    @face_cols.each do |a|
      new_col=3D[]
      while c2 =3D a.pop
        c1 =3D 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 =3D new_face
    @face_rows =3D @face_cols.transpose
  end
  def B
    new_face =3D []
    @face_cols.each do |a|
      new_col=3D[]
      while c2 =3D a.pop
        c1 =3D a.shift
        new_col << c2.get_chain[-1]
        c1.link_to c2
        c2.link_to c1
      end
      new_face << new_col
    end
    @face_cols =3D new_face
    @face_rows =3D @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 =3D value
    @links =3D []
  end
  def link_to c
    @links << c
  end
  def get_chain start_cell=3Dself
    next_cell =3D @links.reject{|x|x=3D=3Dstart_cell}.last
    next_cell ? [self] + next_cell.get_chain(self) : [self]
  end
  def inspect
    @value
  end
end

------=_Part_3182_26150165.1138071587515
Content-Type: application/octet-stream; name=gridfolder.rb
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="gridfolder.rb"

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















------=_Part_3182_26150165.1138071587515--