[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: [QUIZ] Grid Folding (#63

matthew.moss.coder

1/20/2006 4:16:00 PM

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)
20 Answers

Chris Turner

1/21/2006 7:48:00 PM

0

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

asplake

1/21/2006 7:51:00 PM

0

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)

Gavin Kistner

1/21/2006 7:59:00 PM

0

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.

Chris Turner

1/21/2006 8:12:00 PM

0

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

morus.walter

1/21/2006 9:49:00 PM

0

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

Vladimir Agafonkin

1/21/2006 9:57:00 PM

0

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!

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

Vladimir Agafonkin

1/22/2006 2:44:00 PM

0

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

Vladimir Agafonkin

1/22/2006 3:13:00 PM

0

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.

asplake

1/22/2006 3:22:00 PM

0

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

1/22/2006 3:29:00 PM

0

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.