source code
# The Computer Language Benchmarks Game
# http://benchmarksgame.alioth.debian.org
# contributed by Kevin Barnes (Ruby novice)
def blank_board
0b111111100000100000100000100000100000100000100000100000100000100000
end
def is_even( location)
(location % 12) < 6
end
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
def prunable( board, location, slotting = false)
collectors = []
(location / 6).to_i.upto(9) do | row_on |
regions = @@regions[(board >> (row_on * 6)) & 0b11111 ^ 0b11111]
converter = @@converter[row_on]
initial_collector_count = collectors.length
regions.each do | region |
collector_found = nil
region_mask = region[0]
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
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
return false if (collector[2] == 0b11111 && !slotting)
collector[0] = converter[collector[2]]
collector[2] = 0
end
end
end
collectors.compact!
end
return false if (collectors.length <= 1)
collectors.any? { | collector | (collector[1] % 5) != 0 }
end
def as_binary( value)
rtn = ""
5.times do | i |
rtn += "#{value[i]}"
end
rtn
end
def create_regions( value )
regions = []
cur_region = 0
5.times do | bit |
if (value[bit] == 1) 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
def print_board( board, padding = "", rows = 10, row_offset = 0)
rows.times do | row |
rtn = padding
rtn = "#{rtn} " if ((row + row_offset) % 2) == 1
6.times do | col |
rtn = "#{rtn}#{board[row*6+col]} "
end
print "#{rtn}\n"
end
end
class Rotation
attr_reader :start_masks
@@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 )
values, min = get_values( directions )
@even_offsets, @odd_offsets = normalize_offsets( values, min)
@even_mask = mask_for_offsets( @even_offsets)
@odd_mask = mask_for_offsets( @odd_offsets)
@start_masks = Array.new(60)
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
@start_masks[offset] = mask
else
@start_masks[offset] = false
end
end
end
def offsets( location)
if is_even( location) then
@even_offsets.collect { | value | value + location }
else
@odd_offsets.collect { | value | value + location }
end
end
def normalize_offsets( 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
def mask_for_offsets( offsets )
mask = 0
offsets.each { | value | mask = mask + ( 1 << value ) }
mask
end
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, east]
end
def get_values ( directions )
south, east = start_adjust(directions)
min = start = south * 6 + east
values = [ start ]
directions.each do | direction |
if (start % 12 >= 6) then
start += @@rotation_odd_adder[direction]
else
start += @@rotation_even_adder[direction]
end
min = start if (start < min)
values += [ start ]
end
if (values.length != 5)
values.uniq!
end
[ values, min ]
end
end
class Piece
attr_reader :rotations, :type, :masks
attr_accessor :placed
@@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 )
@masks = Array.new();
0.upto(59) do | i |
@masks[i] = @rotations.collect do | rotation |
mask = rotation.start_masks[i]
@map[mask] = [ i, rotation ] if (mask)
mask || nil
end
@masks[i].compact!
end
end
def generate_rotations( directions )
6.times do
rotations.push( Rotation.new(directions))
directions.collect! { | value | @@rotate_converter[value] }
end
end
def fill_array( board_array)
location, rotation = @map[@placed]
rotation.offsets(location).each do | offset |
row, col = offset.divmod(6)
board_array[ row*5 + col ] = @type.to_s
end
end
end
class Processor
attr :pieces, :board
def initialize()
create_collector_support
@pieces = [
Piece.new( [ :east, :east, :east, :se ], 0),
Piece.new( [ :ne, :east, :ne, :nw ], 1),
Piece.new( [ :nw, :ne, :east, :east ], 2),
Piece.new( [ :east, :east, :sw, :se ], 3),
Piece.new( [ :ne, :nw, :se, :east, :se ], 4),
Piece.new( [ :east, :ne, :se, :ne ], 5),
Piece.new( [ :east, :sw, :sw, :se ], 6),
Piece.new( [ :ne, :se, :east, :ne ], 7),
Piece.new( [ :se, :se, :east, :se ], 8),
Piece.new( [ :se, :se, :se, :west ], 9) ];
@all_pieces = Array.new( @pieces)
@min_board = "99999999999999999999999999999999999999999999999999"
@max_board = "00000000000000000000000000000000000000000000000000"
@stop_count = ARGV[0].to_i || 2089
@all_boards = {}
@boards_found = 0
end
def find_all
find_top( 0)
find_top( 1)
print_results
end
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
def find_top( rotation_skip)
board = blank_board
@pieces.length.times do
piece = @pieces.shift
piece.masks[0].each do | mask |
if ((rotation_skip += 1) % 2 == 0) then
piece.placed = mask
find( 1, 1, board | mask)
end
end
@pieces.push(piece)
end
end
def find( start_location, placed, board)
while board[start_location] == 1
start_location += 1
end
return if (start_location < 28 && prunable( board, start_location))
@pieces.length.times do
piece = @pieces.shift
piece.masks[start_location].each do | mask |
if (mask & board == 0) 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
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
def add_board
board_array = Array.new(50)
@all_pieces.each do | piece |
piece.fill_array( board_array )
end
start_board = board_string = board_array.join("")
save( board_string)
board_string = flip( board_string)
save( board_string)
end
def flip( board_string)
new_string = ""
50.times do | i |
row, col = i.divmod(5)
new_string += board_string[((9 - row) * 5) + (4 - col), 1]
end
new_string
end
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
if (@boards_found == @stop_count) then
print_results
exit(0)
end
end
end
end
proc = Processor.new.find_all