Asp Forum - [QUIZ][SOLUTION] Grid Folding (#63

horndude77

1/23/2006 2:57:00 AM

I didn't use multidimensional arrays for my solution. I keep track of
where each number is (row, col, position in paper stack) during the
folds and just insert it directly into the final array. The folding code
isn't as succinct as I'd like it to be with quite a bit of duplication.
Any thoughts on that?

The unfolding function is just magic. I know that's bad, but I'll give
my theory as to why it works. So my original plan was to start in the
middle and look at the numbers on the joint of the fold. Check if
they're in the same row or column to determine if it was a vertical or
horizontal fold and check which number is bigger to determine if it
which side was folded onto the other. This mostly works, but breaks if
there are two folds of the same orientation in a row (ie horizontal
folds: RR, RL, LL, LR). If you look at the end I have it rerun unfold on
the stack generated from folding the new string. This creates the
correct string. As an example lets say we have a 4x1 paper. The valid
folds are:

cmds => stack => unfold(stack)
RR => 2341 => RL
RL => 1432 => RR
LL => 3214 => LR
RL => 4132 => LL

So in this little set we can see that there are pairs of inputs that
give each other as outputs to the unfold section. This happens to also
work for larger paper stacks. I haven't proved this, but I added this to
the unit tests to make sure:

def random_string(len)
vert_folds = ['T', 'B']
horiz_folds = ['L', 'R']
folds = []
(len/2).times do folds << vert_folds[rand(2)] end
(len/2).times do folds << horiz_folds[rand(2)] end
folds.sort{rand}.join
end

def test_random_unfold
100.times do |i|
side_pow = rand(7)+1
side = 2**side_pow
s = random_string(side_pow*2)
assert_equal s, unfold(fold(s, side))
end
end

No failures yet. I'd bet that there is a simple way to fix the
algorithm, but I need to just sit down an figure it out. I can probably
just be able to do a global replace on the string instead of rerunning
fold and unfold. Well, thanks for the quiz!

-----Horndude77

#!/usr/bin/ruby -w

module Math
def Math.lg(n) log(n)/log(2) end
end

def fold(s, n)
#validate inputs
pow = Math.lg(n)
raise "Bad dimension" if pow != pow.round
raise "Bad string length" if s.length != (pow*2).round
horiz, vert = 0, 0
s.downcase.split('').each do |orient|
case orient
when 'r', 'l'
vert += 1
when 't', 'b'
horiz += 1
end
end
raise "Unbalanced folds" if horiz != vert

#do the folding
max = n**2
stack = Array.new(max)
1.upto(max) do |i|
row, col, pos, height = (i-1)/n, (i-1)%n, 0, 1
x, y = n, n
s.each_byte do |move|
pos += height
height *= 2
case move
when ?L
x /= 2
if col < x then
col = x-col-1
pos = height - pos - 1
else
col -= x
end
when ?R
x /= 2
if col >= x then
col = x*2 - col - 1
pos = height - pos - 1
end
when ?T
y /= 2
if row < y then
row = y-row-1
pos = height - pos - 1
else
row -= y
end
when ?B
y /= 2
if row >= y then
row = y*2 - row - 1
pos = height - pos - 1
end
end
end
stack[pos] = i
end
stack
end

def same_row?(a,b,n)
(a-1)/n == (b-1)/n
end

def same_col?(a,b,n)
(a-1)%n == (b-1)%n
end

def unfold(stack, recurse = :yes)
pow = Math.lg(stack.length)
raise "Bad dimension" unless pow == pow.round && (pow.round % 2) ==
0
side = Math.sqrt(stack.length).round
s = ""
while stack.length > 1
half = stack.length/2
a, b = stack[half-1], stack[half]
if same_row? a, b, side then
if a<b then s << 'L' else s << 'R' end
elsif same_col? a, b, side then
if a<b then s << 'T' else s << 'B' end
else
raise "Stack not generated from folding"
end
stack = stack[half, half]
end

s.reverse!
if(recurse == :yes) then
unfold(fold(s, side), :no)
else
s
end
end

--
Posted via http://www.ruby-....

comp.lang.ruby

[QUIZ][SOLUTION] Grid Folding (#63

horndude77

x Login to ForumsZone