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

[David Tran]

def fold(row, col, operations)

def t2b(table)
t1 =3D table[0...table.size/2].reverse
t2 =3D table[table.size/2..-1]
row =3D t1.size
col =3D t1[0].size
row.times { |r| col.times { |c| t2[r][c] =3D 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 <=3D 1 ||
col <=3D 1 ||
2**operations.size !=3D row * col ||
operations =3D~ /[^TBLR]/ ||
2**operations.gsub(/[LR]/,'').size !=3D row
raise "Error: parameters are not correct."
end

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

operations.each_byte do |op|
table =3D 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

#=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D#

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 <=3D 0) # c bits of 1 is 2**c-1
return [0] if (c <=3D 0) # r bits of 0 is 0
table =3D []
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 <=3D 1 ||
col <=3D 1 ||
row * col !=3D result.size ||
2 ** (Math.log(row)/Math.log(2)).to_i !=3D row ||
2 ** (Math.log(col)/Math.log(2)).to_i !=3D col
raise "Error: Parameters are not correct."
end

r =3D Integer(Math.log(row) / Math.log(2))
c =3D Integer(Math.log(col) / Math.log(2))
all_rc_orders =3D all_orders(r,c)

row.times do |tb_operation|
col.times do |lr_operation|
all_rc_orders.each do |order|
operations =3D ''
tb_op =3D tb_operation
lr_op =3D lr_operation
(r+c).times do
if (order & 1 =3D=3D 0)
operations +=3D (tb_op & 1 =3D=3D 0) ? 'T' : 'B'
tb_op >>=3D 1
else
operations +=3D (lr_op & 1 =3D=3D 0) ? 'L' : 'R'
lr_op >>=3D 1
end
order >>=3D 1
end
return operations if fold(row, col, operations) =3D=3D result
end
end
end
"No solution."
end

 

[Edward Faulkner]

--Yylu36WmvOXNoKYn
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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


class Paper
def initialize(width, height)
@grid =3D Array.new(width) { Array.new(height) }
height.times { |y| width.times {|x| @grid[x][y] =3D [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 =3D=3D 1
@grid =3D (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 =3D @grid.transpose.map{|c| c.reverse}
end
end

def fold(width, height, commands)
turns =3D commands.tr('RBLT', '0123').split(//).map{|x| x.to_i}
paper =3D Paper.new(width, height)
turns.each { |turn|
4.times {|i|
paper.fold! if i=3D=3Dturn
paper.rotate!
}
} =20
paper.answer
end

--Yylu36WmvOXNoKYn
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFD1KYknhUz11p9MSARAo31AJ0ZVoQM7on1ogLTvRwU3yEjxVPWMgCeOGh8
GLZHoli43xG7bPWppnKCd2M=
=uO2s
-----END PGP SIGNATURE-----

--Yylu36WmvOXNoKYn--

 

[David Tran]

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

def fold(row, col, operations)

def t2b(table)
t1 =3D table[0...table.size/2].reverse
t2 =3D table[table.size/2..-1]
row =3D t1.size
col =3D t1[0].size
row.times { |r| col.times { |c| t2[r][c] =3D 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 <=3D 1 ||
col <=3D 1 ||
2**operations.size !=3D row * col ||
operations =3D~ /[^TBLR]/ ||
2**operations.gsub(/[LR]/,'').size !=3D row
raise "Error: parameters are not correct."
end

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

operations.each_byte do |op|
table =3D 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

#=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D#

def check_fold(row, col, result)

# find all combinations with binary 0 for row and 1 for column operatio= n
def all_orders(r, c) #
return [2**c - 1] if (r <=3D 0) # c bits of 1 is 2**c-1
return [0] if (c <=3D 0) # r bits of 0 is 0
table =3D []
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 <=3D 1 ||
col <=3D 1 ||
row * col !=3D result.size ||
2 ** (Math.log(row)/Math.log(2)).to_i !=3D row ||
2 ** (Math.log(col)/Math.log(2)).to_i !=3D col
raise "Error: Parameters are not correct."
end

r =3D Integer(Math.log(row) / Math.log(2))
c =3D Integer(Math.log(col) / Math.log(2))
all_rc_orders =3D all_orders(r,c)

row.times do |tb_operation|
col.times do |lr_operation|
all_rc_orders.each do |order|
operations =3D ''
tb_op =3D tb_operation
lr_op =3D lr_operation
(r+c).times do
if (order & 1 =3D=3D 0)
operations +=3D (tb_op & 1 =3D=3D 0) ? 'T' : 'B'
tb_op >>=3D 1
else
operations +=3D (lr_op & 1 =3D=3D 0) ? 'L' : 'R'
lr_op >>=3D 1
end
order >>=3D 1
end
return operations if fold(row, col, operations) =3D=3D result
end
end
end
"No solution."
end

 

[Bill Dolinar]

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_enumeach_slice, 1).to_a
values = values.to_enumeach_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[j] = item + @values[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