Fwd: Grid Folding (#63)


#1

Begin forwarded message:


#2

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


#3

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


#4

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


#5

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.


#6

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


#7

On 1/23/06, Matthew M. removed_email_address@domain.invalid wrote:

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

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

Levin, :slight_smile:


#8

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