(NOTE: The 16x16 test below is the result of my own solution. I'm
fairly certain it's correct, but not 100%.  So if you run this and
pass the other two tests but fail the 16x16 test, I'd be interested to
see your output and between us figure out what the expected solution
is.)

Oh, and if you have more tests, feel free to share.

require 'test/unit'
require 'test/unit/ui/console/testrunner'

class FoldTest < Test::Unit::TestCase
   def test_2x2
      folds = {"TR" => [4, 2, 1, 3],
               "BR" => [2, 4, 3, 1],
               "TL" => [3, 1, 2, 4],
               "BL" => [1, 3, 4, 2],
               "RT" => [1, 2, 4, 3],
               "RB" => [3, 4, 2, 1],
               "LT" => [2, 1, 3, 4],
               "LB" => [4, 3, 1, 2]}

      folds.each do |cmds,xpct|
         assert_equal xpct, fold(2, 2, cmds)
      end
   end

   def test_16x16
      xpct = [189,  77,  68, 180, 196,  52,  61, 205,
              204,  60,  53, 197, 181,  69,  76, 188,
              185,  73 , 72, 184, 200,  56,  57, 201,
              208,  64,  49, 193, 177,  65,  80, 192,
              191,  79,  66, 178, 194,  50,  63, 207,
              202,  58,  55, 199, 183,  71,  74, 186,
              187,  75,  70, 182, 198,  54,  59, 203,
              206,  62,  51, 195, 179,  67,  78, 190,
              142, 126, 115, 131, 243,   3,  14, 254,
              251,  11,   6, 246, 134, 118, 123, 139,
              138, 122, 119, 135, 247,   7,  10, 250,
              255,  15,   2, 242, 130, 114, 127, 143,
              144, 128, 113, 129, 241,   1,  16, 256,
              249,   9,   8, 248, 136, 120, 121, 137,
              140, 124, 117, 133, 245,   5,  12, 252,
              253,  13,   4, 244, 132, 116, 125, 141,
              157, 109, 100, 148, 228,  20,  29, 237,
              236,  28,  21, 229, 149, 101, 108, 156,
              153, 105, 104, 152, 232,  24,  25, 233,
              240,  32,  17, 225, 145,  97, 112, 160,
              159, 111,  98, 146, 226,  18,  31, 239,
              234,  26,  23, 231, 151, 103, 106, 154,
              155, 107, 102, 150, 230,  22,  27, 235,
              238,  30,  19, 227, 147,  99, 110, 158,
              174,  94,  83, 163, 211,  35,  46, 222,
              219,  43,  38, 214, 166,  86,  91, 171,
              170,  90,  87, 167, 215,  39,  42, 218,
              223,  47,  34, 210, 162,  82,  95, 175,
              176,  96,  81, 161, 209,  33,  48, 224,
              217,  41,  40, 216, 168,  88,  89, 169,
              172,  92,  85, 165, 213,  37,  44, 220,
              221,  45,  36, 212, 164,  84,  93, 173]
      assert_equal xpct, fold(16, 16, "TLBLRRTB")
   end

   def test_invalid
      assert_raise(RuntimeError) { fold(2, 2, "LR") } # too many horz folds
      assert_raise(RuntimeError) { fold(2, 2, "TRB") } # too many folds
      assert_raise(RuntimeError) { fold(3, 2, "LR") } # bad input dimensions
   end

end

BTW it's not hard to work out (and - hint to Chris - validate) the grid
dimensions from the folds so my function takes just the one argument.

Regards, Mike

On 1/21/06, Gavin Kistner <ga...@refinery.com> wrote:

This was a good task, and somewhat hard for me too (I'm a total newbie
after all :-). Maybe that's because I didn't find a simple solution and
was forced to just model the situation roughly, without any hacks.

Thanks, Matt!

But doesn't that imply that any input is valid? E.g. LR is ok for
a 4x1 sheet (giving 4,1,2,3).
Or did you introduce a rule that the input has to be a square?

I suggest other tests based on my solution
   def test_1024_1024
     xpct = 'b5319b3045af0ab0f931dacca739d90a'
     md5 = MD5.new(fold(1024,1024,'TRTRTRTRTRTRTRTRTRTR').join(' '))
     assert_equal xpct, md5.hexdigest
   end
   def test_2048_2048
     xpct = '8e046199eee20b097e4948a5ea503516'
     md5 = MD5.new(fold(2048,2048,'TRTRTRTRTRTRTRTRTRTRTR').join(' '))
     assert_equal xpct, md5.hexdigest
   end
(you need to add a 'require "md5"' to the test skript, the array itself
is a bit lengthy ;-))

For larger sheets my system (512M) starts to swap too much.
Probably I should have used a singe array instead of three dimensional
arrays of arrays...

class SquareSheet
  def initialize(dim_power)
    @dim = @cols = @rows = 2**dim_power
    @power = dim_power
    @order = [] #desired number order
    @layers = [[0,0]] #array of layer coordinates
    #(relative to the top left corner of the whole sheet)
    @origin = [[:top, :left]] #array of layer spatial orientations
  end

  def opposite(dir)
    case dir
      when :bottom: :top
      when :top: :bottom
      when :left: :right
      when :right: :left
    end
  end

  def fold(sequence)
    raise "Invalid sequence" \
        unless (sequence.count("TB") == @power) && \
               (sequence.count("LR") == @power)
    sequence.split(//).each do |char|
      len = @layers.length
      case char
      when "T", "B":
        @rows /= 2
        for i in 0..len-1 do #in such cases 'for' perfoms better than
'each'
          #calculate new orientations and coordinates of each layer
          @origin[2*len-i-1] = [opposite((@origin[i])[0]),
(@origin[i])[1]]
          @layers[2*len-i-1] = [(@layers[i])[0], (@layers[i])[1]]
          if (@origin[i])[0] == :bottom: (@layers[2*len-i-1])[0] +=
@rows
          else (@layers[i])[0] += @rows; end
        end
        @layers.reverse! if char=="B"
      when "L", "R":
        @cols /= 2
        for i in 0..len-1 do
          @origin[2*len-i-1] = [(@origin[i])[0],
opposite((@origin[i])[1])]
          @layers[2*len-i-1] = [(@layers[i])[0], (@layers[i])[1]]
          if (@origin[i])[1] == :right: (@layers[2*len-i-1])[1] += @cols
          else (@layers[i])[1] += @cols; end
        end
        @layers.reverse! if char=="R"
      end
    end
    @layers.each {|coord| @order << coord[0]*@dim+coord[1]+1}
    return @order.reverse
  end
end

#example usage:
#sheet = SquareSheet.new(4)  #creates 2**4 x 2**4 sheet
#p sheet.fold("TLBLRRTB")

class Array
  def reverse_each
    map {|x| x.reverse}
  end
end

def fold(str,w=8,h=8)
  grid = Array.new(h) {|y| Array.new(w) {|x| [w*y+x+1] }  }
  str.each_byte {|c|
    grid = case c
          when ?R then rightFold(grid)
          when ?L then rightFold(grid.reverse_each).reverse_each
          when ?B then rightFold(grid.transpose).transpose
          when ?T then rightFold(grid.reverse.transpose).transpose.reverse
        end
  }
  raise "invalid folding instructions" unless grid.length == 1 &&
grid[0].length == 1
  return grid[0][0]
end

def rightFold(grid)
  grid.map { |row|
    for ix in 0...row.length/2
          row[ix] = row[-ix-1].reverse + row[ix]
        end
    row[0...row.length/2]
  }
end

p fold("RB",2,2)
p fold("TLRBB",4,8)
p fold("TLBLRRTB",16,16)

Pretty slow I guess.
So I redid that using a single array instead of arrays of arrays of arrays.
I'm still accessing each cell indidually. But that turned out to be even
slower (I used a Array3d class and the additional method lookup is obviously
too expensive, especially since I access each point individually).

So here's my solution:

#! /usr/bin/ruby

class Sheet

  attr_reader :width, :height, :depth

  def check(dim)
    n = Math.log(dim)/Math.log(2) # ' /x
    if n != n.to_i
           raise "dimension must be power of 2"
       end
  end
  def initialize(width, height)
    check(width)
    check(height)
    sheet = []
    0.upto(height-1) do | y |
      sheet[y] = []
      0.upto(width-1) do | x |
        sheet[y][x] = [ width*y + x ]
      end
    end
    set_sheet(sheet)
  end

  def set_sheet(sheet)
    @sheet = sheet
    @width = sheet[0].size
    @height = sheet.size
    @depth = sheet[0][0].size
  end

  def output()
    0.upto( height-1 ) do | y |
      0.upto( width-1 ) do | x |
        (depth-1).downto( 0 ) do | z |
          print "%3d " % (@sheet[y][x][z]+1)
        end
        print "    "
      end
      puts ""
    end
    puts ""
  end

  def result
    @sheet[0][0].reverse.collect { | i | i+1 }
  end

  # ok, here comes the ugly part...
  # for each folding direction a new (stacked) sheet is calculated
  def fold(dir)
    new_sheet = []
    if dir == "T"
      s2 = height/2 # i'd really liked to know why xemacs has problems with foo/2; probably it's confused with a regex
      raise "cannot fold" if s2 == 0
      0.upto( s2-1 ) do | y |
        new_sheet[y] = @sheet[y + s2]
        0.upto( width-1 ) do | x |
          0.upto( depth-1 ) do | z |
            new_sheet[y][x][depth+depth-1-z] = @sheet[s2-1-y][x][z]
          end
        end
      end
    elsif dir == "B"
      s2 = height/2 #'/x
      raise "cannot fold" if s2 == 0
      0.upto( s2-1 ) do | y |
        new_sheet[y] = @sheet[y]
        0.upto( width-1 ) do | x |
          0.upto(depth-1) do | z |
            new_sheet[y][x][depth+depth-1-z] = @sheet[s2+s2-1-y][x][z]
          end
        end
      end
    elsif dir == "L"
      s2 = width/2 #'/x
      raise "cannot fold" if s2 == 0
      0.upto( height-1 ) do | y |
        new_sheet[y] ||= []
        0.upto( s2-1 ) do | x |
          new_sheet[y][x] ||= []
          0.upto( depth-1 ) do | z |
            new_sheet[y][x][z] = @sheet[y][x+s2][z]
            new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2-1-x][z]
          end
        end
      end
    elsif dir == "R"
      s2 = width/2 #'/x
      raise "cannot fold" if s2 == 0
      0.upto( height-1 ) do | y |
        new_sheet[y] ||= []
        0.upto( s2-1 ) do | x |
          new_sheet[y][x] ||= []
          0.upto( depth-1 ) do | z |
            new_sheet[y][x][z] = @sheet[y][x][z]
            new_sheet[y][x][depth+depth-1-z] = @sheet[y][s2+s2-1-x][z]
          end
        end
      end
    else
      raise "unknown edge #{dir}"
    end
    set_sheet(new_sheet)
  end

  def folds(dirs)
    dirs.split(//).each do | dir |
      fold(dir)
    end
  end

end

def fold(width, height, cmds)
  sheet = Sheet.new(width, height)
  sheet.folds(cmds)
  raise "to few folds..." if sheet.width > 1 || sheet.height > 1
  return sheet.result
end

Chris Turner

# folding.rb --------------------------------------------------------------------------- ------------------------------

# A few helper methods

def try
  begin
    yield
  rescue
  end
end

class Object
  def deep_dup
    Marshal::load(Marshal.dump(self))
  end
end

module Math
  def Math.log2(num)
    Math.log(num) / Math.log(2)
  end
end

class Fixnum
  def power_of_2?
    power_of_two = 2
    begin
      return true if power_of_two == self
    end while((power_of_two = power_of_two*2) <= self)
    false
  end
end

# First part of solution (plus first extra credit)
class Paper
  attr_reader :paper
  def initialize(size=16)
    raise "Paper size must be power of 2" unless size.power_of_2?
    @paper = []
    (1..size).each do |h|
      @paper.push((((h-1)*size)+1..(((h-1)*size)+size)).to_a)
      @paper[-1].map! {|x| [x]}
    end
    @size = size
    self
  end

  def fold(commands)
    size = commands.size
    folds_req = Math.log2(@size).to_i*2
    raise "Need #{folds_req-size} more folds" if folds_req > size
    raise "Have too many folds (by #{size-folds_req})" if folds_req < size

    directions = parse_fold_commands(commands)
    directions.each do |direction|
      send(direction)
    end
    @paper[0][0]
  end

  def fold_bottom
    fold_vert(false)
  end

  def fold_top
    fold_vert(true)
  end

  def fold_left
    fold_horiz(true)
  end

  def fold_right
    fold_horiz(false)
  end

private
  def parse_fold_commands(commands)
    commands.split("").map do |d|
      case d.downcase
      when "r"
        :fold_right
      when "l"
        :fold_left
      when "t"
        :fold_top
      when "b"
        :fold_bottom
      else
        raise "Invalid command: #{d}"
      end
    end
  end

  def fold_two_halves(new_half, old_half)
    new_half.each_with_index do |new_row, r_index|
      old_row = old_half[r_index]
      new_row.each_with_index do |new_col, c_index|
        old_col = old_row[c_index]
        new_col.unshift(old_col.reverse).flatten!
      end
    end
  end

  def fold_vert(top_to_bottom)
    check_foldable(:v)
    top_half, bottom_half = get_top_and_bottom
    new_half, old_half = if top_to_bottom
                           [bottom_half, top_half]
                         else
                           [top_half, bottom_half]
                         end
    old_half = old_half.reverse
    fold_two_halves(new_half, old_half)
    (@paper.size/2).times do
      if top_to_bottom
        @paper.shift
      else
        @paper.pop
      end
    end
    self
  end

  def fold_horiz(left_to_right)
    check_foldable(:h)
    left_half, right_half = get_left_and_right
    new_half, old_half = if left_to_right
                           [right_half, left_half]
                         else
                           [left_half, right_half]
                         end
    old_half = old_half.map { |x| x.reverse }
    fold_two_halves(new_half, old_half)
    @paper.each do |row|
      (row.size/2).times do
        if left_to_right
          row.shift
        else
          row.pop
        end
      end
    end
    self
  end

  def get_top_and_bottom
    new_size = @paper.size/2
    [@paper[0,new_size], @paper[new_size,new_size]]
  end

  def get_left_and_right
    new_size = @paper[0].size/2
    [@paper.map {|x| x[0,new_size]}, @paper.map {|x| x[new_size,new_size]}]
  end

  def check_foldable(direction)
    if (@paper.size % 2 != 0) || (@paper[0].size % 2 != 0)
      raise "Must be foldable" if @paper.size != 1 && @paper[0].size != 1
    end

    if direction == :v
      raise "Can't fold this direction" if @paper.size == 1
    elsif direction == :h
      raise "Can't fold this direction" if @paper[0].size == 1
    end
  end
end

def fold(command, size=16)
  Paper.new(size).fold(command)
end

if __FILE__ == $0
  paper_size = ARGV[0] || 16
  p fold(STDIN.gets.chomp, paper_size.to_i)
end

#
# Begin extra extra
credit--------------------------------------------------------------------- --------------
#
class Paper
  def unfold(commands)
    directions = parse_unfold_commands(commands)
    directions.each do |direction|
      send(direction)
    end
    self
  end

  def reset_to(new_paper)
    @paper = new_paper
    self
  end

  def at_start?
    if @paper.size == @size and @paper[0].size == @size
      catch(:not_correct) do
        (0..@size-1).each do |row|
          (0..@size-1).each do |col|
            throw :not_correct if(@paper[row][col][0] != (row*@size)+col+1)
          end
        end
        return true
      end
      false
    end
  end

  def unfold_to_bottom
    check_unfoldable(:v)
    @paper.reverse.each do |row|
      new_row = []
      row.each do |col|
        new_col = []
        (col.size/2).times { new_col.unshift(col.shift) }
        new_row.push(new_col)
      end
      @paper.push(new_row)
    end
    self
  end

  def unfold_to_top
    check_unfoldable(:v)
    me = @paper.dup
    me.each do |row|
      new_row = []
      row.each do |col|
        new_col = []
        (col.size/2).times { new_col.unshift(col.shift) }
        new_row.push(new_col)
      end
      @paper.unshift(new_row)
    end
    self
  end

  def unfold_to_left
    check_unfoldable(:h)
    @paper.each do |row|
      row_dup = row.dup
      row_dup.each do |col|
        new_col = []
        (col.size/2).times { new_col.unshift(col.shift) }
        row.unshift(new_col)
      end
    end
    self
  end

  def unfold_to_right
    check_unfoldable(:h)
    @paper.each do |row|
      row.reverse.each do |col|
        new_col = []
        (col.size/2).times { new_col.unshift(col.shift) }
        row.push(new_col)
      end
    end
    self
  end

private
  def parse_unfold_commands(commands)
    commands.split("").map do |d|
      case d.downcase
      when "r"
        :unfold_to_right
      when "l"
        :unfold_to_left
      when "t"
        :unfold_to_top
      when "b"
        :unfold_to_bottom
      else
        raise "Invalid command: #{d}"
      end
    end
  end

  def check_unfoldable(direction)
    if (@paper.size % 2 != 0) || (@paper[0].size % 2 != 0)
      raise "Must be foldable" if @paper.size != 1 && @paper[0].size != 1
    end

    raise "Already unfolded" if (@paper[0][0].size == 1)
  end
end

def check_fold(ary)
  raise "Invalid solution" unless ary.size.power_of_2?
  answer_size = Math.sqrt(ary.size).to_i
  paper = Paper.new(answer_size).reset_to([[ary.deep_dup]])
  try_all(paper, [""])
end

def try_all(start, directions)
  n = []
  directions.each do |sol|
    new_sol = start.deep_dup.unfold(sol)
    ufl = ufr = uft = ufb = nil

    try { ufl = new_sol.deep_dup.unfold_to_left }
    try { ufr = new_sol.deep_dup.unfold_to_right }
    try { uft = new_sol.deep_dup.unfold_to_top }
    try { ufb = new_sol.deep_dup.unfold_to_bottom }

    return (sol + "l").reverse if ufl and ufl.at_start?
    return (sol + "r").reverse if ufr and ufr.at_start?
    return (sol + "t").reverse if uft and uft.at_start?
    return (sol + "b").reverse if ufb and ufb.at_start?

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

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

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

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

#========================================================================#

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

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

On 1/23/06, David Tran <email55...@gmail.com> wrote: