bench/shootout/meteor.ruby

   1 #!/usr/bin/env ruby
   2 #
   3 # The Computer Language Shootout
   4 #   http://shootout.alioth.debian.org
   5 #   contributed by Kevin Barnes (Ruby novice)
   6
   7 def blank_board
   8   0b111111100000100000100000100000100000100000100000100000100000100000
   9 end
  10
  11 def is_even( location)
  12   (location % 12) < 6
  13 end
  14
  15 def create_collector_support
  16     odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]
  17     even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]
  18
  19     all_odds = Array.new(0b100000)
  20     all_evens = Array.new(0b100000)
  21     bit_counts = Array.new(0b100000)
  22     new_regions = Array.new(0b100000)
  23     0.upto(0b11111) do | i |
  24       bit_count = odd = even = 0
  25       0.upto(4) do | bit |
  26         if (i[bit] == 1) then
  27           bit_count += 1
  28           odd |= odd_map[bit]
  29           even |= even_map[bit]
  30         end
  31       end
  32       all_odds[i] = odd
  33       all_evens[i] = even
  34       bit_counts[i] = bit_count
  35       new_regions[i] = create_regions( i)
  36     end
  37
  38     @@converter = []
  39     10.times { | row | @@converter.push((row % 2 == 0) ? all_evens : all_odds) }
  40     @@bit_counts = bit_counts
  41     @@regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }
  42
  43   end
  44
  45 def prunable( board, location, slotting = false)
  46   collectors = []
  47   (location / 6).to_i.upto(9) do | row_on |
  48     regions = @@regions[(board >> (row_on * 6)) & 0b11111 ^ 0b11111]
  49     converter = @@converter[row_on]
  50     initial_collector_count = collectors.length
  51     regions.each do | region |
  52       collector_found = nil
  53       region_mask = region[0]
  54       initial_collector_count.times do | collector_num |
  55         collector = collectors[collector_num]
  56         if (collector) then
  57           collector_mask = collector[0]
  58           if (collector_mask & region_mask != 0) then
  59             if (collector_found) then
  60               collector_found[0] |= collector_mask
  61               collector_found[1] += collector[1]
  62               collector_found[2] |= collector[2]
  63               collectors[collector_num] = nil
  64             else
  65               collector_found = collector
  66               collector[1] += region[1]
  67               collector[2] |= region_mask
  68             end
  69           end
  70         end
  71       end
  72       if (collector_found == nil) then
  73         collectors.push(Array.new(region))
  74       end
  75     end
  76     collectors.length.times do | collector_num |
  77       collector = collectors[collector_num]
  78       if (collector) then
  79         if (collector[2] == 0) then
  80           return true if (collector[1] % 5 != 0)
  81           collectors[collector_num] = nil
  82         else
  83           return false if (collector[2] == 0b11111 && !slotting)
  84           collector[0] = converter[collector[2]]
  85           collector[2] = 0
  86         end
  87       end
  88     end
  89     collectors.compact!
  90   end
  91   return false if (collectors.length <= 1)
  92   collectors.any? { | collector | (collector[1] % 5) != 0 }
  93 end
  94
  95 def as_binary( value)
  96   rtn = ""
  97   5.times do | i |
  98     rtn += "#{value[i]}"
  99   end
 100   rtn
 101 end
 102
 103 def create_regions( value )
 104   regions = []
 105   cur_region = 0
 106   5.times do | bit |
 107     if (value[bit] == 1) then
 108       cur_region |= 1 << bit
 109     else
 110       if (cur_region !=0 ) then
 111         regions.push( cur_region)
 112         cur_region = 0;
 113       end
 114     end
 115   end
 116   regions.push(cur_region) if (cur_region != 0)
 117   regions
 118 end
 119
 120 def print_board( board, padding = "", rows = 10, row_offset = 0)
 121   rows.times do | row |
 122     rtn = padding
 123     rtn = "#{rtn} " if ((row + row_offset) % 2) == 1
 124     6.times do | col |
 125       rtn = "#{rtn}#{board[row*6+col]} "
 126     end
 127     print "#{rtn}\n"
 128   end
 129 end
 130
 131 class Rotation
 132   attr_reader :start_masks
 133
 134   @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }
 135   @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }
 136
 137   def initialize( directions )
 138     values, min = get_values( directions )
 139     @even_offsets, @odd_offsets = normalize_offsets( values, min)
 140
 141     @even_mask = mask_for_offsets( @even_offsets)
 142     @odd_mask = mask_for_offsets( @odd_offsets)
 143
 144     @start_masks = Array.new(60)
 145
 146     0.upto(59) do | offset |
 147       mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)
 148       if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then
 149         @start_masks[offset] = mask
 150       else
 151         @start_masks[offset] = false
 152       end
 153     end
 154   end
 155
 156   def offsets( location)
 157     if is_even( location) then
 158       @even_offsets.collect { | value | value + location }
 159     else
 160       @odd_offsets.collect { | value | value + location }
 161     end
 162   end
 163
 164   def normalize_offsets( values, min)
 165     even_min = is_even(min)
 166     other_min = even_min ? min + 6 : min + 7
 167     other_values = values.collect do | value |
 168       if is_even(value) then
 169         value + 6 - other_min
 170       else
 171         value + 7 - other_min
 172       end
 173     end
 174     values.collect! { | value | value - min }
 175
 176     if even_min then
 177       [values, other_values]
 178     else
 179       [other_values, values]
 180     end
 181   end
 182
 183   def mask_for_offsets( offsets )
 184     mask = 0
 185     offsets.each { | value | mask = mask + ( 1 << value ) }
 186     mask
 187   end
 188
 189   def start_adjust( directions )
 190     south = east = 0;
 191     directions.each do | direction |
 192       east += 1 if ( direction == :sw || direction == :nw || direction == :west )
 193       south += 1 if ( direction == :nw || direction == :ne )
 194     end
 195     [south, east]
 196   end
 197
 198   def get_values ( directions )
 199     south, east = start_adjust(directions)
 200     min = start = south * 6 + east
 201     values = [ start ]
 202     directions.each do | direction |
 203       if (start % 12 >= 6) then
 204         start += @@rotation_odd_adder[direction]
 205       else
 206         start += @@rotation_even_adder[direction]
 207       end
 208       min = start if (start < min)
 209       values += [ start ]
 210     end
 211
 212     if (values.length != 5)
 213       values.uniq!
 214     end
 215
 216     [ values, min ]
 217   end
 218 end
 219
 220 class Piece
 221   attr_reader :rotations, :type, :masks
 222   attr_accessor :placed
 223
 224   @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }
 225   @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }
 226
 227   def initialize( directions, type )
 228     @type = type
 229     @rotations = Array.new();
 230     @map = {}
 231     generate_rotations( directions )
 232     directions.collect! { | value | @@flip_converter[value] }
 233     generate_rotations( directions )
 234
 235     @masks = Array.new();
 236     0.upto(59) do | i |
 237       @masks[i] = @rotations.collect do | rotation |
 238         mask = rotation.start_masks[i]
 239         @map[mask] = [ i, rotation ] if (mask)
 240         mask || nil
 241       end
 242       @masks[i].compact!
 243     end
 244   end
 245
 246   def generate_rotations( directions )
 247     6.times do
 248       rotations.push( Rotation.new(directions))
 249       directions.collect! { | value | @@rotate_converter[value] }
 250     end
 251   end
 252
 253   def fill_array( board_array)
 254     location, rotation = @map[@placed]
 255     rotation.offsets(location).each do | offset |
 256       row, col = offset.divmod(6)
 257       board_array[ row*5 + col ] = @type.to_s
 258     end
 259   end
 260 end
 261
 262 class Processor
 263   attr :pieces, :board
 264
 265   def initialize()
 266     create_collector_support
 267     @pieces = [
 268       Piece.new( [ :east, :east, :east, :se ], 0),
 269       Piece.new( [ :ne, :east, :ne, :nw ], 1),
 270       Piece.new( [ :nw, :ne, :east, :east ], 2),
 271       Piece.new( [ :east, :east, :sw, :se ], 3),
 272       Piece.new( [ :ne, :nw, :se, :east, :se ], 4),
 273       Piece.new( [ :east, :ne, :se, :ne ], 5),
 274       Piece.new( [ :east, :sw, :sw, :se ], 6),
 275       Piece.new( [ :ne, :se, :east, :ne ], 7),
 276       Piece.new( [ :se, :se, :east, :se ], 8),
 277       Piece.new( [ :se, :se, :se, :west ], 9) ];
 278
 279     @all_pieces = Array.new( @pieces)
 280
 281     @min_board = "99999999999999999999999999999999999999999999999999"
 282     @max_board = "00000000000000000000000000000000000000000000000000"
 283     @stop_count = ARGV[0].to_i || 2089
 284     @all_boards = {}
 285     @boards_found = 0
 286   end
 287
 288   def find_all
 289     find_top( 0)
 290     find_top( 1)
 291     print_results
 292   end
 293
 294   def print_results
 295     print "#{@boards_found} solutions found\n\n"
 296     print_full_board( @min_board)
 297     print "\n"
 298     print_full_board( @max_board)
 299     print "\n"
 300   end
 301
 302   def find_top( rotation_skip)
 303     board = blank_board
 304     @pieces.length.times do
 305       piece = @pieces.shift
 306       piece.masks[0].each do | mask |
 307         if ((rotation_skip += 1) % 2 == 0) then
 308           piece.placed = mask
 309           find( 1, 1, board | mask)
 310         end
 311       end
 312       @pieces.push(piece)
 313     end
 314   end
 315
 316   def find( start_location, placed, board)
 317     while board[start_location] == 1
 318       start_location += 1
 319     end
 320
 321     return if (start_location < 28 && prunable( board, start_location))
 322
 323     @pieces.length.times do
 324       piece = @pieces.shift
 325       piece.masks[start_location].each do | mask |
 326         if (mask & board == 0) then
 327           piece.placed = mask
 328           if (placed == 9) then
 329             add_board
 330           else
 331             find( start_location + 1, placed + 1, board | mask)
 332           end
 333         end
 334       end
 335       @pieces.push(piece)
 336     end
 337   end
 338
 339   def print_full_board( board_string)
 340     10.times do | row |
 341       print " " if (row % 2 == 1)
 342       5.times do | col |
 343         print "#{board_string[row*5 + col,1]} "
 344       end
 345       print "\n"
 346     end
 347   end
 348
 349   def add_board
 350     board_array = Array.new(50)
 351     @all_pieces.each do | piece |
 352       piece.fill_array( board_array )
 353     end
 354     start_board = board_string = board_array.join("")
 355     save( board_string)
 356     board_string = flip( board_string)
 357     save( board_string)
 358   end
 359
 360   def flip( board_string)
 361     new_string = ""
 362     50.times do | i |
 363       row, col = i.divmod(5)
 364       new_string += board_string[((9 - row) * 5) + (4 - col), 1]
 365     end
 366     new_string
 367   end
 368
 369   def save( board_string)
 370     if (@all_boards[board_string] == nil) then
 371       @min_board = board_string if (board_string < @min_board)
 372       @max_board = board_string if (board_string > @max_board)
 373       @all_boards.store(board_string,true)
 374       @boards_found += 1
 375
 376       if (@boards_found == @stop_count) then
 377         print_results
 378         exit(0)
 379       end
 380     end
 381   end
 382
 383 end
 384
 385 proc = Processor.new.find_all
 386