# Fwd: Grid Folding (#63)

**URL:** <https://www.ruby-forum.com/t/fwd-grid-folding-63/53010>\
**Category:** Ruby\
**Created:** [January 22, 2006, 7:21pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010 "2006-01-22T19:21:10Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 22, 2006, 7:21pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/1 "2006-01-22T19:21:10Z")

</div>

Begin forwarded message:

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 22, 2006, 11:13pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/2 "2006-01-22T23:13:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 23, 2006, 5:16pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/3 "2006-01-23T17:16:01Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 23, 2006, 5:16pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/4 "2006-01-23T17:16:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 23, 2006, 5:19pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/5 "2006-01-23T17:19:05Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 23, 2006, 5:25pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/6 "2006-01-23T17:25:37Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 23, 2006, 5:41pm UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/7 "2006-01-23T17:41:10Z")

</div>

On 1/23/06, Matthew M. [removed\_email\_address@domain.invalid](mailto: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, 🙂

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 24, 2006, 4:01am UTC](https://www.ruby-forum.com/t/fwd-grid-folding-63/53010/8 "2006-01-24T04:01:08Z")

</div>

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