#!/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 invalid 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!!!