[QUIZ] Grid Folding (#63)

ruby-talk
1

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Matthew Moss

You have a square sheet of grid paper, 16 cells across by 16 down. A number is
written in each cell, starting at 1 in the upper-left corner, going across each
line then down the paper, ending with 256 in the lower-right corner.

Your task is write a Ruby function to fold the paper in half repeatedly (along
the horizontal or vertical middle), until you are left with a single cell, 256
layers thick, and report back on the order of those layers, top to bottom.

The input to the function is a string containing the characters "T" (the top
edge folded down to the bottom edge), "B" (bottom up to top), "R" (right to
left) and "L" (left to right). Not every combination of those will be valid, so
make sure you verify your input. Output will be an Array of Integers from 1 to
256, arranged in the top-to-bottom layer order after all folds are done.

To help clarify, here's a 2x2 example.

  +-+-+
  >1|2|
  +-+-+
  >3|4|
  +-+-+
  
  fold("RB") => [3, 4, 2, 1]
  fold("TL") => [3, 1, 2, 4]
  fold("LR") => raise exception for invalid input

Extra credit: Make your fold function take an additional input parameter(s),
the dimensions of the paper; dimensions should be power-of-2 in order to fold
down to one cell.

Extra extra credit: Write a method check_fold() that takes the resulting Array
of Integers from the quiz and returns the transformation String argument (i.e.
fold(check_fold(final_order)) == final_order).

2

[...]
} The input to the function is a string containing the characters "T" (the
} top edge folded down to the bottom edge), "B" (bottom up to top), "R"
} (right to left) and "L" (left to right). Not every combination of those
} will be valid, so make sure you verify your input.
[...]
} To help clarify, here's a 2x2 example.
}
} +-+-+
} |1|2|
} +-+-+
} |3|4|
} +-+-+
}
} fold("RB") => [3, 4, 2, 1]
} fold("TL") => [3, 1, 2, 4]
} fold("LR") => raise exception for invalid input

Assuming it is only composed of [LRTB], is there any way in which the
string can be invalid other than too many folds in a particular dimension?

--Greg

···

On Fri, Jan 20, 2006 at 10:57:03PM +0900, Ruby Quiz wrote:

3

The first extra credit (handling dimensions other than 16x16) is
pretty darn easy, so you may want to start out on a 2x2 to get yer
basics working and move up. With that in mind, here are a few tests
to help verify your work. The test_2x2 tests all possible folding
combinations.

(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

Test::Unit::UI::Console::TestRunner.run(FoldTest)

4

here is my solution, it uses a 3d array to keep track of the stack of
numbers in every location.

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)

i tried to use map(&:reverse) for the reverse_each function but that
doesn't seem to work :frowning:
irb(main):001:0> require 'extensions/symbol'
irb(main):002:0> [[1,2,3]].map(&:reverse)
NoMethodError: undefined method `reverse' for 1:Fixnum

5

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

6

My solution is at http://users.adelphia.net/~showaltb/rubyquiz/63/fold.rb, made without peeking at other solutions.

I only did the first extra credit. The extra extra credit looks hard!

7

Assuming it is only composed of [LRTB], is there any way in which the
string can be invalid other than too many folds in a particular dimension?

Yes... too few folds. The 16x16 (or MxN) paper should be reduced via
folding to a 1x1 stack. Knowing that the input dimensions should be
powers of 2, you can determine the exact number of folds. If the
paper is 16 wide, there should be exactly log2(16) == 4 horizontal
folds.

8

Is this right? I was under the impression that the above fold string
is invalid. You shouldn't be able to fold "RR" or "TB", as you must
always fold in half. My solution, at least, tells me that. :slight_smile:

Chris

···

On 1/20/06, Matthew Moss <matthew.moss.coder@gmail.com> wrote:

   def test_16x16
      # ...
      assert_equal xpct, fold(16, 16, "TLBLRRTB")
   end

9

Here's my newbie solution:

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")

···

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

10

Here's my (first ever) solution. For the extra-extra credit, my
sincere thanks go out to Tristan Allwood, who's solution to the
Numeric Maze I used to check_fold. It is incredibly slow, as it has to
try every possible unfold, but it ends up working.

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?

    n << (sol + "l") if ufl
    n << (sol + "r") if ufr
    n << (sol + "t") if uft
    n << (sol + "b") if ufb
  end
  try_all(start, n) if directions.size != 0
end

11

You can fold a 4x8 sheet of paper in half four ways. Two of them produce a dimensions 2x8, and two of them produce dimensions 4x4. You seem to imply that 'folding in half' means always produce a square result, unless the paper is already square.

···

On Jan 21, 2006, at 12:47 PM, Chris Turner wrote:

On 1/20/06, Matthew Moss <matthew.moss.coder@gmail.com> wrote:

   def test_16x16
      # ...
      assert_equal xpct, fold(16, 16, "TLBLRRTB")
   end

Is this right? I was under the impression that the above fold string
is invalid. You shouldn't be able to fold "RR" or "TB", as you must
always fold in half. My solution, at least, tells me that. :slight_smile:

12

Matthew, thank you for sharing your results (and in the form of test
cases). Pleased to report that mine are identical (and pass!).

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

Matthew Moss wrote:

···

The first extra credit (handling dimensions other than 16x16) is
pretty darn easy, so you may want to start out on a 2x2 to get yer
basics working and move up. With that in mind, here are a few tests
to help verify your work. The test_2x2 tests all possible folding
combinations.

(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

Test::Unit::UI::Console::TestRunner.run(FoldTest)

13

That's how I read it. Looking back at the requirements, however, I now
see that the reason "LR" in a 2x2 paper is invalid is for a completely
different reason. :slight_smile: Oops.

···

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

On Jan 21, 2006, at 12:47 PM, Chris Turner wrote:

> On 1/20/06, Matthew Moss <matthew.moss.coder@gmail.com> wrote:
>> def test_16x16
>> # ...
>> assert_equal xpct, fold(16, 16, "TLBLRRTB")
>> end
>
> Is this right? I was under the impression that the above fold string
> is invalid. You shouldn't be able to fold "RR" or "TB", as you must
> always fold in half. My solution, at least, tells me that. :slight_smile:

You can fold a 4x8 sheet of paper in half four ways. Two of them
produce a dimensions 2x8, and two of them produce dimensions 4x4.
You seem to imply that 'folding in half' means always produce a
square result, unless the paper is already square.

--
Check out my brand spankin' new website at bestfriendchris.com

14

In article <1137873033.046262.256300@g49g2000cwa.googlegroups.com>,
  "asplake" <mjb@asplake.co.uk> writes:

Matthew, thank you for sharing your results (and in the form of test
cases). Pleased to report that mine are identical (and pass!).

me too :slight_smile:

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.

Good hint.

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...

Morus

15

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.

Well, sure... That's like setting the speed limit to 300mph and
suddenly there are no more speeders. :slight_smile: But since this is rubyquiz
and not traffic school, that's cool.

16

Chris Turner wrote:

That's how I read it. Looking back at the requirements, however, I now
see that the reason "LR" in a 2x2 paper is invalid is for a completely
different reason. :slight_smile: Oops.

I wrote a solution for this quiz yesterday (this will be my first
submission, by the way) and can assure everyone that the tests provided
by Matthew are 100% correct, as I have the same results. :slight_smile:

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!

···

--
Posted via http://www.ruby-forum.com/\.

17

Thanks for the test, passed.

"Finished in 182.372 seconds." - quite long for my 2Ghz P4. I wonder
how much it takes to pass the test for the other participants.

18

Or did you introduce a rule that the input has to be a square?

Sorry, I missed this earlier, but as per my submission a few minutes
ago I raise an exception if it's non-square, but only to pass the unit
tests. Otherwise I see no problem with this.

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...

Very interesting to see other solutions. So far I seem to be the only
one not to have modelled the grid explicitly, allocating an array only
for the output. Tried 1024x1024 just now (took 4 minutes - how about
you?) and I'll give your tests a try. Mine seems to be the most
verbose though...

Mike Burrows

19

Mike, you have an interesting concept for this quiz, but the script is
very slow (3 times slower than the nearest neighbour) - I just tested
it on my machine along with others.

20

In article <1137942795.627040.75460@g43g2000cwa.googlegroups.com>,
  "Vladimir Agafonkin" <agafonkin@gmail.com> writes:

Thanks for the test, passed.

"Finished in 182.372 seconds." - quite long for my 2Ghz P4. I wonder
how much it takes to pass the test for the other participants.

502.175 (~90 for the 1024x1024 and 411 for the 2048x2048)
on a AMD Athlon XP 1600+ (1400 MHz).

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] = [ 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][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][depth+depth-1-z] = @sheet[s2-1-y][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][depth+depth-1-z] = @sheet[s2+s2-1-y][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] ||=
          0.upto( depth-1 ) do | z |
            new_sheet[y][z] = @sheet[y][x+s2][z]
            new_sheet[y][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] ||=
          0.upto( depth-1 ) do | z |
            new_sheet[y][z] = @sheet[y][z]
            new_sheet[y][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

if ARGV[0]
  cmds = ARGV[0]
  width = (ARGV[1] || 16).to_i
  height = (ARGV[2] || width).to_i
  digits = (Math.log(width*height)/Math.log(10)).ceil
  puts fold(width, height, cmds).collect { | i | "%#{digits}d" % i }.join(", ")
end