Forum: Ruby Grid Folding (#63)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2006-01-20 16:34
(Received via mailing list)
The three rules of Ruby Q.:

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 Q. 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 T. follow the discussion.

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

by Matthew M.

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).
Gregory S. (Guest)
on 2006-01-20 18:38
(Received via mailing list)
On Fri, Jan 20, 2006 at 10:57:03PM +0900, Ruby Q. wrote:
[...]
} 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
Matthew M. (Guest)
on 2006-01-20 18:50
(Received via mailing list)
> 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.
Matthew M. (Guest)
on 2006-01-20 18:53
(Received via mailing list)
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)
Chris Turner (Guest)
on 2006-01-21 21:50
(Received via mailing list)
On 1/20/06, Matthew M. <removed_email_address@domain.invalid> 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. :-)

Chris
Gavin K. (Guest)
on 2006-01-21 21:59
(Received via mailing list)
On Jan 21, 2006, at 12:47 PM, Chris Turner wrote:

> On 1/20/06, Matthew M. <removed_email_address@domain.invalid> 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. :-)

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.
Chris Turner (Guest)
on 2006-01-21 22:15
(Received via mailing list)
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. :-) Oops.
Guest (Guest)
on 2006-01-21 23:56
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. :-) 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. :-)

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!
Vladimir A. (Guest)
on 2006-01-22 16:43
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")
Sander L. (Guest)
on 2006-01-22 19:13
(Received via mailing list)
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 :(
irb(main):001:0> require 'extensions/symbol'
irb(main):002:0> [[1,2,3]].map(&:reverse)
NoMethodError: undefined method `reverse' for 1:Fixnum
Chris Turner (Guest)
on 2006-01-22 19:47
(Received via mailing list)
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
Guest (Guest)
on 2006-01-23 04:57
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
Bob S. (Guest)
on 2006-01-23 06:22
(Received via mailing list)
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!
Mike B. (Guest)
on 2006-01-24 17:39
(Received via mailing list)
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
unknown (Guest)
on 2006-01-24 17:57
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
	"asplake" <removed_email_address@domain.invalid> 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 :-)

> 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
Vladimir A. (Guest)
on 2006-01-24 18:13
(Received via mailing list)
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.
Mike B. (Guest)
on 2006-01-24 18:13
(Received via mailing list)
> 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
Vladimir A. (Guest)
on 2006-01-24 18:16
(Received via mailing list)
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.
Mike B. (Guest)
on 2006-01-24 18:16
(Received via mailing list)
Not 100% surprised, and it's longer than others too.  For the large
(e.g. 1024x1024) runs it's now about twice as fast, just by
preallocating the results array and using 'for' instead of 'each'
loops.  Oh well.  Still the slowest.  Perhaps mine uses less memory ;-)
Vladimir A. (Guest)
on 2006-01-24 18:19
(Received via mailing list)
Excuse me for a dumb question, but how do you preallocate the array?
Mike B. (Guest)
on 2006-01-24 18:19
(Received via mailing list)
with: result = Array.new(orig_width * orig_height)
and if "preallocate" was the wrong word, I apologise!
Vladimir A. (Guest)
on 2006-01-24 18:22
(Received via mailing list)
Thanks. I don't know how to apply it to my code, though. Lets say I
have an array of symbol pairs such as: [[:top, :left], [:bottom,
:left], [:top, :right]] ... ], and there's an N of them.

Replacing "@origin = []" with something like "@origin = Array.new(2*N)"
gives out an error about accessing nil later in the code.
unknown (Guest)
on 2006-01-24 18:25
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
	"Vladimir A." <removed_email_address@domain.invalid> 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][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

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
unknown (Guest)
on 2006-01-24 18:25
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
	"asplake" <removed_email_address@domain.invalid> writes:
>> 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.
>
I don't see a problem, I was just curious how you understand validation
if you get the sizes from the folding instructions, since I'd say any
instruction is valid then. But that's just a question of interpretation
of the task.

Morus
unknown (Guest)
on 2006-01-24 19:01
(Received via mailing list)
In article <removed_email_address@domain.invalid>,
	removed_email_address@domain.invalid (Morus W.) writes:

I did another solution doing an unfold of the final stack.
It's much cleaner than the first one.
Unfortunately it's still pretty slow for large grids.
So I did a third one, based on the second one replacing the calculation
by C. The drawback is that it isn't portable anymore, though it should
run on any unix environment having a gcc compiler ;-)

--- second one ---
#! /usr/bin/ruby

def fold(width, height, cmds)

  size = width * height

  horz = cmds.count("RL")
  vert = cmds.count("BT")
  raise "illegal width" if 2**horz != width
  raise "illegal height" if 2**vert != height

  func = "def unfold(z)\n(x,y,z) = [ 0,0,z ]\n"

  w = 1
  h = 1
  d = size
  cmds.split(//).reverse.each do | dir |
    if dir == 'R'
      func += "(x,z) = (z < #{d/2}) ? [ #{2*w-1}-x, #{d/2-1}-z ] : [ x,
z-#{d/2} ]\n"
      w*=2
    elsif dir == 'L'
      func += "(x,z) = (z < #{d/2}) ? [ #{w-1}-x, #{d/2-1}-z ] : [
x+#{w}, z-#{d/2} ]\n"
      w*=2
    elsif dir == 'B'
      func += "(y,z) = (z < #{d/2}) ? [ #{2*h-1}-y, #{d/2-1}-z ] : [ y,
z-#{d/2} ]\n"
      h*=2
    elsif dir == 'T'
      func += "(y,z) = (z < #{d/2}) ? [ #{h-1}-y, #{d/2-1}-z ] : [
y+#{h}, z-#{d/2} ]\n"
      h*=2
    end
    d/=2
  end
  func += "x + y * #{width} + 1\n"
  func += "end\n"

  eval func

  (0..size-1).collect { | i | unfold(i) }
end

if ARGV[0]
  dirs = ARGV[0]
  width = (ARGV[1] || 16).to_i
  height = (ARGV[2] || width).to_i

  res = fold(width, height, dirs)

  puts res.join(", ")
end


--- third one ---
#! /usr/bin/ruby


def fold(width, height, cmds)

  size = width * height

  horz = cmds.count("RL")
  vert = cmds.count("BT")
  raise "illegal width" if 2**horz != width
  raise "illegal height" if 2**vert != height

  func = "#include <stdio.h>\n#include <stdlib.h>\n"
  func += "int unfold(int z) { \n int x=0; int y=0;\n"

  w = 1
  h = 1
  d = size
  cmds.split(//).reverse.each do | dir |
    if dir == 'R'
      func += "x = (z < #{d/2}) ? #{2*w-1}-x : x;\n"
      func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
      w*=2
    elsif dir == 'L'
      func += "x = (z < #{d/2}) ? #{w-1}-x : x+#{w};\n"
      func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
      w*=2
    elsif dir == 'B'
      func += "y = (z < #{d/2}) ? #{2*h-1}-y : y;\n"
      func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
      h*=2
    elsif dir == 'T'
      func += "y = (z < #{d/2}) ? #{h-1}-y : y+#{h};\n"
      func += "z = (z < #{d/2}) ? #{d/2-1}-z : z-#{d/2};\n"
      h*=2
    end
    d/=2
  end
  func += "return x + y * #{width} + 1; }\n"
  func += "int main(int argc, char**argv) {\n"
  func += "int i=0;\nint max=atoi(argv[1]);for (i=0;i<max;i++) {
printf(\"%d \",unfold(i)); } }\n"

  File.open("unfold.c", "w") do | fh |
    fh.puts func
  end

  `gcc -O2 -o unfold unfold.c`

  IO.popen("./unfold #{size}").readline.split(" ").collect { | i |
i.to_i }
end

if ARGV[0]
  dirs = ARGV[0]
  width = (ARGV[1] || 16).to_i
  height = (ARGV[2] || width).to_i

  res = fold(width, height, dirs)

  puts res.join(", ")
end
Matthew M. (Guest)
on 2006-01-24 19:26
(Received via mailing list)
> 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.  :)  But since this is rubyquiz
and not traffic school, that's cool.
Matthew M. (Guest)
on 2006-01-24 19:32
(Received via mailing list)
On 1/24/06, Vladimir A. <removed_email_address@domain.invalid> wrote:
> 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.

My solution took only 143 seconds to do all the tests...  of course,
my machine is a 3.2GHz P4, so it the solution ain't that fast.
Mike H. (Guest)
on 2006-01-27 03:19
(Received via mailing list)
I was waiting to clean up my solution, but it's Thursday, so here it
is.  It's too late for the summary, I'm just looking to get my first
successful RubyQuiz up.  I also used this as my first TDD "project,"
which explains why it's so verbose in places.  I've also included the
tests, can't hurt.

class String
  def each_char
    for i in 0...length
      yield(self[i,1])
    end
  end
end

class Array
  alias_method :old_eq, :==
  def ==(arg)
    return arg == self if arg.kind_of?(Grid)
    old_eq(arg)
  end
end

class Range
  def middle
    (first+last)/2
  end

  def flip(i)
    last-1-(i-first)
  end

  def flip_doubled(i)
    (last*2)-1-(i-first)
  end
end

module DiscreteMethod
  def make_disc_meth(sym)
    define_method(sym) do |*args|
      temp_var = clone
      temp_var.send(sym.to_s + "!",*args)
      temp_var
    end
  end
end

class Grid
  extend DiscreteMethod
  attr_accessor :size, :rows, :cols, :vert, :cells
  def initialize(n = 0)
    @size = n
    @rows = 0...n
    @cols = 0...n
    @vert = 0...1
    @cells = {}
    init_cells if n > 0
  end

  def init_cells
    num = 1
    for r in 0...size
      for c in 0...size
        @cells[[r,c,0]] = num; num += 1;
      end
    end
  end

  def [](r,c,v)
    @cells[[r,c,v]]
  end

  make_disc_meth "fold"
  def fold!(str)
    if str.length > 1
      str.each_char { |c| fold!(c) }
      return
    end
    raise "bad attempted fold" unless ["R","T","L","B"].include?(str)
    raise "bad attempted fold" if (str == "R" or str == "L") and
cols.first == cols.last-1
    raise "bad attempted fold" if (str == "B" or str == "T") and
rows.first == rows.last-1
    @cells.keys.find_all { |k| k[1] >= cols.middle }.each { |k|
self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == "R"
    @cells.keys.find_all { |k| k[1] < cols.middle }.each { |k|
self[k[0],cols.flip(k[1]),vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == "L"
    @cells.keys.find_all { |k| k[0] >= rows.middle }.each { |k|
self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k)  } if str == "B"
    @cells.keys.find_all { |k| k[0] < rows.middle }.each { |k|
self[rows.flip(k[0]),k[1],vert.flip_doubled(k[2])] = @cells[k];
@cells.delete(k) } if str == "T"
    update_boundaries!(str)
  end

  make_disc_meth "update_boundaries"
  def update_boundaries!(d)
     @vert = (0...vert.last*2)
     @rows = (rows.first...rows.middle) if d == "B"
     @rows = (rows.middle...rows.last) if d == "T"
     @cols = (cols.first...cols.middle) if d == "R"
     @cols = (cols.middle...cols.last) if d == "L"
  end

  def []=(r,c,v,n)
    @cells[[r,c,v]] = n
  end

  def clone
    g = Grid.new
    g.rows,g.cols,g.vert = rows.clone,cols.clone,vert.clone
    @cells.each_key do |k|
      g[k[0],k[1],k[2]] = @cells[k]
    end
    g
  end

  def ==(g)
    return to_a == g if g.kind_of? Array
    return false if @cells.keys.size != g.cells.keys.size
    return false if size != g.size or cols != g.cols or rows != g.rows
or vert != g.vert
    @cells.keys.each { |k| return false if @cells[k] != g.cells[k] }
    true
  end

  def sorted_keys
    @cells.keys.sort { |a,b| x = b[2] <=> a[2]; (x = a[0] <=> b[0]) if
x==0; (x = a[1] <=> b[1]) if x==0; x }
  end

  def to_a
    a = []
    sorted_keys.each { |k| a << @cells[k] }
    a
  end
end

def fold(r,c,str)
  raise "Bad Input Dimensions" if r != c or
![1,2,4,8,16,32,64,128].include?(r)
  g = Grid.new(r)
  g.fold!(str)
  g.to_a
end

-----------

require 'test/unit'
require '../grid.rb'

class TestGridFold < Test::Unit::TestCase
  def setup
    @two = Grid.new(2)
    @two_folded_rb = Grid.new
    @two_folded_rb.rows = (0...1)
    @two_folded_rb.cols = (0...1)
    @two_folded_rb.vert = (0...4)
    @two_folded_rb[0,0,3] = 3
    @two_folded_rb[0,0,2] = 4
    @two_folded_rb[0,0,1] = 2
    @two_folded_rb[0,0,0] = 1
    @st = Grid.new(16)
  end

  def test_size
    assert @two.size == 2
  end

  def test_get
    assert @two[0,0,0] == 1
    assert @two[0,1,0] == 2
    assert @two[1,0,0] == 3
    assert @two[1,1,0] == 4
  end

  def test_out_bounds
    assert @two[2,2,2].nil?
  end

  def test_full_fold
    g = @two.fold("RB")
    assert g == @two_folded_rb,g.to_a
    #assert @two.fold("TL") == [3,1,2,4]
  end

  def test_one_fold
    g = @two.fold("R")
    assert g == [2,4,1,3],g.to_a
    g = g.fold("B")
    assert g == @two_folded_rb
  end

  def test_fold_not_modify
    @two.fold("R")
    test_get
  end

  def test_fold_exc
    assert @two.fold("RB") == @two_folded_rb
  end

  def test_init_boundaries
    assert @two.rows == (0...2)
    assert @two.cols == (0...2)
    assert @two.vert == (0...1)
  end

  def test_boundaries_after_fold
    assert @two.fold("R").cols == (0...1)
    assert @two.fold("L").cols == (1...2)
    assert @two.fold("R").rows == (0...2)
    assert @two.fold("L").rows == (0...2)
  end

  def test_update_boundaries_r
    g = @two.update_boundaries("R")
    assert g.rows == (0...2)
    assert g.cols == (0...1),g.cols
    assert g.vert == (0...2)
  end

  def test_update_boundaries_t
    assert @two.update_boundaries("T").rows == (1...2)
    assert @two.update_boundaries("T").cols == (0...2)
    assert @two.update_boundaries("T").vert == (0...2)
  end

  def test_update_boundaries_l
    g = @two.update_boundaries("L")
    assert g.rows == (0...2)
    assert g.cols == (1...2),g.cols
    assert g.vert == (0...2)
  end

  def test_update_boundaries_ll
    g = @st.update_boundaries("L").update_boundaries("L")
    assert g.rows == (0...16)
    assert g.cols == (12...16),g.cols
    assert g.vert == (0...4)
  end

  def test_update_boundaries_llrbt
    g =
@st.update_boundaries("L").update_boundaries("L").update_boundaries("R").update_boundaries("B").update_boundaries("T")
    assert g.rows == (4...8)
    assert g.cols == (12...14),g.cols
    assert g.vert == (0...32)
  end

  def test_update_boundaries_no_update
    @two.update_boundaries("R")
    assert @two.cols == (0...2)
  end

  def test_update_boundaries_exc_update
    @two.update_boundaries!("R")
    assert @two.cols == (0...1)
  end

  def test_clone
    g = @two.clone
    assert g[0,0,0] == 1
    assert g[1,1,0] == 4
    g[0,0,0] = 9
    assert g[0,0,0] == 9
    assert @two[0,0,0] == 1
  end

  def test_set
    @two[0,0,0] = 9
    assert @two[0,0,0] == 9
  end

  def test_equality_grid
    assert @two == Grid.new(2)
    assert Grid.new(2).fold("R") == Grid.new(2).fold("R")
    assert Grid.new(2).fold("RB") == Grid.new(2).fold("RB")
  end

  def test_equality_array
    assert @two_folded_rb == [3,4,2,1]
  end

  def test_to_a
    a = @two_folded_rb.to_a
    assert a == [3,4,2,1],a
  end


end
This topic is locked and can not be replied to.