# \[SOLUTION\] Grid Folding (#63)

**URL:** <https://www.ruby-forum.com/t/solution-grid-folding-63/64366>\
**Category:** Ruby\
**Created:** [January 23, 2006, 7:14am UTC](https://www.ruby-forum.com/t/solution-grid-folding-63/64366 "2006-01-23T07:14:26Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [January 23, 2006, 7:14am UTC](https://www.ruby-forum.com/t/solution-grid-folding-63/64366/1 "2006-01-23T07:14:26Z")

</div>

def fold(row, col, operations)

def t2b(table)  
t1 = table[0…table.size/2].reverse  
t2 = table[table.size/2…-1]  
row = t1.size  
col = t1[0].size  
row.times { |r| col.times { |c| t2[r][c] = t1[r][c].reverse +  
t2[r][c] } }  
t2  
end

def b2t(table)  
t2b(table.reverse).reverse  
end

def l2r(table)  
t2b(table.transpose).transpose  
end

def r2l(table)  
t2b(table.transpose.reverse).reverse.transpose  
end

if row \<= 1 ||  
col \<= 1 ||  
2**operations.size != row \* col ||  
operations =~ /[^TBLR]/ ||  
2**operations.gsub(/[LR]/,’’).size != row  
raise “Error: parameters are not correct.”  
end

index = 0  
table = Array.new(row) { Array.new(col) { [index += 1] } }

operations.each\_byte do |op|  
table = case op  
when ?T : t2b(table)  
when ?B : b2t(table)  
when ?L : l2r(table)  
when ?R : r2l(table)  
else raise “Error: Invalid fold operation.”  
end  
end

table[0][0]  
end

#========================================================================#

def check\_fold(row, col, result)

# find all combinations with binary 0 for row and 1 for column

operation  
def all\_orders(r, c) #  
return [2**c - 1] if (r \<= 0) # c bits of 1 is 2**c-1  
return [0] if (c \<= 0) # r bits of 0 is 0  
table = []  
all\_orders(r-1,c).each { |t| table \<\< ((t \<\< 1) + 0) }  
all\_orders(r,c-1).each { |t| table \<\< ((t \<\< 1) + 1) }  
table  
end

if row \<= 1 ||  
col \<= 1 ||  
row \* col != result.size ||  
2 \*\* (Math.log(row)/Math.log(2)).to\_i != row ||  
2 \*\* (Math.log(col)/Math.log(2)).to\_i != col  
raise “Error: Parameters are not correct.”  
end

r = Integer(Math.log(row) / Math.log(2))  
c = Integer(Math.log(col) / Math.log(2))  
all\_rc\_orders = all\_orders(r,c)

row.times do |tb\_operation|  
col.times do |lr\_operation|  
all\_rc\_orders.each do |order|  
operations = ‘’  
tb\_op = tb\_operation  
lr\_op = lr\_operation  
(r+c).times do  
if (order & 1 == 0)  
operations += (tb\_op & 1 == 0) ? ‘T’ : ‘B’  
tb\_op \>\>= 1  
else  
operations += (lr\_op & 1 == 0) ? ‘L’ : ‘R’  
lr\_op \>\>= 1  
end  
order \>\>= 1  
end  
return operations if fold(row, col, operations) == result  
end  
end  
end  
“No solution.”  
end

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [January 23, 2006, 10:48am UTC](https://www.ruby-forum.com/t/solution-grid-folding-63/64366/2 "2006-01-23T10:48:56Z")

</div>

This is the kind of problem where it makes sense to trade off  
efficiency for simplicity.

class Paper  
def initialize(width, height)  
@grid = Array.new(width) { Array.new(height) }  
height.times { |y| width.times {|x| @grid[x][y] = [width\*y+x+1] }}  
end

def width; @grid.size; end  
def height; @grid[0].size; end

def answer  
raise “Not enough folds” if width \> 1 or height \> 1  
@grid[0][0]  
end

# Fold right side over to left

def fold!  
raise “Bad input” if width%2 == 1  
@grid = (0 … (width / 2 - 1)).map { |col|  
@grid[col].zip(@grid[width - col - 1]).map {|pair| pair[1].reverse

- pair[0]}  
}  
end

def fold(width, height, commands)  
turns = commands.tr(‘RBLT’, ‘0123’).split(//).map{|x| x.to\_i}  
paper = Paper.new(width, height)  
turns.each { |turn|  
4.times {|i|  
paper.fold! if i==turn  
paper.rotate!  
}  
}  
paper.answer  
end

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [January 23, 2006, 4:03pm UTC](https://www.ruby-forum.com/t/solution-grid-folding-63/64366/3 "2006-01-23T16:03:04Z")

</div>

Correction:  
found a little bug on my script.  
The checking row \<= 1 || col \<= 1 is “too much”.  
These two checking should remove,  
because it fail for doing something like fold( 1, 2, ‘L’ )

---

<div class="post-metadata">

**Author:** ![davidtl](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/35a633/32.png) [@davidtl](https://www.ruby-forum.com/u/davidtl)\
**Post date:** [January 24, 2006, 10:21am UTC](https://www.ruby-forum.com/t/solution-grid-folding-63/64366/4 "2006-01-24T10:21:01Z")

</div>

Cleaned up the code in my previous solution. Made check\_fold not  
copy the array and instead just index into the array passed.  
Completely changed FoldMatrix to use 3-d array and operations that  
make it more readable like split, flip, and place over.

#! /usr/bin/env ruby -w

require ‘enumerator’

# Fold up matrix of numbers using given directions where directions

# are in a string with T = top, B = bottom, L = left, R = right:

# “TLBR”. Throws ArgumentError on invalid direction or rows or cols

# not a power of 2.

def fold(directions, rows=16, cols=16)  
check\_rows\_and\_cols(rows, cols)  
if (directions =~ /[^TLBR]/)  
raise ArgumentError, “Invalid direction given”  
end

# build array of values

# using each\_slice as described by Levin A.

values = (1…rows\*cols).to\_enum(:each\_slice, 1).to\_a  
values = values.to\_enum(:each\_slice, cols).to\_a

fold\_matrix = FoldMatrix.new(values)

directions.split(//).each do |direction|  
fold\_matrix.fold(direction)  
end  
fold\_matrix.result  
end

# Get the folding directions from a fold array. The item that has

# never been folded over is at end of array. The item that wasn’t

# folded until the last fold and is now at at the first of array.

# Can iterate through last folded by continually cutting array in

# half. Throws ArgumentError on array not in fold order or rows or

# cols not power of 2.

def check\_fold(fold\_result, rows=16, cols=16)  
check\_rows\_and\_cols(rows, cols)

directions = “”  
folded = 0  
size = fold\_result.size  
while folded \< fold\_result.size - 1  
# get direction in original matrix from last to first  
directions \<\< direction\_to(fold\_result.last, fold\_result  
[folded], cols)

```
 # move to next item last folded
 size = size/2
 folded += size

```

end  
directions.reverse  
end

class FoldMatrix

attr\_reader :values

def initialize(values)  
@values = values  
end

# Return a new fold matrix by folding in direction where direction

# is one of :left, :right, :top, :bottom.

def fold(direction)  
case direction  
when “L”  
left, @values = split\_along\_v  
flip\_along\_v(left)  
place\_over(left)  
when “R”  
@values, right = split\_along\_v  
flip\_along\_v(right)  
place\_over(right)  
when “T”  
top, @values = split\_along\_h  
flip\_along\_h(top)  
place\_over(top)  
when “B”  
@values, bottom = split\_along\_h  
flip\_along\_h(bottom)  
place\_over(bottom)  
end  
end

# Return the result of folding in flattened array

def result  
if (@values.size != 1 && @values[0].size != 1)  
raise ArgumentError, “Paper not completely folded”  
end  
@values.flatten  
end

protected

def split\_along\_v  
left = []  
right = []  
cols = @values[0].size  
@values.each do |row|  
left \<\< row[0…cols/2]  
right \<\< row[cols/2…cols]  
end  
return left, right  
end

def split\_along\_h  
rows = @values.size  
top = @values[0…rows/2]  
bottom = @values[rows/2…rows]  
return top, bottom  
end

def flip\_along\_v(a)  
a.each do |row|  
row.reverse!  
row.each {|item| item.reverse!}  
end  
end

def flip\_along\_h(a)  
a.reverse!  
a.each {|row| row.each {|item| item.reverse!}}  
end

def place\_over(top)  
top.each\_with\_index do |row, i|  
row.each\_with\_index do |item, j|  
@values[i][j] = item + @values[i][j]  
end  
end  
end  
end

# Determine if a number is a power of 2

def is\_power\_of\_2(number)  
return false if number \< 1

# keep on shifting left until number equals one (power of 2) or has

# one bit set but isn’t one (not power of 2)

while number \> 1  
number \>\>= 1  
return false if ((number & 1) == 1 && number != 1)  
end  
true  
end

def coordinate(index, cols)  
index -= 1  
i, j = index/cols, index%cols  
end

# Get the direction from an unfolded matrix element to the one

# just folded to the top. Both must be in same row or column.

def direction\_to(unfolded, folded, cols)  
unfolded\_i, unfolded\_j = coordinate(unfolded, cols)  
folded\_i, folded\_j = coordinate(folded, cols)

i\_compare = unfolded\_i \<=\> folded\_i  
j\_compare = unfolded\_j \<=\> folded\_j

case [i\_compare, j\_compare]  
when [0, 1] then “L”  
when [0, -1] then “R”  
when [1, 0] then “T”  
when [-1, 0] then “B”  
else  
raise ArgumentError, "Values not in same row or column: " +  
“#{unfolded}, #{folded}, #{rows}x#{cols}”  
end  
end

def check\_rows\_and\_cols(rows, cols)  
unless is\_power\_of\_2(rows)  
raise ArgumentError, “Rows must be power of two”  
end  
unless is\_power\_of\_2(cols)  
raise ArgumentError, “Cols must be power of two”  
end  
end