------extPart_000_0026_01C61F60.9D2384F0
Content-Type: text/plain;
	charsets-ascii"
Content-Transfer-Encoding: 7bit


And here's mine.  I didn't use a grid at all - working it out a cell at a
time.

One key difference is that mine works out the dimensions from the supplied
folds.  It checks that the grid to be square (raises an exception
otherwise), but only to pass what might have been an over-zealous test case.

Regards,
Mike


-----Original Message-----
From: Luke Blanshard [mailto:luke / blanshard.us] 
Sent: 22 January 2006 13:56
To: ruby-talk ML
Subject: [/QUIZ] #63: Grid Folding

Greetings all,

  Attached is my solution.  It uses nested arrays to simulate the 3-d 
grid cells, and adds methods to Array to effect this.  It handles 
arbitrary rectangles of 2**n by 2**m.  The unit tests provided earlier pass.

  I can't help feeling there should be a direct numerical way to 
calculate this sequence.  To study the sequence, I wrote a second 
script, also attached, that prints the bits of the resulting sequence 
from any given rectangle dimensions and list of folds.  (I subtract one 
from the sequence to make it zero-based.)  However, even with a fair 
amount of studying lists of bit patterns I haven't cracked the code.

Luke Blanshard


------extPart_000_0026_01C61F60.9D2384F0
Content-Type: application/octet-stream;
	name3_grid_folding.rb"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename3_grid_folding.rb"

# Fold 1-dimensionally "forward" - i.e. Left to Right or Top to bottom
class ForwardFolder
	def fold1d(position, length, depth, thickness)
if position >= (to_length = length / 2)
		  position -= to_length 
		  depth += thickness
		else
		  position = to_length - position - 1
		  depth = thickness - depth - 1
		end
		[position, to_length, depth, 2*thickness]
	end
end

# Fold 1-dimensionally "backward" - i.e. bottom to top or right to left
class BackwardFolder
	def fold1d(position, length, depth, thickness)
if position >= (to_length = length / 2)
		  position = length - position - 1
		  depth = thickness - depth - 1
		else
		  depth += thickness
		end
		[position, to_length, depth, 2*thickness]
	end
end

# Mixin to make a Forward or Backward folder a Left or Right folder (respectively)
module LeftRightFolder
  def fold(x, y, w, h, depth, thickness)
, w, depth, thickness = fold1d(x, w, depth, thickness)
x, y, w, h, depth, thickness]
  end
end
    
# Mixin to make a Forward or Backward folder a Top or Bottom fold (respectively)
module TopBottomFolder
  def fold(x, y, w, h, depth, thickness)
  	y, h, depth, thickness = fold1d(y, h, depth, thickness)
  	[x, y, w, h, depth, thickness]
  end
end

# The main class
class Fold
ap command letters to a suitable folder object
  FOLDERS = {
		'L' => ForwardFolder.new.extend(LeftRightFolder),
		'R' => BackwardFolder.new.extend(LeftRightFolder),
		'T' => ForwardFolder.new.extend(TopBottomFolder),
		'B' => BackwardFolder.new.extend(TopBottomFolder)
  }
	
	def self.fold(instructions)
    raise("bad instructions") unless instructions.match(/^[LRTB]*$/)

	  folds = instructions.split(//).collect {|i| FOLDERS[i]}
	  
	  # work out the width and height by "unfolding" by the number of Left/Right and Top/Bottom folds respectively
	  orig_width  = 1 << folds.grep(LeftRightFolder).length
	  orig_height = 1 << folds.grep(TopBottomFolder).length
	
	  # and check that they are the same (i.e. that the grid is square (because the spec says so - not that it would break anything)
	  raise("non-square: unequal width (#{orig_width}) and height (#{orig_height}) implied by folds \"#{instructions}\"") unless orig_height == orig_width
	  
	  # Do it - a cell at a time...
	  result = []
	  (0...orig_height).each do |row|
	    (0...orig_width).each do |col|
	    
	      n = row * orig_width + col + 1  # n being the original cell number
	      x, y = col, row
	      w, h = orig_width, orig_height
	      depth = 0
	      thickness = 1
	      
	      # ...and apply the list of folds
			  folds.each do |folder|
	        x, y, w, h, depth, thickness = folder.fold(x, y, w, h, depth, thickness)
	      end
	      
	      result[depth] = n               # record the layer (or depth) that cell n ends up in
	    end
	  end
	  
	  result
	end
end

if __FILE__ == $0
  require 'test/unit'

lass 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.fold(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.fold("TLBLRRTB")
	   end
	
	   def test_invalid
	      assert_raise(RuntimeError) { Fold.fold("LR") }  # too many horz folds
	      assert_raise(RuntimeError) { Fold.fold("TRB") } # too many folds
	      assert_raise(RuntimeError) { Fold.fold("LR") }  # bad input dimensions
	   end
  end
end

------extPart_000_0026_01C61F60.9D2384F0--