diff options
Diffstat (limited to 'benchmark/bm_so_meteor_contest.rb')
| -rwxr-xr-x | benchmark/bm_so_meteor_contest.rb | 563 |
1 files changed, 0 insertions, 563 deletions
diff --git a/benchmark/bm_so_meteor_contest.rb b/benchmark/bm_so_meteor_contest.rb deleted file mode 100755 index 8c136baa6c..0000000000 --- a/benchmark/bm_so_meteor_contest.rb +++ /dev/null @@ -1,563 +0,0 @@ -#!/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 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!!! |