* set eol-style.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13944 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 564 insertions, 564 deletions

diff --git a/benchmark/bm_so_meteor_contest.rb b/benchmark/bm_so_meteor_contest.rb
index 5dd720c340..30b99715af 100644
--- a/benchmark/bm_so_meteor_contest.rb
+++ b/benchmark/bm_so_meteor_contest.rb
@@ -1,564 +1,564 @@
-#!/usr/bin/env ruby

-#

-# The Computer Language Shootout

-#   http://shootout.alioth.debian.org

-#   contributed by Kevin Barnes (Ruby novice)

-

-# PROGRAM:  the main body is at the bottom.

-#   1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/

-#   2) see how I represent a board as a bitmask by reading the blank_board comments

-#   3) read as your mental paths take you

-

-def print *args

-end

-

-# class to represent all information about a particular rotation of a particular piece

-class Rotation

-  # an array (by location) containing a bit mask for how the piece maps at the given location.

-  # if the rotation is illegal at that location the mask will contain false

-  attr_reader :start_masks

-

-  # maps a direction to a relative location.  these differ depending on whether it is an even or

-  # odd row being mapped from

-  @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }

-  @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }

-

-  def initialize( directions )

-    @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))

-

-    @even_mask = mask_for_offsets( @even_offsets)

-    @odd_mask = mask_for_offsets( @odd_offsets)

-

-    @start_masks = Array.new(60)

-

-    # create the rotational masks by placing the base mask at the location and seeing if

-    # 1) it overlaps the boundries and 2) it produces a prunable board.  if either of these

-    # is true the piece cannot be placed

-    0.upto(59) do | offset |

-      mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)

-      if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then

-        imask = compute_required( mask, offset)

-        @start_masks[offset] = [ mask, imask, imask | mask ]

-      else

-        @start_masks[offset] = false

-      end

-    end

-  end

-

-  def compute_required( mask, offset )

-    board = blank_board

-    0.upto(offset) { | i | board |= 1 << i }

-    board |= mask

-    return 0 if (!prunable(board | mask, offset))

-    board = flood_fill(board,58)

-    count = 0

-    imask = 0

-    0.upto(59) do | i |

-      if (board[i] == 0) then

-        imask |= (1 << i)

-        count += 1

-      end

-    end

-    (count > 0 && count < 5) ? imask : 0

-  end

-

-  def flood_fill( board, location)

-    return board if (board[location] == 1)

-    board |= 1 << location

-    row, col = location.divmod(6)

-    board = flood_fill( board, location - 1) if (col > 0)

-    board = flood_fill( board, location + 1) if (col < 4)

-    if (row % 2 == 0) then

-      board = flood_fill( board, location - 7) if (col > 0 && row > 0)

-      board = flood_fill( board, location - 6) if (row > 0)

-      board = flood_fill( board, location + 6) if (row < 9)

-      board = flood_fill( board, location + 5) if (col > 0 && row < 9)

-    else

-      board = flood_fill( board, location - 5) if (col < 4 && row > 0)

-      board = flood_fill( board, location - 6) if (row > 0)

-      board = flood_fill( board, location + 6) if (row < 9)

-      board = flood_fill( board, location + 7) if (col < 4 && row < 9)

-    end

-    board

-  end

-

-  # given a location, produces a list of relative locations covered by the piece at this rotation

-  def offsets( location)

-    if is_even( location) then

-      @even_offsets.collect { | value | value + location }

-    else

-      @odd_offsets.collect { | value | value + location }

-    end

-  end

-

-  # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)

-  # this is hard to explain. imagine we have this partial board:

-  #   0 0 0 0 0 x        [positions 0-5]

-  #    0 0 1 1 0 x       [positions 6-11]

-  #   0 0 1 0 0 x        [positions 12-17]

-  #    0 1 0 0 0 x       [positions 18-23]

-  #   0 1 0 0 0 x        [positions 24-29]

-  #    0 0 0 0 0 x       [positions 30-35]

-  #       ...

-  # The top-left of the piece is at position 8, the

-  # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that

-  # sorted order.  Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained

-  # by subtracting 8 from everything.  Now imagine the piece shifted up and to the right so it's on an even row:

-  #   0 0 0 1 1 x        [positions 0-5]

-  #    0 0 1 0 0 x       [positions 6-11]

-  #   0 0 1 0 0 x        [positions 12-17]

-  #    0 1 0 0 0 x       [positions 18-23]

-  #   0 0 0 0 0 x        [positions 24-29]

-  #    0 0 0 0 0 x       [positions 30-35]

-  #       ...

-  # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the

-  # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what

-  # this function would return

-  def normalize_offsets( values)

-    min = values.min

-    even_min = is_even(min)

-    other_min = even_min ? min + 6 : min + 7

-    other_values = values.collect do | value |

-      if is_even(value) then

-        value + 6 - other_min

-      else

-        value + 7 - other_min

-      end

-    end

-    values.collect! { | value | value - min }

-

-    if even_min then

-      [values, other_values]

-    else

-      [other_values, values]

-    end

-  end

-

-  # produce a bitmask representation of an array of offset locations

-  def mask_for_offsets( offsets )

-    mask = 0

-    offsets.each { | value | mask = mask + ( 1 << value ) }

-    mask

-  end

-

-  # finds a "safe" position that a position as described by a list of directions can be placed

-  # without falling off any edge of the board.  the values returned a location to place the first piece

-  # at so it will fit after making the described moves

-  def start_adjust( directions )

-    south = east = 0;

-    directions.each do | direction |

-      east += 1 if ( direction == :sw || direction == :nw || direction == :west )

-      south += 1 if ( direction == :nw || direction == :ne )

-    end

-    south * 6 + east

-  end

-

-  # given a set of directions places the piece (as defined by a set of directions) on the board at

-  # a location that will not take it off the edge

-  def get_values ( directions )

-    start = start_adjust(directions)

-    values = [ start ]

-    directions.each do | direction |

-      if (start % 12 >= 6) then

-        start += @@rotation_odd_adder[direction]

-      else

-        start += @@rotation_even_adder[direction]

-      end

-      values += [ start ]

-    end

-

-    # some moves take you back to an existing location, we'll strip duplicates

-    values.uniq

-  end

-end

-

-# describes a piece and caches information about its rotations to as to be efficient for iteration

-# ATTRIBUTES:

-#   rotations -- all the rotations of the piece

-#   type -- a numeic "name" of the piece

-#   masks -- an array by location of all legal rotational masks (a n inner array) for that location

-#   placed -- the mask that this piece was last placed at (not a location, but the actual mask used)

-class Piece

-  attr_reader :rotations, :type, :masks

-  attr_accessor :placed

-

-  # transform hashes that change one direction into another when you either flip or rotate a set of directions

-  @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }

-  @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }

-

-  def initialize( directions, type )

-    @type = type

-    @rotations = Array.new();

-    @map = {}

-

-    generate_rotations( directions )

-    directions.collect! { | value | @@flip_converter[value] }

-    generate_rotations( directions )

-

-    # creates the masks AND a map that returns [location, rotation] for any given mask

-    # this is used when a board is found and we want to draw it, otherwise the map is unused

-    @masks = Array.new();

-    0.upto(59) do | i |

-      even = true

-      @masks[i] = @rotations.collect do | rotation |

-        mask = rotation.start_masks[i]

-        @map[mask[0]] = [ i, rotation ] if (mask)

-        mask || nil

-      end

-      @masks[i].compact!

-    end

-  end

-

-  # rotates a set of directions through all six angles and adds a Rotation to the list for each one

-  def generate_rotations( directions )

-    6.times do

-      rotations.push( Rotation.new(directions))

-      directions.collect! { | value | @@rotate_converter[value] }

-    end

-  end

-

-  # given a board string, adds this piece to the board at whatever location/rotation

-  # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)

-  def fill_string( board_string)

-    location, rotation = @map[@placed]

-    rotation.offsets(location).each do | offset |

-      row, col = offset.divmod(6)

-      board_string[ row*5 + col, 1 ] = @type.to_s

-    end

-  end

-end

-

-# a blank bit board having this form:

-#

-#    0 0 0 0 0 1

-#     0 0 0 0 0 1

-#    0 0 0 0 0 1

-#     0 0 0 0 0 1

-#    0 0 0 0 0 1

-#     0 0 0 0 0 1

-#    0 0 0 0 0 1

-#     0 0 0 0 0 1

-#    0 0 0 0 0 1

-#     0 0 0 0 0 1

-#    1 1 1 1 1 1

-#

-# where left lest significant bit is the top left and the most significant is the lower right

-# the actual board only consists of the 0 places, the 1 places are blockers to keep things from running

-# off the edges or bottom

-def blank_board

-  0b111111100000100000100000100000100000100000100000100000100000100000

-end

-

-def full_board

-  0b111111111111111111111111111111111111111111111111111111111111111111

-end

-

-# determines if a location (bit position) is in an even row

-def is_even( location)

-  (location % 12) < 6

-end

-

-# support function that create three utility maps:

-#  $converter -- for each row an array that maps a five bit row (via array mapping)

-#                to the a a five bit representation of the bits below it

-#  $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row

-#  @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays

-#                   a region array has three values the first is a mask of bits in the region,

-#                   the second is the count of those bits and the third is identical to the first

-#                   examples:

-#                           0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]

-#                           0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]

-#                           0b10001 => [ 0b01110, 3, 0b01110 ]

-def create_collector_support

-  odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]

-  even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]

-

-  all_odds = Array.new(0b100000)

-  all_evens = Array.new(0b100000)

-  bit_counts = Array.new(0b100000)

-  new_regions = Array.new(0b100000)

-  0.upto(0b11111) do | i |

-    bit_count = odd = even = 0

-    0.upto(4) do | bit |

-      if (i[bit] == 1) then

-        bit_count += 1

-        odd |= odd_map[bit]

-        even |= even_map[bit]

-      end

-    end

-    all_odds[i] = odd

-    all_evens[i] = even

-    bit_counts[i] = bit_count

-    new_regions[i] = create_regions( i)

-  end

-

-  $converter = []

-  10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }

-  $bit_counts = bit_counts

-  $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }

-end

-

-# determines if a board is punable, meaning that there is no possibility that it

-# can be filled up with pieces.  A board is prunable if there is a grouping of unfilled spaces

-# that are not a multiple of five.  The following board is an example of a prunable board:

-#    0 0 1 0 0

-#     0 1 0 0 0

-#    1 1 0 0 0

-#     0 1 0 0 0

-#    0 0 0 0 0

-#       ...

-#

-# This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it

-# parameters:

-#   board -- an initial bit board (6 bit padded rows, see blank_board for format)

-#   location -- starting location, everything above and to the left is already full

-#   slotting -- set to true only when testing initial pieces, when filling normally

-#               additional assumptions are possible

-#

-# Algorithm:

-#    The algorithm starts at the top row (as determined by location) and iterates a row at a time

-#    maintainng counts of active open areas (kept in the collector array) each collector contains

-#    three values at the start of an iteration:

-#          0: mask of bits that would be adjacent to the collector in this row

-#          1: the number of bits collected so far

-#          2: a scratch space starting as zero, but used during the computation to represent

-#             the empty bits in the new row that are adjacent (position 0)

-#  The exact procedure is described in-code

-def prunable( board, location, slotting = false)

-  collectors = []

-  # loop accross the rows

-  (location / 6).to_i.upto(9) do | row_on |

-    # obtain a set of regions representing the bits of the curent row.

-    regions = $regions[(board >> (row_on * 6)) & 0b11111]

-    converter = $converter[row_on]

-

-    # track the number of collectors at the start of the cycle so that

-    # we don't compute against newly created collectors, only existing collectors

-    initial_collector_count = collectors.length

-

-    # loop against the regions.  For each region of the row

-    # we will see if it connects to one or more existing collectors.

-    # if it connects to 1 collector, the bits from the region are added to the

-    # bits of the collector and the mask is placed in collector[2]

-    # If the region overlaps more than one collector then all the collectors

-    # it overlaps with are merged into the first one (the others are set to nil in the array)

-    # if NO collectors are found then the region is copied as a new collector

-    regions.each do | region |

-      collector_found = nil

-      region_mask = region[2]

-      initial_collector_count.times do | collector_num |

-        collector = collectors[collector_num]

-        if (collector) then

-          collector_mask = collector[0]

-          if (collector_mask & region_mask != 0) then

-            if (collector_found) then

-              collector_found[0] |= collector_mask

-              collector_found[1] += collector[1]

-              collector_found[2] |= collector[2]

-              collectors[collector_num] = nil

-            else

-              collector_found = collector

-              collector[1] += region[1]

-              collector[2] |= region_mask

-            end

-          end

-        end

-      end

-      if (collector_found == nil) then

-        collectors.push(Array.new(region))

-      end

-    end

-

-    # check the existing collectors, if any collector overlapped no bits in the region its [2] value will

-    # be zero.  The size of any such reaason is tested if it is not a muliple of five true is returned since

-    # the board is prunable.  if it is a multiple of five it is removed.

-    # Collector that are still active have a new adjacent value [0] set based n the matched bits

-    # and have [2] cleared out for the next cycle.

-    collectors.length.times do | collector_num |

-      collector = collectors[collector_num]

-      if (collector) then

-        if (collector[2] == 0) then

-          return true if (collector[1] % 5 != 0)

-          collectors[collector_num] = nil

-        else

-          # if a collector matches all bits in the row then we can return unprunable early for the

-          # follwing reasons:

-          #    1) there can be no more unavailable bits bince we fill from the top left downward

-          #    2) all previous regions have been closed or joined so only this region can fail

-          #    3) this region must be good since there can never be only 1 region that is nuot

-          #       a multiple of five

-          # this rule only applies when filling normally, so we ignore the rule if we are "slotting"

-          # in pieces to see what configurations work for them (the only other time this algorithm is used).

-          return false if (collector[2] == 0b11111 && !slotting)

-          collector[0] = converter[collector[2]]

-          collector[2] = 0

-        end

-      end

-    end

-

-    # get rid of all the empty converters for the next round

-    collectors.compact!

-  end

-  return false if (collectors.length <= 1) # 1 collector or less and the region is fine

-  collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size

-end

-

-# creates a region given a row mask.  see prunable for what a "region" is

-def create_regions( value )

-  regions = []

-  cur_region = 0

-  5.times do | bit |

-    if (value[bit] == 0) then

-      cur_region |= 1 << bit

-    else

-      if (cur_region != 0 ) then

-        regions.push( cur_region)

-        cur_region = 0;

-      end

-    end

-  end

-  regions.push(cur_region) if (cur_region != 0)

-  regions

-end

-

-# find up to the counted number of solutions (or all solutions) and prints the final result

-def find_all

-  find_top( 1)

-  find_top( 0)

-  print_results

-end

-

-# show the board

-def print_results

-  print "#{@boards_found} solutions found\n\n"

-  print_full_board( @min_board)

-  print "\n"

-  print_full_board( @max_board)

-  print "\n"

-end

-

-# finds solutions.  This special version of the main function is only used for the top level

-# the reason for it is basically to force a particular ordering on how the rotations are tested for

-# the first piece.  It is called twice, first looking for placements of the odd rotations and then

-# looking for placements of the even locations.

-#

-# WHY?

-#   Since any found solution has an inverse we want to maximize finding solutions that are not already found

-#   as an inverse.  The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away

-#   (an odd number).  Checking even vs odd then produces a higher probability of finding more pieces earlier

-#   in the cycle.  We still need to keep checking all the permutations, but our probability of finding one will

-#   diminsh over time.  Since we are TOLD how many to search for this lets us exit before checking all pieces

-#   this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the

-#   maximum number

-def find_top( rotation_skip)

-  board = blank_board

-  (@pieces.length-1).times do

-    piece = @pieces.shift

-    piece.masks[0].each do | mask, imask, cmask |

-      if ((rotation_skip += 1) % 2 == 0) then

-        piece.placed = mask

-        find( 1, 1, board | mask)

-      end

-    end

-    @pieces.push(piece)

-  end

-  piece = @pieces.shift

-  @pieces.push(piece)

-end

-

-# the normail find routine, iterates through the available pieces, checks all rotations at the current location

-# and adds any boards found.  depth is acheived via recursion.  the overall approach is described

-# here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/

-# parameters:

-#  start_location -- where to start looking for place for the next piece at

-#  placed -- number of pieces placed

-#  board -- current state of the board

-#

-# see in-code comments

-def find( start_location, placed, board)

-  # find the next location to place a piece by looking for an empty bit

-  while board[start_location] == 1

-    start_location += 1

-  end

-

-  @pieces.length.times do

-    piece = @pieces.shift

-    piece.masks[start_location].each do | mask, imask, cmask |

-      if ( board & cmask == imask) then

-        piece.placed = mask

-        if (placed == 9) then

-          add_board

-        else

-          find( start_location + 1, placed + 1, board | mask)

-        end

-      end

-    end

-    @pieces.push(piece)

-  end

-end

-

-# print the board

-def print_full_board( board_string)

-  10.times do | row |

-    print " " if (row % 2 == 1)

-    5.times do | col |

-      print "#{board_string[row*5 + col,1]} "

-    end

-    print "\n"

-  end

-end

-

-# when a board is found we "draw it" into a string and then flip that string, adding both to

-# the list (hash) of solutions if they are unique.

-def add_board

-  board_string = "99999999999999999999999999999999999999999999999999"

-  @all_pieces.each {  | piece | piece.fill_string( board_string ) }

-  save( board_string)

-  save( board_string.reverse)

-end

-

-# adds a board string to the list (if new) and updates the current best/worst board

-def save( board_string)

-  if (@all_boards[board_string] == nil) then

-    @min_board = board_string if (board_string < @min_board)

-    @max_board = board_string if (board_string > @max_board)

-    @all_boards.store(board_string,true)

-    @boards_found += 1

-

-    # the exit motif is a time saver.  Ideally the function should return, but those tests

-    # take noticable time (performance).

-    if (@boards_found == @stop_count) then

-      print_results

-      exit(0)

-    end

-  end

-end

-

-

-##

-## MAIN BODY :)

-##

-create_collector_support

-@pieces = [

-  Piece.new( [ :nw, :ne, :east, :east ], 2),

-  Piece.new( [ :ne, :se, :east, :ne ], 7),

-  Piece.new( [ :ne, :east, :ne, :nw ], 1),

-  Piece.new( [ :east, :sw, :sw, :se ], 6),

-  Piece.new( [ :east, :ne, :se, :ne ], 5),

-  Piece.new( [ :east, :east, :east, :se ], 0),

-  Piece.new( [ :ne, :nw, :se, :east, :se ], 4),

-  Piece.new( [ :se, :se, :se, :west ], 9),

-  Piece.new( [ :se, :se, :east, :se ], 8),

-  Piece.new( [ :east, :east, :sw, :se ], 3)

-  ];

-

-@all_pieces = Array.new( @pieces)

-

-@min_board = "99999999999999999999999999999999999999999999999999"

-@max_board = "00000000000000000000000000000000000000000000000000"

-@stop_count = ARGV[0].to_i || 2089

-@all_boards = {}

-@boards_found = 0

-

-find_all ######## DO IT!!!

-

+#!/usr/bin/env ruby
+#
+# The Computer Language Shootout
+#   http://shootout.alioth.debian.org
+#   contributed by Kevin Barnes (Ruby novice)
+
+# PROGRAM:  the main body is at the bottom.
+#   1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
+#   2) see how I represent a board as a bitmask by reading the blank_board comments
+#   3) read as your mental paths take you
+
+def print *args
+end
+
+# class to represent all information about a particular rotation of a particular piece
+class Rotation
+  # an array (by location) containing a bit mask for how the piece maps at the given location.
+  # if the rotation is illegal at that location the mask will contain false
+  attr_reader :start_masks
+
+  # maps a direction to a relative location.  these differ depending on whether it is an even or
+  # odd row being mapped from
+  @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }
+  @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }
+
+  def initialize( directions )
+    @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))
+
+    @even_mask = mask_for_offsets( @even_offsets)
+    @odd_mask = mask_for_offsets( @odd_offsets)
+
+    @start_masks = Array.new(60)
+
+    # create the rotational masks by placing the base mask at the location and seeing if
+    # 1) it overlaps the boundries and 2) it produces a prunable board.  if either of these
+    # is true the piece cannot be placed
+    0.upto(59) do | offset |
+      mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)
+      if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then
+        imask = compute_required( mask, offset)
+        @start_masks[offset] = [ mask, imask, imask | mask ]
+      else
+        @start_masks[offset] = false
+      end
+    end
+  end
+
+  def compute_required( mask, offset )
+    board = blank_board
+    0.upto(offset) { | i | board |= 1 << i }
+    board |= mask
+    return 0 if (!prunable(board | mask, offset))
+    board = flood_fill(board,58)
+    count = 0
+    imask = 0
+    0.upto(59) do | i |
+      if (board[i] == 0) then
+        imask |= (1 << i)
+        count += 1
+      end
+    end
+    (count > 0 && count < 5) ? imask : 0
+  end
+
+  def flood_fill( board, location)
+    return board if (board[location] == 1)
+    board |= 1 << location
+    row, col = location.divmod(6)
+    board = flood_fill( board, location - 1) if (col > 0)
+    board = flood_fill( board, location + 1) if (col < 4)
+    if (row % 2 == 0) then
+      board = flood_fill( board, location - 7) if (col > 0 && row > 0)
+      board = flood_fill( board, location - 6) if (row > 0)
+      board = flood_fill( board, location + 6) if (row < 9)
+      board = flood_fill( board, location + 5) if (col > 0 && row < 9)
+    else
+      board = flood_fill( board, location - 5) if (col < 4 && row > 0)
+      board = flood_fill( board, location - 6) if (row > 0)
+      board = flood_fill( board, location + 6) if (row < 9)
+      board = flood_fill( board, location + 7) if (col < 4 && row < 9)
+    end
+    board
+  end
+
+  # given a location, produces a list of relative locations covered by the piece at this rotation
+  def offsets( location)
+    if is_even( location) then
+      @even_offsets.collect { | value | value + location }
+    else
+      @odd_offsets.collect { | value | value + location }
+    end
+  end
+
+  # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)
+  # this is hard to explain. imagine we have this partial board:
+  #   0 0 0 0 0 x        [positions 0-5]
+  #    0 0 1 1 0 x       [positions 6-11]
+  #   0 0 1 0 0 x        [positions 12-17]
+  #    0 1 0 0 0 x       [positions 18-23]
+  #   0 1 0 0 0 x        [positions 24-29]
+  #    0 0 0 0 0 x       [positions 30-35]
+  #       ...
+  # The top-left of the piece is at position 8, the
+  # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that
+  # sorted order.  Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained
+  # by subtracting 8 from everything.  Now imagine the piece shifted up and to the right so it's on an even row:
+  #   0 0 0 1 1 x        [positions 0-5]
+  #    0 0 1 0 0 x       [positions 6-11]
+  #   0 0 1 0 0 x        [positions 12-17]
+  #    0 1 0 0 0 x       [positions 18-23]
+  #   0 0 0 0 0 x        [positions 24-29]
+  #    0 0 0 0 0 x       [positions 30-35]
+  #       ...
+  # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the
+  # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what
+  # this function would return
+  def normalize_offsets( values)
+    min = values.min
+    even_min = is_even(min)
+    other_min = even_min ? min + 6 : min + 7
+    other_values = values.collect do | value |
+      if is_even(value) then
+        value + 6 - other_min
+      else
+        value + 7 - other_min
+      end
+    end
+    values.collect! { | value | value - min }
+
+    if even_min then
+      [values, other_values]
+    else
+      [other_values, values]
+    end
+  end
+
+  # produce a bitmask representation of an array of offset locations
+  def mask_for_offsets( offsets )
+    mask = 0
+    offsets.each { | value | mask = mask + ( 1 << value ) }
+    mask
+  end
+
+  # finds a "safe" position that a position as described by a list of directions can be placed
+  # without falling off any edge of the board.  the values returned a location to place the first piece
+  # at so it will fit after making the described moves
+  def start_adjust( directions )
+    south = east = 0;
+    directions.each do | direction |
+      east += 1 if ( direction == :sw || direction == :nw || direction == :west )
+      south += 1 if ( direction == :nw || direction == :ne )
+    end
+    south * 6 + east
+  end
+
+  # given a set of directions places the piece (as defined by a set of directions) on the board at
+  # a location that will not take it off the edge
+  def get_values ( directions )
+    start = start_adjust(directions)
+    values = [ start ]
+    directions.each do | direction |
+      if (start % 12 >= 6) then
+        start += @@rotation_odd_adder[direction]
+      else
+        start += @@rotation_even_adder[direction]
+      end
+      values += [ start ]
+    end
+
+    # some moves take you back to an existing location, we'll strip duplicates
+    values.uniq
+  end
+end
+
+# describes a piece and caches information about its rotations to as to be efficient for iteration
+# ATTRIBUTES:
+#   rotations -- all the rotations of the piece
+#   type -- a numeic "name" of the piece
+#   masks -- an array by location of all legal rotational masks (a n inner array) for that location
+#   placed -- the mask that this piece was last placed at (not a location, but the actual mask used)
+class Piece
+  attr_reader :rotations, :type, :masks
+  attr_accessor :placed
+
+  # transform hashes that change one direction into another when you either flip or rotate a set of directions
+  @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }
+  @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }
+
+  def initialize( directions, type )
+    @type = type
+    @rotations = Array.new();
+    @map = {}
+
+    generate_rotations( directions )
+    directions.collect! { | value | @@flip_converter[value] }
+    generate_rotations( directions )
+
+    # creates the masks AND a map that returns [location, rotation] for any given mask
+    # this is used when a board is found and we want to draw it, otherwise the map is unused
+    @masks = Array.new();
+    0.upto(59) do | i |
+      even = true
+      @masks[i] = @rotations.collect do | rotation |
+        mask = rotation.start_masks[i]
+        @map[mask[0]] = [ i, rotation ] if (mask)
+        mask || nil
+      end
+      @masks[i].compact!
+    end
+  end
+
+  # rotates a set of directions through all six angles and adds a Rotation to the list for each one
+  def generate_rotations( directions )
+    6.times do
+      rotations.push( Rotation.new(directions))
+      directions.collect! { | value | @@rotate_converter[value] }
+    end
+  end
+
+  # given a board string, adds this piece to the board at whatever location/rotation
+  # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)
+  def fill_string( board_string)
+    location, rotation = @map[@placed]
+    rotation.offsets(location).each do | offset |
+      row, col = offset.divmod(6)
+      board_string[ row*5 + col, 1 ] = @type.to_s
+    end
+  end
+end
+
+# a blank bit board having this form:
+#
+#    0 0 0 0 0 1
+#     0 0 0 0 0 1
+#    0 0 0 0 0 1
+#     0 0 0 0 0 1
+#    0 0 0 0 0 1
+#     0 0 0 0 0 1
+#    0 0 0 0 0 1
+#     0 0 0 0 0 1
+#    0 0 0 0 0 1
+#     0 0 0 0 0 1
+#    1 1 1 1 1 1
+#
+# where left lest significant bit is the top left and the most significant is the lower right
+# the actual board only consists of the 0 places, the 1 places are blockers to keep things from running
+# off the edges or bottom
+def blank_board
+  0b111111100000100000100000100000100000100000100000100000100000100000
+end
+
+def full_board
+  0b111111111111111111111111111111111111111111111111111111111111111111
+end
+
+# determines if a location (bit position) is in an even row
+def is_even( location)
+  (location % 12) < 6
+end
+
+# support function that create three utility maps:
+#  $converter -- for each row an array that maps a five bit row (via array mapping)
+#                to the a a five bit representation of the bits below it
+#  $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row
+#  @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays
+#                   a region array has three values the first is a mask of bits in the region,
+#                   the second is the count of those bits and the third is identical to the first
+#                   examples:
+#                           0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]
+#                           0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]
+#                           0b10001 => [ 0b01110, 3, 0b01110 ]
+def create_collector_support
+  odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]
+  even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]
+
+  all_odds = Array.new(0b100000)
+  all_evens = Array.new(0b100000)
+  bit_counts = Array.new(0b100000)
+  new_regions = Array.new(0b100000)
+  0.upto(0b11111) do | i |
+    bit_count = odd = even = 0
+    0.upto(4) do | bit |
+      if (i[bit] == 1) then
+        bit_count += 1
+        odd |= odd_map[bit]
+        even |= even_map[bit]
+      end
+    end
+    all_odds[i] = odd
+    all_evens[i] = even
+    bit_counts[i] = bit_count
+    new_regions[i] = create_regions( i)
+  end
+
+  $converter = []
+  10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }
+  $bit_counts = bit_counts
+  $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }
+end
+
+# determines if a board is punable, meaning that there is no possibility that it
+# can be filled up with pieces.  A board is prunable if there is a grouping of unfilled spaces
+# that are not a multiple of five.  The following board is an example of a prunable board:
+#    0 0 1 0 0
+#     0 1 0 0 0
+#    1 1 0 0 0
+#     0 1 0 0 0
+#    0 0 0 0 0
+#       ...
+#
+# This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it
+# parameters:
+#   board -- an initial bit board (6 bit padded rows, see blank_board for format)
+#   location -- starting location, everything above and to the left is already full
+#   slotting -- set to true only when testing initial pieces, when filling normally
+#               additional assumptions are possible
+#
+# Algorithm:
+#    The algorithm starts at the top row (as determined by location) and iterates a row at a time
+#    maintainng counts of active open areas (kept in the collector array) each collector contains
+#    three values at the start of an iteration:
+#          0: mask of bits that would be adjacent to the collector in this row
+#          1: the number of bits collected so far
+#          2: a scratch space starting as zero, but used during the computation to represent
+#             the empty bits in the new row that are adjacent (position 0)
+#  The exact procedure is described in-code
+def prunable( board, location, slotting = false)
+  collectors = []
+  # loop accross the rows
+  (location / 6).to_i.upto(9) do | row_on |
+    # obtain a set of regions representing the bits of the curent row.
+    regions = $regions[(board >> (row_on * 6)) & 0b11111]
+    converter = $converter[row_on]
+
+    # track the number of collectors at the start of the cycle so that
+    # we don't compute against newly created collectors, only existing collectors
+    initial_collector_count = collectors.length
+
+    # loop against the regions.  For each region of the row
+    # we will see if it connects to one or more existing collectors.
+    # if it connects to 1 collector, the bits from the region are added to the
+    # bits of the collector and the mask is placed in collector[2]
+    # If the region overlaps more than one collector then all the collectors
+    # it overlaps with are merged into the first one (the others are set to nil in the array)
+    # if NO collectors are found then the region is copied as a new collector
+    regions.each do | region |
+      collector_found = nil
+      region_mask = region[2]
+      initial_collector_count.times do | collector_num |
+        collector = collectors[collector_num]
+        if (collector) then
+          collector_mask = collector[0]
+          if (collector_mask & region_mask != 0) then
+            if (collector_found) then
+              collector_found[0] |= collector_mask
+              collector_found[1] += collector[1]
+              collector_found[2] |= collector[2]
+              collectors[collector_num] = nil
+            else
+              collector_found = collector
+              collector[1] += region[1]
+              collector[2] |= region_mask
+            end
+          end
+        end
+      end
+      if (collector_found == nil) then
+        collectors.push(Array.new(region))
+      end
+    end
+
+    # check the existing collectors, if any collector overlapped no bits in the region its [2] value will
+    # be zero.  The size of any such reaason is tested if it is not a muliple of five true is returned since
+    # the board is prunable.  if it is a multiple of five it is removed.
+    # Collector that are still active have a new adjacent value [0] set based n the matched bits
+    # and have [2] cleared out for the next cycle.
+    collectors.length.times do | collector_num |
+      collector = collectors[collector_num]
+      if (collector) then
+        if (collector[2] == 0) then
+          return true if (collector[1] % 5 != 0)
+          collectors[collector_num] = nil
+        else
+          # if a collector matches all bits in the row then we can return unprunable early for the
+          # follwing reasons:
+          #    1) there can be no more unavailable bits bince we fill from the top left downward
+          #    2) all previous regions have been closed or joined so only this region can fail
+          #    3) this region must be good since there can never be only 1 region that is nuot
+          #       a multiple of five
+          # this rule only applies when filling normally, so we ignore the rule if we are "slotting"
+          # in pieces to see what configurations work for them (the only other time this algorithm is used).
+          return false if (collector[2] == 0b11111 && !slotting)
+          collector[0] = converter[collector[2]]
+          collector[2] = 0
+        end
+      end
+    end
+
+    # get rid of all the empty converters for the next round
+    collectors.compact!
+  end
+  return false if (collectors.length <= 1) # 1 collector or less and the region is fine
+  collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size
+end
+
+# creates a region given a row mask.  see prunable for what a "region" is
+def create_regions( value )
+  regions = []
+  cur_region = 0
+  5.times do | bit |
+    if (value[bit] == 0) then
+      cur_region |= 1 << bit
+    else
+      if (cur_region != 0 ) then
+        regions.push( cur_region)
+        cur_region = 0;
+      end
+    end
+  end
+  regions.push(cur_region) if (cur_region != 0)
+  regions
+end
+
+# find up to the counted number of solutions (or all solutions) and prints the final result
+def find_all
+  find_top( 1)
+  find_top( 0)
+  print_results
+end
+
+# show the board
+def print_results
+  print "#{@boards_found} solutions found\n\n"
+  print_full_board( @min_board)
+  print "\n"
+  print_full_board( @max_board)
+  print "\n"
+end
+
+# finds solutions.  This special version of the main function is only used for the top level
+# the reason for it is basically to force a particular ordering on how the rotations are tested for
+# the first piece.  It is called twice, first looking for placements of the odd rotations and then
+# looking for placements of the even locations.
+#
+# WHY?
+#   Since any found solution has an inverse we want to maximize finding solutions that are not already found
+#   as an inverse.  The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away
+#   (an odd number).  Checking even vs odd then produces a higher probability of finding more pieces earlier
+#   in the cycle.  We still need to keep checking all the permutations, but our probability of finding one will
+#   diminsh over time.  Since we are TOLD how many to search for this lets us exit before checking all pieces
+#   this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the
+#   maximum number
+def find_top( rotation_skip)
+  board = blank_board
+  (@pieces.length-1).times do
+    piece = @pieces.shift
+    piece.masks[0].each do | mask, imask, cmask |
+      if ((rotation_skip += 1) % 2 == 0) then
+        piece.placed = mask
+        find( 1, 1, board | mask)
+      end
+    end
+    @pieces.push(piece)
+  end
+  piece = @pieces.shift
+  @pieces.push(piece)
+end
+
+# the normail find routine, iterates through the available pieces, checks all rotations at the current location
+# and adds any boards found.  depth is acheived via recursion.  the overall approach is described
+# here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
+# parameters:
+#  start_location -- where to start looking for place for the next piece at
+#  placed -- number of pieces placed
+#  board -- current state of the board
+#
+# see in-code comments
+def find( start_location, placed, board)
+  # find the next location to place a piece by looking for an empty bit
+  while board[start_location] == 1
+    start_location += 1
+  end
+
+  @pieces.length.times do
+    piece = @pieces.shift
+    piece.masks[start_location].each do | mask, imask, cmask |
+      if ( board & cmask == imask) then
+        piece.placed = mask
+        if (placed == 9) then
+          add_board
+        else
+          find( start_location + 1, placed + 1, board | mask)
+        end
+      end
+    end
+    @pieces.push(piece)
+  end
+end
+
+# print the board
+def print_full_board( board_string)
+  10.times do | row |
+    print " " if (row % 2 == 1)
+    5.times do | col |
+      print "#{board_string[row*5 + col,1]} "
+    end
+    print "\n"
+  end
+end
+
+# when a board is found we "draw it" into a string and then flip that string, adding both to
+# the list (hash) of solutions if they are unique.
+def add_board
+  board_string = "99999999999999999999999999999999999999999999999999"
+  @all_pieces.each {  | piece | piece.fill_string( board_string ) }
+  save( board_string)
+  save( board_string.reverse)
+end
+
+# adds a board string to the list (if new) and updates the current best/worst board
+def save( board_string)
+  if (@all_boards[board_string] == nil) then
+    @min_board = board_string if (board_string < @min_board)
+    @max_board = board_string if (board_string > @max_board)
+    @all_boards.store(board_string,true)
+    @boards_found += 1
+
+    # the exit motif is a time saver.  Ideally the function should return, but those tests
+    # take noticable time (performance).
+    if (@boards_found == @stop_count) then
+      print_results
+      exit(0)
+    end
+  end
+end
+
+
+##
+## MAIN BODY :)
+##
+create_collector_support
+@pieces = [
+  Piece.new( [ :nw, :ne, :east, :east ], 2),
+  Piece.new( [ :ne, :se, :east, :ne ], 7),
+  Piece.new( [ :ne, :east, :ne, :nw ], 1),
+  Piece.new( [ :east, :sw, :sw, :se ], 6),
+  Piece.new( [ :east, :ne, :se, :ne ], 5),
+  Piece.new( [ :east, :east, :east, :se ], 0),
+  Piece.new( [ :ne, :nw, :se, :east, :se ], 4),
+  Piece.new( [ :se, :se, :se, :west ], 9),
+  Piece.new( [ :se, :se, :east, :se ], 8),
+  Piece.new( [ :east, :east, :sw, :se ], 3)
+  ];
+
+@all_pieces = Array.new( @pieces)
+
+@min_board = "99999999999999999999999999999999999999999999999999"
+@max_board = "00000000000000000000000000000000000000000000000000"
+@stop_count = ARGV[0].to_i || 2089
+@all_boards = {}
+@boards_found = 0
+
+find_all ######## DO IT!!!
+