 # [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.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 ||
2operations.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
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 [2c - 1] if (r <= 0) # c bits of 1 is 2c-1
return  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.size; end

raise “Not enough folds” if width > 1 or height > 1
@grid
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.reverse

• pair}
}
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’ )

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’

# 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

# 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

# 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

# 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.size != 1)
raise ArgumentError, “Paper not completely folded”
end
@values.flatten
end

protected

def split_along_v
left = []
right = []
cols = @values.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

# 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

# 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.