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

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

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

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

# 90 degree counter clockwise rotation
def rotate!
@grid = @grid.transpose.map{|c| c.reverse}
end
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!
}
}
end

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' )

···

On 1/23/06, David Tran <email55555@gmail.com> wrote:

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

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 Alexander
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

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]
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