1: #!/usr/bin/env ruby
    2: #
    3: # The Computer Language Shootout
    4: #   http://shootout.alioth.debian.org
    5: #   contributed by Kevin Barnes (Ruby novice)
    6: 
    7: # PROGRAM:  the main body is at the bottom.
    8: #   1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
    9: #   2) see how I represent a board as a bitmask by reading the blank_board comments
   10: #   3) read as your mental paths take you
   11: 
   12: def print *args
   13: end
   14: 
   15: # class to represent all information about a particular rotation of a particular piece
   16: class Rotation
   17:   # an array (by location) containing a bit mask for how the piece maps at the given location.
   18:   # if the rotation is invalid at that location the mask will contain false
   19:   attr_reader :start_masks
   20: 
   21:   # maps a direction to a relative location.  these differ depending on whether it is an even or
   22:   # odd row being mapped from
   23:   @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }
   24:   @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }
   25: 
   26:   def initialize( directions )
   27:     @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))
   28: 
   29:     @even_mask = mask_for_offsets( @even_offsets)
   30:     @odd_mask = mask_for_offsets( @odd_offsets)
   31: 
   32:     @start_masks = Array.new(60)
   33: 
   34:     # create the rotational masks by placing the base mask at the location and seeing if
   35:     # 1) it overlaps the boundries and 2) it produces a prunable board.  if either of these
   36:     # is true the piece cannot be placed
   37:     0.upto(59) do | offset |
   38:       mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)
   39:       if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then
   40:         imask = compute_required( mask, offset)
   41:         @start_masks[offset] = [ mask, imask, imask | mask ]
   42:       else
   43:         @start_masks[offset] = false
   44:       end
   45:     end
   46:   end
   47: 
   48:   def compute_required( mask, offset )
   49:     board = blank_board
   50:     0.upto(offset) { | i | board |= 1 << i }
   51:     board |= mask
   52:     return 0 if (!prunable(board | mask, offset))
   53:     board = flood_fill(board,58)
   54:     count = 0
   55:     imask = 0
   56:     0.upto(59) do | i |
   57:       if (board[i] == 0) then
   58:         imask |= (1 << i)
   59:         count += 1
   60:       end
   61:     end
   62:     (count > 0 && count < 5) ? imask : 0
   63:   end
   64: 
   65:   def flood_fill( board, location)
   66:     return board if (board[location] == 1)
   67:     board |= 1 << location
   68:     row, col = location.divmod(6)
   69:     board = flood_fill( board, location - 1) if (col > 0)
   70:     board = flood_fill( board, location + 1) if (col < 4)
   71:     if (row % 2 == 0) then
   72:       board = flood_fill( board, location - 7) if (col > 0 && row > 0)
   73:       board = flood_fill( board, location - 6) if (row > 0)
   74:       board = flood_fill( board, location + 6) if (row < 9)
   75:       board = flood_fill( board, location + 5) if (col > 0 && row < 9)
   76:     else
   77:       board = flood_fill( board, location - 5) if (col < 4 && row > 0)
   78:       board = flood_fill( board, location - 6) if (row > 0)
   79:       board = flood_fill( board, location + 6) if (row < 9)
   80:       board = flood_fill( board, location + 7) if (col < 4 && row < 9)
   81:     end
   82:     board
   83:   end
   84: 
   85:   # given a location, produces a list of relative locations covered by the piece at this rotation
   86:   def offsets( location)
   87:     if is_even( location) then
   88:       @even_offsets.collect { | value | value + location }
   89:     else
   90:       @odd_offsets.collect { | value | value + location }
   91:     end
   92:   end
   93: 
   94:   # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)
   95:   # this is hard to explain. imagine we have this partial board:
   96:   #   0 0 0 0 0 x        [positions 0-5]
   97:   #    0 0 1 1 0 x       [positions 6-11]
   98:   #   0 0 1 0 0 x        [positions 12-17]
   99:   #    0 1 0 0 0 x       [positions 18-23]
  100:   #   0 1 0 0 0 x        [positions 24-29]
  101:   #    0 0 0 0 0 x       [positions 30-35]
  102:   #       ...
  103:   # The top-left of the piece is at position 8, the
  104:   # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that
  105:   # sorted order.  Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained
  106:   # by subtracting 8 from everything.  Now imagine the piece shifted up and to the right so it's on an even row:
  107:   #   0 0 0 1 1 x        [positions 0-5]
  108:   #    0 0 1 0 0 x       [positions 6-11]
  109:   #   0 0 1 0 0 x        [positions 12-17]
  110:   #    0 1 0 0 0 x       [positions 18-23]
  111:   #   0 0 0 0 0 x        [positions 24-29]
  112:   #    0 0 0 0 0 x       [positions 30-35]
  113:   #       ...
  114:   # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the
  115:   # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what
  116:   # this function would return
  117:   def normalize_offsets( values)
  118:     min = values.min
  119:     even_min = is_even(min)
  120:     other_min = even_min ? min + 6 : min + 7
  121:     other_values = values.collect do | value |
  122:       if is_even(value) then
  123:         value + 6 - other_min
  124:       else
  125:         value + 7 - other_min
  126:       end
  127:     end
  128:     values.collect! { | value | value - min }
  129: 
  130:     if even_min then
  131:       [values, other_values]
  132:     else
  133:       [other_values, values]
  134:     end
  135:   end
  136: 
  137:   # produce a bitmask representation of an array of offset locations
  138:   def mask_for_offsets( offsets )
  139:     mask = 0
  140:     offsets.each { | value | mask = mask + ( 1 << value ) }
  141:     mask
  142:   end
  143: 
  144:   # finds a "safe" position that a position as described by a list of directions can be placed
  145:   # without falling off any edge of the board.  the values returned a location to place the first piece
  146:   # at so it will fit after making the described moves
  147:   def start_adjust( directions )
  148:     south = east = 0;
  149:     directions.each do | direction |
  150:       east += 1 if ( direction == :sw || direction == :nw || direction == :west )
  151:       south += 1 if ( direction == :nw || direction == :ne )
  152:     end
  153:     south * 6 + east
  154:   end
  155: 
  156:   # given a set of directions places the piece (as defined by a set of directions) on the board at
  157:   # a location that will not take it off the edge
  158:   def get_values ( directions )
  159:     start = start_adjust(directions)
  160:     values = [ start ]
  161:     directions.each do | direction |
  162:       if (start % 12 >= 6) then
  163:         start += @@rotation_odd_adder[direction]
  164:       else
  165:         start += @@rotation_even_adder[direction]
  166:       end
  167:       values += [ start ]
  168:     end
  169: 
  170:     # some moves take you back to an existing location, we'll strip duplicates
  171:     values.uniq
  172:   end
  173: end
  174: 
  175: # describes a piece and caches information about its rotations to as to be efficient for iteration
  176: # ATTRIBUTES:
  177: #   rotations -- all the rotations of the piece
  178: #   type -- a numeic "name" of the piece
  179: #   masks -- an array by location of all legal rotational masks (a n inner array) for that location
  180: #   placed -- the mask that this piece was last placed at (not a location, but the actual mask used)
  181: class Piece
  182:   attr_reader :rotations, :type, :masks
  183:   attr_accessor :placed
  184: 
  185:   # transform hashes that change one direction into another when you either flip or rotate a set of directions
  186:   @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }
  187:   @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }
  188: 
  189:   def initialize( directions, type )
  190:     @type = type
  191:     @rotations = Array.new();
  192:     @map = {}
  193: 
  194:     generate_rotations( directions )
  195:     directions.collect! { | value | @@flip_converter[value] }
  196:     generate_rotations( directions )
  197: 
  198:     # creates the masks AND a map that returns [location, rotation] for any given mask
  199:     # this is used when a board is found and we want to draw it, otherwise the map is unused
  200:     @masks = Array.new();
  201:     0.upto(59) do | i |
  202:       even = true
  203:       @masks[i] = @rotations.collect do | rotation |
  204:         mask = rotation.start_masks[i]
  205:         @map[mask[0]] = [ i, rotation ] if (mask)
  206:         mask || nil
  207:       end
  208:       @masks[i].compact!
  209:     end
  210:   end
  211: 
  212:   # rotates a set of directions through all six angles and adds a Rotation to the list for each one
  213:   def generate_rotations( directions )
  214:     6.times do
  215:       rotations.push( Rotation.new(directions))
  216:       directions.collect! { | value | @@rotate_converter[value] }
  217:     end
  218:   end
  219: 
  220:   # given a board string, adds this piece to the board at whatever location/rotation
  221:   # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)
  222:   def fill_string( board_string)
  223:     location, rotation = @map[@placed]
  224:     rotation.offsets(location).each do | offset |
  225:       row, col = offset.divmod(6)
  226:       board_string[ row*5 + col, 1 ] = @type.to_s
  227:     end
  228:   end
  229: end
  230: 
  231: # a blank bit board having this form:
  232: #
  233: #    0 0 0 0 0 1
  234: #     0 0 0 0 0 1
  235: #    0 0 0 0 0 1
  236: #     0 0 0 0 0 1
  237: #    0 0 0 0 0 1
  238: #     0 0 0 0 0 1
  239: #    0 0 0 0 0 1
  240: #     0 0 0 0 0 1
  241: #    0 0 0 0 0 1
  242: #     0 0 0 0 0 1
  243: #    1 1 1 1 1 1
  244: #
  245: # where left lest significant bit is the top left and the most significant is the lower right
  246: # the actual board only consists of the 0 places, the 1 places are blockers to keep things from running
  247: # off the edges or bottom
  248: def blank_board
  249:   0b111111100000100000100000100000100000100000100000100000100000100000
  250: end
  251: 
  252: def full_board
  253:   0b111111111111111111111111111111111111111111111111111111111111111111
  254: end
  255: 
  256: # determines if a location (bit position) is in an even row
  257: def is_even( location)
  258:   (location % 12) < 6
  259: end
  260: 
  261: # support function that create three utility maps:
  262: #  $converter -- for each row an array that maps a five bit row (via array mapping)
  263: #                to the a a five bit representation of the bits below it
  264: #  $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row
  265: #  @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays
  266: #                   a region array has three values the first is a mask of bits in the region,
  267: #                   the second is the count of those bits and the third is identical to the first
  268: #                   examples:
  269: #                           0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]
  270: #                           0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]
  271: #                           0b10001 => [ 0b01110, 3, 0b01110 ]
  272: def create_collector_support
  273:   odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]
  274:   even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]
  275: 
  276:   all_odds = Array.new(0b100000)
  277:   all_evens = Array.new(0b100000)
  278:   bit_counts = Array.new(0b100000)
  279:   new_regions = Array.new(0b100000)
  280:   0.upto(0b11111) do | i |
  281:     bit_count = odd = even = 0
  282:     0.upto(4) do | bit |
  283:       if (i[bit] == 1) then
  284:         bit_count += 1
  285:         odd |= odd_map[bit]
  286:         even |= even_map[bit]
  287:       end
  288:     end
  289:     all_odds[i] = odd
  290:     all_evens[i] = even
  291:     bit_counts[i] = bit_count
  292:     new_regions[i] = create_regions( i)
  293:   end
  294: 
  295:   $converter = []
  296:   10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }
  297:   $bit_counts = bit_counts
  298:   $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }
  299: end
  300: 
  301: # determines if a board is punable, meaning that there is no possibility that it
  302: # can be filled up with pieces.  A board is prunable if there is a grouping of unfilled spaces
  303: # that are not a multiple of five.  The following board is an example of a prunable board:
  304: #    0 0 1 0 0
  305: #     0 1 0 0 0
  306: #    1 1 0 0 0
  307: #     0 1 0 0 0
  308: #    0 0 0 0 0
  309: #       ...
  310: #
  311: # This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it
  312: # parameters:
  313: #   board -- an initial bit board (6 bit padded rows, see blank_board for format)
  314: #   location -- starting location, everything above and to the left is already full
  315: #   slotting -- set to true only when testing initial pieces, when filling normally
  316: #               additional assumptions are possible
  317: #
  318: # Algorithm:
  319: #    The algorithm starts at the top row (as determined by location) and iterates a row at a time
  320: #    maintainng counts of active open areas (kept in the collector array) each collector contains
  321: #    three values at the start of an iteration:
  322: #          0: mask of bits that would be adjacent to the collector in this row
  323: #          1: the number of bits collected so far
  324: #          2: a scratch space starting as zero, but used during the computation to represent
  325: #             the empty bits in the new row that are adjacent (position 0)
  326: #  The exact procedure is described in-code
  327: def prunable( board, location, slotting = false)
  328:   collectors = []
  329:   # loop accross the rows
  330:   (location / 6).to_i.upto(9) do | row_on |
  331:     # obtain a set of regions representing the bits of the curent row.
  332:     regions = $regions[(board >> (row_on * 6)) & 0b11111]
  333:     converter = $converter[row_on]
  334: 
  335:     # track the number of collectors at the start of the cycle so that
  336:     # we don't compute against newly created collectors, only existing collectors
  337:     initial_collector_count = collectors.length
  338: 
  339:     # loop against the regions.  For each region of the row
  340:     # we will see if it connects to one or more existing collectors.
  341:     # if it connects to 1 collector, the bits from the region are added to the
  342:     # bits of the collector and the mask is placed in collector[2]
  343:     # If the region overlaps more than one collector then all the collectors
  344:     # it overlaps with are merged into the first one (the others are set to nil in the array)
  345:     # if NO collectors are found then the region is copied as a new collector
  346:     regions.each do | region |
  347:       collector_found = nil
  348:       region_mask = region[2]
  349:       initial_collector_count.times do | collector_num |
  350:         collector = collectors[collector_num]
  351:         if (collector) then
  352:           collector_mask = collector[0]
  353:           if (collector_mask & region_mask != 0) then
  354:             if (collector_found) then
  355:               collector_found[0] |= collector_mask
  356:               collector_found[1] += collector[1]
  357:               collector_found[2] |= collector[2]
  358:               collectors[collector_num] = nil
  359:             else
  360:               collector_found = collector
  361:               collector[1] += region[1]
  362:               collector[2] |= region_mask
  363:             end
  364:           end
  365:         end
  366:       end
  367:       if (collector_found == nil) then
  368:         collectors.push(Array.new(region))
  369:       end
  370:     end
  371: 
  372:     # check the existing collectors, if any collector overlapped no bits in the region its [2] value will
  373:     # be zero.  The size of any such reaason is tested if it is not a muliple of five true is returned since
  374:     # the board is prunable.  if it is a multiple of five it is removed.
  375:     # Collector that are still active have a new adjacent value [0] set based n the matched bits
  376:     # and have [2] cleared out for the next cycle.
  377:     collectors.length.times do | collector_num |
  378:       collector = collectors[collector_num]
  379:       if (collector) then
  380:         if (collector[2] == 0) then
  381:           return true if (collector[1] % 5 != 0)
  382:           collectors[collector_num] = nil
  383:         else
  384:           # if a collector matches all bits in the row then we can return unprunable early for the
  385:           # follwing reasons:
  386:           #    1) there can be no more unavailable bits bince we fill from the top left downward
  387:           #    2) all previous regions have been closed or joined so only this region can fail
  388:           #    3) this region must be good since there can never be only 1 region that is nuot
  389:           #       a multiple of five
  390:           # this rule only applies when filling normally, so we ignore the rule if we are "slotting"
  391:           # in pieces to see what configurations work for them (the only other time this algorithm is used).
  392:           return false if (collector[2] == 0b11111 && !slotting)
  393:           collector[0] = converter[collector[2]]
  394:           collector[2] = 0
  395:         end
  396:       end
  397:     end
  398: 
  399:     # get rid of all the empty converters for the next round
  400:     collectors.compact!
  401:   end
  402:   return false if (collectors.length <= 1) # 1 collector or less and the region is fine
  403:   collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size
  404: end
  405: 
  406: # creates a region given a row mask.  see prunable for what a "region" is
  407: def create_regions( value )
  408:   regions = []
  409:   cur_region = 0
  410:   5.times do | bit |
  411:     if (value[bit] == 0) then
  412:       cur_region |= 1 << bit
  413:     else
  414:       if (cur_region != 0 ) then
  415:         regions.push( cur_region)
  416:         cur_region = 0;
  417:       end
  418:     end
  419:   end
  420:   regions.push(cur_region) if (cur_region != 0)
  421:   regions
  422: end
  423: 
  424: # find up to the counted number of solutions (or all solutions) and prints the final result
  425: def find_all
  426:   find_top( 1)
  427:   find_top( 0)
  428:   print_results
  429: end
  430: 
  431: # show the board
  432: def print_results
  433:   print "#{@boards_found} solutions found\n\n"
  434:   print_full_board( @min_board)
  435:   print "\n"
  436:   print_full_board( @max_board)
  437:   print "\n"
  438: end
  439: 
  440: # finds solutions.  This special version of the main function is only used for the top level
  441: # the reason for it is basically to force a particular ordering on how the rotations are tested for
  442: # the first piece.  It is called twice, first looking for placements of the odd rotations and then
  443: # looking for placements of the even locations.
  444: #
  445: # WHY?
  446: #   Since any found solution has an inverse we want to maximize finding solutions that are not already found
  447: #   as an inverse.  The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away
  448: #   (an odd number).  Checking even vs odd then produces a higher probability of finding more pieces earlier
  449: #   in the cycle.  We still need to keep checking all the permutations, but our probability of finding one will
  450: #   diminsh over time.  Since we are TOLD how many to search for this lets us exit before checking all pieces
  451: #   this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the
  452: #   maximum number
  453: def find_top( rotation_skip)
  454:   board = blank_board
  455:   (@pieces.length-1).times do
  456:     piece = @pieces.shift
  457:     piece.masks[0].each do | mask, imask, cmask |
  458:       if ((rotation_skip += 1) % 2 == 0) then
  459:         piece.placed = mask
  460:         find( 1, 1, board | mask)
  461:       end
  462:     end
  463:     @pieces.push(piece)
  464:   end
  465:   piece = @pieces.shift
  466:   @pieces.push(piece)
  467: end
  468: 
  469: # the normail find routine, iterates through the available pieces, checks all rotations at the current location
  470: # and adds any boards found.  depth is acheived via recursion.  the overall approach is described
  471: # here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/
  472: # parameters:
  473: #  start_location -- where to start looking for place for the next piece at
  474: #  placed -- number of pieces placed
  475: #  board -- current state of the board
  476: #
  477: # see in-code comments
  478: def find( start_location, placed, board)
  479:   # find the next location to place a piece by looking for an empty bit
  480:   while board[start_location] == 1
  481:     start_location += 1
  482:   end
  483: 
  484:   @pieces.length.times do
  485:     piece = @pieces.shift
  486:     piece.masks[start_location].each do | mask, imask, cmask |
  487:       if ( board & cmask == imask) then
  488:         piece.placed = mask
  489:         if (placed == 9) then
  490:           add_board
  491:         else
  492:           find( start_location + 1, placed + 1, board | mask)
  493:         end
  494:       end
  495:     end
  496:     @pieces.push(piece)
  497:   end
  498: end
  499: 
  500: # print the board
  501: def print_full_board( board_string)
  502:   10.times do | row |
  503:     print " " if (row % 2 == 1)
  504:     5.times do | col |
  505:       print "#{board_string[row*5 + col,1]} "
  506:     end
  507:     print "\n"
  508:   end
  509: end
  510: 
  511: # when a board is found we "draw it" into a string and then flip that string, adding both to