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

on 2006-01-20 15:34

on 2006-01-20 17:38

On Fri, Jan 20, 2006 at 10:57:03PM +0900, Ruby Quiz 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

on 2006-01-20 17:50

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

on 2006-01-20 17:53

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)

on 2006-01-21 20:50

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. :-) Chris

on 2006-01-21 20:59

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. :-) 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 2006-01-21 21:15

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.

on 2006-01-21 22: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!

on 2006-01-22 15: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")

on 2006-01-22 18:13

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

on 2006-01-22 18:47

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

on 2006-01-23 03: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

on 2006-01-23 05:22

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!

on 2006-01-24 16:39

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

on 2006-01-24 16:57

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

on 2006-01-24 17:13

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.

on 2006-01-24 17:13

> 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

on 2006-01-24 17:16

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.

on 2006-01-24 17:16

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

on 2006-01-24 17:19

Excuse me for a dumb question, but how do you preallocate the array?

on 2006-01-24 17:19

with: result = Array.new(orig_width * orig_height) and if "preallocate" was the wrong word, I apologise!

on 2006-01-24 17:22

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.

on 2006-01-24 17:25

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][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

on 2006-01-24 17:25

In article <1137943343.626652.112980@g47g2000cwa.googlegroups.com>, "asplake" <mjb@asplake.co.uk> 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

on 2006-01-24 18:01

In article <2orca3-pk3.ln1@morus.walter.news.arcor.de>, morus.walter@gmail.com (Morus Walter) 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

on 2006-01-24 18:26

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

on 2006-01-24 18:32

On 1/24/06, Vladimir Agafonkin <agafonkin@gmail.com> 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.

on 2006-01-27 02:19

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