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

Discussion in 'Ruby' started by horndude77@gmail.com, Jan 23, 2006.

  1. Guest

    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/.
    , Jan 23, 2006
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Tran
    Replies:
    9
    Views:
    186
    David Tran
    Jan 21, 2005
  2. Luke Blanshard

    [/QUIZ] #63: Grid Folding

    Luke Blanshard, Jan 22, 2006, in forum: Ruby
    Replies:
    15
    Views:
    231
    Luke Blanshard
    Jan 25, 2006
  3. David Tran
    Replies:
    3
    Views:
    168
    Bill Dolinar
    Jan 24, 2006
  4. Matthew Moss

    [QUIZ.SUMMARY] Grid Folding (#63)

    Matthew Moss, Jan 26, 2006, in forum: Ruby
    Replies:
    3
    Views:
    144
    Morus Walter
    Jan 27, 2006
  5. David Tran
    Replies:
    2
    Views:
    116
    Morus Walter
    Jan 28, 2006
Loading...

Share This Page