Bill Dolinar
1/24/2006 9:18:00 AM
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
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