From: horndude77@...
Date: 2006-01-23T11:57:18+09:00
Subject: [QUIZ][SOLUTION] Grid Folding (#63)

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-forum.com/.