summaryrefslogtreecommitdiff
path: root/benchmark/bm_so_meteor_contest.rb
diff options
context:
space:
mode:
authorko1 <ko1@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2007-09-28 10:18:53 +0000
committerko1 <ko1@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2007-09-28 10:18:53 +0000
commit30b2cb380e0a8f777a2fc2d736c2ccddf3362fcd (patch)
tree715a72c59e797ee8ca71ce8870db38bf68ed3fd1 /benchmark/bm_so_meteor_contest.rb
parent335fe1ee7bf51534c5f2abd0f359e86721307335 (diff)
* benchmark/driver.rb: fix notations.
* benchmark/bm_loop_whileloop.rb: ditto. * benchmark/bm_loop_whileloop2.rb: ditto. * benchmark/bm_app_uri.rb: added. * benchmark/bm_vm1_ivar_set.rb: ditto. * benchmark/bm_so_binary_trees.rb: added from Computer Language Benchmarks Game (http://shootout.alioth.debian.org/). * benchmark/bm_so_fannkuch.rb: ditto. * benchmark/bm_so_mandelbrot.rb: ditto. * benchmark/bm_so_meteor_contest.rb: ditto. * benchmark/bm_so_nbody.rb: ditto. * benchmark/bm_so_nsieve.rb: ditto. * benchmark/bm_so_nsieve_bits.rb: ditto. * benchmark/bm_so_partial_sums.rb: ditto. * benchmark/bm_so_pidigits.rb: ditto. * benchmark/bm_so_spectralnorm.rb: ditto. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13548 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'benchmark/bm_so_meteor_contest.rb')
-rw-r--r--benchmark/bm_so_meteor_contest.rb564
1 files changed, 564 insertions, 0 deletions
diff --git a/benchmark/bm_so_meteor_contest.rb b/benchmark/bm_so_meteor_contest.rb
new file mode 100644
index 0000000..5dd720c
--- /dev/null
+++ b/benchmark/bm_so_meteor_contest.rb
@@ -0,0 +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!!!
+