diff options
Diffstat (limited to 'benchmark/so_meteor_contest.yml')
| -rw-r--r-- | benchmark/so_meteor_contest.yml | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/benchmark/so_meteor_contest.yml b/benchmark/so_meteor_contest.yml new file mode 100644 index 0000000000..c35df18f68 --- /dev/null +++ b/benchmark/so_meteor_contest.yml @@ -0,0 +1,567 @@ +prelude: | + #!/usr/bin/env ruby +benchmark: + so_meteor_contest: | + # + # 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 boundaries 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 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 across the rows + (location / 6).to_i.upto(9) do | row_on | + # obtain a set of regions representing the bits of the current 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 multiple 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 + # following 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 achieved 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 noticeable 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!!! +loop_count: 1 |