From 75feee0968c9345e7ffd2bda9835fcd60b4c0880 Mon Sep 17 00:00:00 2001 From: nobu Date: Fri, 16 Nov 2007 01:30:29 +0000 Subject: * set eol-style. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13944 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- benchmark/bm_so_meteor_contest.rb | 1128 ++++++++++++++++++------------------- 1 file changed, 564 insertions(+), 564 deletions(-) (limited to 'benchmark/bm_so_meteor_contest.rb') diff --git a/benchmark/bm_so_meteor_contest.rb b/benchmark/bm_so_meteor_contest.rb index 5dd720c340..30b99715af 100644 --- a/benchmark/bm_so_meteor_contest.rb +++ b/benchmark/bm_so_meteor_contest.rb @@ -1,564 +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!!! - +#!/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!!! + -- cgit v1.2.3