From 433af16167aec949c6345ad41b78b17c440b4a6d Mon Sep 17 00:00:00 2001
From: k0kubun <k0kubun@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Tue, 10 Jul 2018 13:08:40 +0000
Subject: benchmark: drop all bm_ prefix for legacy driver.rb

benchmark/*.rb is only benchmarks now. We don't need prefixes.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@63928 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
---
 benchmark/so_meteor_contest.rb | 563 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 563 insertions(+)
 create mode 100644 benchmark/so_meteor_contest.rb

(limited to 'benchmark/so_meteor_contest.rb')

diff --git a/benchmark/so_meteor_contest.rb b/benchmark/so_meteor_contest.rb
new file mode 100644
index 0000000000..8c136baa6c
--- /dev/null
+++ b/benchmark/so_meteor_contest.rb
@@ -0,0 +1,563 @@
+#!/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!!!
-- 
cgit v1.2.3