[SOLUTION] Grid Folding (#63)


#1

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 ||
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[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 [2c - 1] if (r <= 0) # c bits of 1 is 2c-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


#2

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

    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!
}
}
paper.answer
end


#3

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


#4

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