From: James Edward Gray II Date: 2006-01-23T03:20:35+09:00 Subject: Fwd: [QUIZ] Grid Folding (#63) --Apple-Mail-1-733028561 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed Begin forwarded message: > From: Aditya Mahajan > Date: January 22, 2006 5:13:03 AM CST > To: Matthew Moss > Cc: james@grayproductions.net > Subject: Re: [QUIZ] Grid Folding (#63) > > Hi Guys, > > This is my first submission to Ruby Quiz. I have solved it in an > obfuscated way of using Arrays and Matrices and moving back and > forth between them. I am pretty sure there is a more elegent > method, but what the heck, my method works :-) Time taken ~ 4hrs. > > The code passes Matthew's tests and also a few that I tried out by > hand. Thanks for the super quiz. > > Aditya > > > <--- On Jan 21, 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) >> >> >> > > -- > ________________________________________________________ > Aditya Mahajan > EECS-Systems 1835 Shirley Lane, #C7 > University of Michigan Ann Arbor, MI-48105 > Ann Arbor MI (734) 262 4008 > http://www.eecs.umich.edu/~adityam > _________________________________________________________ --Apple-Mail-1-733028561 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; x-unix-mode=0666; name="grid.rb" Content-Disposition: attachment; filename=grid.rb #!/usr/bin/ruby=0D =0D require 'Matrix'=0D =0D # Extend Fixnum to have method reverse to avoid unneccessary checking = later=0D class Fixnum=0D def reverse=0D self=0D end=0D end=0D =0D class Grid=0D attr_reader :grid=0D # Assume correct dimensions. The caller method takes care of checking = input =0D # size=0D def initialize (dimension1,dimension2)=0D @grid =3D Matrix.rows((0...dimension2).collect{ |i| =0D ((1+i*dimension1)..(i+1)*dimension1).to_a })=0D end=0D =0D # Main function to be called from outside=0D def apply_fold(string)=0D instructions =3D string.split("")=0D instructions.each do |dir|=0D case dir=0D when "B"=0D fold_bottom=0D when "T"=0D fold_top=0D when "R"=0D fold_right=0D when "L"=0D fold_left=0D end=0D end=0D @grid.to_a.flatten=0D end=0D =0D # Avoid the trouble of flattening each element while folding=0D # Simply flatten after folding=0D def flatten_grid=0D height =3D grid.row_size=0D width =3D grid.column_size=0D for i in 0...height=0D for j in 0...width=0D @grid[i,j].flatten!=0D end=0D end=0D end=0D =0D def fold_top=0D height =3D grid.row_size=0D top_grid =3D (-height/2+1..0).collect do=0D |x| grid.row(-x).to_a.collect{ |y| y.reverse }=0D end=0D bottom_grid =3D (height/2...height).collect{ |x| grid.row(x).to_a }=0D= # p top_grid=0D # p bottom_grid=0D @grid =3D (0...height/2).collect{ |i| top_grid[i].zip bottom_grid[i] = }=0D @grid =3D Matrix.rows(@grid)=0D flatten_grid=0D end=0D =0D def fold_bottom=0D height =3D grid.row_size=0D top_grid =3D (0...height/2).collect{ |x| grid.row(x).to_a }=0D bottom_grid =3D (-height+1..-height/2).collect do |x| =0D grid.row(-x).to_a.collect{ |y| y.reverse }=0D end=0D # p top_grid=0D # p bottom_grid=0D @grid =3D (0...height/2).collect{ |i| bottom_grid[i].zip top_grid[i] = }=0D @grid =3D Matrix.rows(@grid)=0D flatten_grid=0D end=0D =0D def fold_left=0D width =3D grid.column_size=0D left_grid =3D (-width/2+1..0).collect do |x| =0D grid.column(-x).to_a.collect{ |y| y.reverse }=0D end=0D right_grid =3D (width/2...width).collect{ |x| grid.column(x).to_a }=0D= # p left_grid=0D # p right_grid=0D @grid =3D (0...width/2).collect{ |i| left_grid[i].zip right_grid[i] = }=0D @grid =3D Matrix.rows(@grid).transpose=0D flatten_grid=0D end=0D =0D def fold_right=0D width =3D grid.column_size=0D left_grid =3D (0...width/2).collect{ |x| grid.column(x).to_a }=0D right_grid =3D (-width+1..-width/2).collect do |x| =0D grid.column(-x).to_a.collect{ |y| y.reverse}=0D end=0D # p left_grid=0D # p right_grid=0D @grid =3D (0...width/2).collect{ |i| right_grid[i].zip left_grid[i] = }=0D @grid =3D Matrix.rows(@grid).transpose=0D flatten_grid=0D end=0D end=0D =0D # Main function to be called from outside=0D def fold(dim1, dim2, args)=0D raise "bad input dimensions" unless power2?(dim1) && power2?(dim2)=0D raise "too many vertical folds" unless args.split("").find_all{ |x| x = =3D=3D "T" || x =3D=3D "B" }.length =3D=3D power2(dim1)=0D raise "too many horizontal folds" unless args.split("").find_all{ |x| = x =3D=3D "L" || x =3D=3D "R" }.length =3D=3D power2(dim2)=0D grid =3D Grid.new(dim1,dim2)=0D grid.apply_fold(args)=0D end=0D =0D def power2?(dimension)=0D (Math.log(dimension)/Math.log(2)).ceil =3D=3D = (Math.log(dimension)/Math.log(2)).floor=0D end=0D =0D def power2(dimension)=0D (Math.log(dimension)/Math.log(2)).ceil=0D end=0D --Apple-Mail-1-733028561 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed --Apple-Mail-1-733028561--