| blob | 5dd720c340e2da1a504ddd6e4e652d43ec03807f |
1 #!/usr/bin/env ruby\r
2 #\r
3 # The Computer Language Shootout\r
4 # http://shootout.alioth.debian.org\r
5 # contributed by Kevin Barnes (Ruby novice)\r
6 \r
7 # PROGRAM: the main body is at the bottom.\r
8 # 1) read about the problem here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/\r
9 # 2) see how I represent a board as a bitmask by reading the blank_board comments\r
10 # 3) read as your mental paths take you\r
11 \r
12 def print *args\r
13 end\r
14 \r
15 # class to represent all information about a particular rotation of a particular piece\r
16 class Rotation\r
17 # an array (by location) containing a bit mask for how the piece maps at the given location.\r
18 # if the rotation is illegal at that location the mask will contain false\r
19 attr_reader :start_masks\r
20 \r
21 # maps a direction to a relative location. these differ depending on whether it is an even or\r
22 # odd row being mapped from\r
23 @@rotation_even_adder = { :west => -1, :east => 1, :nw => -7, :ne => -6, :sw => 5, :se => 6 }\r
24 @@rotation_odd_adder = { :west => -1, :east => 1, :nw => -6, :ne => -5, :sw => 6, :se => 7 }\r
25 \r
26 def initialize( directions )\r
27 @even_offsets, @odd_offsets = normalize_offsets( get_values( directions ))\r
28 \r
29 @even_mask = mask_for_offsets( @even_offsets)\r
30 @odd_mask = mask_for_offsets( @odd_offsets)\r
31 \r
32 @start_masks = Array.new(60)\r
33 \r
34 # create the rotational masks by placing the base mask at the location and seeing if\r
35 # 1) it overlaps the boundries and 2) it produces a prunable board. if either of these\r
36 # is true the piece cannot be placed\r
37 0.upto(59) do | offset |\r
38 mask = is_even(offset) ? (@even_mask << offset) : (@odd_mask << offset)\r
39 if (blank_board & mask == 0 && !prunable(blank_board | mask, 0, true)) then\r
40 imask = compute_required( mask, offset)\r
41 @start_masks[offset] = [ mask, imask, imask | mask ]\r
42 else\r
43 @start_masks[offset] = false\r
44 end\r
45 end\r
46 end\r
47 \r
48 def compute_required( mask, offset )\r
49 board = blank_board\r
50 0.upto(offset) { | i | board |= 1 << i }\r
51 board |= mask\r
52 return 0 if (!prunable(board | mask, offset))\r
53 board = flood_fill(board,58)\r
54 count = 0\r
55 imask = 0\r
56 0.upto(59) do | i |\r
57 if (board[i] == 0) then\r
58 imask |= (1 << i)\r
59 count += 1\r
60 end\r
61 end\r
62 (count > 0 && count < 5) ? imask : 0\r
63 end\r
64 \r
65 def flood_fill( board, location)\r
66 return board if (board[location] == 1)\r
67 board |= 1 << location\r
68 row, col = location.divmod(6)\r
69 board = flood_fill( board, location - 1) if (col > 0)\r
70 board = flood_fill( board, location + 1) if (col < 4)\r
71 if (row % 2 == 0) then\r
72 board = flood_fill( board, location - 7) if (col > 0 && row > 0)\r
73 board = flood_fill( board, location - 6) if (row > 0)\r
74 board = flood_fill( board, location + 6) if (row < 9)\r
75 board = flood_fill( board, location + 5) if (col > 0 && row < 9)\r
76 else\r
77 board = flood_fill( board, location - 5) if (col < 4 && row > 0)\r
78 board = flood_fill( board, location - 6) if (row > 0)\r
79 board = flood_fill( board, location + 6) if (row < 9)\r
80 board = flood_fill( board, location + 7) if (col < 4 && row < 9)\r
81 end\r
82 board\r
83 end\r
84 \r
85 # given a location, produces a list of relative locations covered by the piece at this rotation\r
86 def offsets( location)\r
87 if is_even( location) then\r
88 @even_offsets.collect { | value | value + location }\r
89 else\r
90 @odd_offsets.collect { | value | value + location }\r
91 end\r
92 end\r
93 \r
94 # returns a set of offsets relative to the top-left most piece of the rotation (by even or odd rows)\r
95 # this is hard to explain. imagine we have this partial board:\r
96 # 0 0 0 0 0 x [positions 0-5]\r
97 # 0 0 1 1 0 x [positions 6-11]\r
98 # 0 0 1 0 0 x [positions 12-17]\r
99 # 0 1 0 0 0 x [positions 18-23]\r
100 # 0 1 0 0 0 x [positions 24-29]\r
101 # 0 0 0 0 0 x [positions 30-35]\r
102 # ...\r
103 # The top-left of the piece is at position 8, the\r
104 # board would be passed as a set of positions (values array) containing [8,9,14,19,25] not necessarily in that\r
105 # sorted order. Since that array starts on an odd row, the offsets for an odd row are: [0,1,6,11,17] obtained\r
106 # by subtracting 8 from everything. Now imagine the piece shifted up and to the right so it's on an even row:\r
107 # 0 0 0 1 1 x [positions 0-5]\r
108 # 0 0 1 0 0 x [positions 6-11]\r
109 # 0 0 1 0 0 x [positions 12-17]\r
110 # 0 1 0 0 0 x [positions 18-23]\r
111 # 0 0 0 0 0 x [positions 24-29]\r
112 # 0 0 0 0 0 x [positions 30-35]\r
113 # ...\r
114 # Now the positions are [3,4,8,14,19] which after subtracting the lowest value (3) gives [0,1,5,11,16] thus, the\r
115 # offsets for this particular piece are (in even, odd order) [0,1,5,11,16],[0,1,6,11,17] which is what\r
116 # this function would return\r
117 def normalize_offsets( values)\r
118 min = values.min\r
119 even_min = is_even(min)\r
120 other_min = even_min ? min + 6 : min + 7\r
121 other_values = values.collect do | value |\r
122 if is_even(value) then\r
123 value + 6 - other_min\r
124 else\r
125 value + 7 - other_min\r
126 end\r
127 end\r
128 values.collect! { | value | value - min }\r
129 \r
130 if even_min then\r
131 [values, other_values]\r
132 else\r
133 [other_values, values]\r
134 end\r
135 end\r
136 \r
137 # produce a bitmask representation of an array of offset locations\r
138 def mask_for_offsets( offsets )\r
139 mask = 0\r
140 offsets.each { | value | mask = mask + ( 1 << value ) }\r
141 mask\r
142 end\r
143 \r
144 # finds a "safe" position that a position as described by a list of directions can be placed\r
145 # without falling off any edge of the board. the values returned a location to place the first piece\r
146 # at so it will fit after making the described moves\r
147 def start_adjust( directions )\r
148 south = east = 0;\r
149 directions.each do | direction |\r
150 east += 1 if ( direction == :sw || direction == :nw || direction == :west )\r
151 south += 1 if ( direction == :nw || direction == :ne )\r
152 end\r
153 south * 6 + east\r
154 end\r
155 \r
156 # given a set of directions places the piece (as defined by a set of directions) on the board at\r
157 # a location that will not take it off the edge\r
158 def get_values ( directions )\r
159 start = start_adjust(directions)\r
160 values = [ start ]\r
161 directions.each do | direction |\r
162 if (start % 12 >= 6) then\r
163 start += @@rotation_odd_adder[direction]\r
164 else\r
165 start += @@rotation_even_adder[direction]\r
166 end\r
167 values += [ start ]\r
168 end\r
169 \r
170 # some moves take you back to an existing location, we'll strip duplicates\r
171 values.uniq\r
172 end\r
173 end\r
174 \r
175 # describes a piece and caches information about its rotations to as to be efficient for iteration\r
176 # ATTRIBUTES:\r
177 # rotations -- all the rotations of the piece\r
178 # type -- a numeic "name" of the piece\r
179 # masks -- an array by location of all legal rotational masks (a n inner array) for that location\r
180 # placed -- the mask that this piece was last placed at (not a location, but the actual mask used)\r
181 class Piece\r
182 attr_reader :rotations, :type, :masks\r
183 attr_accessor :placed\r
184 \r
185 # transform hashes that change one direction into another when you either flip or rotate a set of directions\r
186 @@flip_converter = { :west => :west, :east => :east, :nw => :sw, :ne => :se, :sw => :nw, :se => :ne }\r
187 @@rotate_converter = { :west => :nw, :east => :se, :nw => :ne, :ne => :east, :sw => :west, :se => :sw }\r
188 \r
189 def initialize( directions, type )\r
190 @type = type\r
191 @rotations = Array.new();\r
192 @map = {}\r
193 \r
194 generate_rotations( directions )\r
195 directions.collect! { | value | @@flip_converter[value] }\r
196 generate_rotations( directions )\r
197 \r
198 # creates the masks AND a map that returns [location, rotation] for any given mask\r
199 # this is used when a board is found and we want to draw it, otherwise the map is unused\r
200 @masks = Array.new();\r
201 0.upto(59) do | i |\r
202 even = true\r
203 @masks[i] = @rotations.collect do | rotation |\r
204 mask = rotation.start_masks[i]\r
205 @map[mask[0]] = [ i, rotation ] if (mask)\r
206 mask || nil\r
207 end\r
208 @masks[i].compact!\r
209 end\r
210 end\r
211 \r
212 # rotates a set of directions through all six angles and adds a Rotation to the list for each one\r
213 def generate_rotations( directions )\r
214 6.times do\r
215 rotations.push( Rotation.new(directions))\r
216 directions.collect! { | value | @@rotate_converter[value] }\r
217 end\r
218 end\r
219 \r
220 # given a board string, adds this piece to the board at whatever location/rotation\r
221 # important: the outbound board string is 5 wide, the normal location notation is six wide (padded)\r
222 def fill_string( board_string)\r
223 location, rotation = @map[@placed]\r
224 rotation.offsets(location).each do | offset |\r
225 row, col = offset.divmod(6)\r
226 board_string[ row*5 + col, 1 ] = @type.to_s\r
227 end\r
228 end\r
229 end\r
230 \r
231 # a blank bit board having this form:\r
232 #\r
233 # 0 0 0 0 0 1\r
234 # 0 0 0 0 0 1\r
235 # 0 0 0 0 0 1\r
236 # 0 0 0 0 0 1\r
237 # 0 0 0 0 0 1\r
238 # 0 0 0 0 0 1\r
239 # 0 0 0 0 0 1\r
240 # 0 0 0 0 0 1\r
241 # 0 0 0 0 0 1\r
242 # 0 0 0 0 0 1\r
243 # 1 1 1 1 1 1\r
244 #\r
245 # where left lest significant bit is the top left and the most significant is the lower right\r
246 # the actual board only consists of the 0 places, the 1 places are blockers to keep things from running\r
247 # off the edges or bottom\r
248 def blank_board\r
249 0b111111100000100000100000100000100000100000100000100000100000100000\r
250 end\r
251 \r
252 def full_board\r
253 0b111111111111111111111111111111111111111111111111111111111111111111\r
254 end\r
255 \r
256 # determines if a location (bit position) is in an even row\r
257 def is_even( location)\r
258 (location % 12) < 6\r
259 end\r
260 \r
261 # support function that create three utility maps:\r
262 # $converter -- for each row an array that maps a five bit row (via array mapping)\r
263 # to the a a five bit representation of the bits below it\r
264 # $bit_count -- maps a five bit row (via array mapping) to the number of 1s in the row\r
265 # @@new_regions -- maps a five bit row (via array mapping) to an array of "region" arrays\r
266 # a region array has three values the first is a mask of bits in the region,\r
267 # the second is the count of those bits and the third is identical to the first\r
268 # examples:\r
269 # 0b10010 => [ 0b01100, 2, 0b01100 ], [ 0b00001, 1, 0b00001]\r
270 # 0b01010 => [ 0b10000, 1, 0b10000 ], [ 0b00100, 1, 0b00100 ], [ 0b00001, 1, 0b00001]\r
271 # 0b10001 => [ 0b01110, 3, 0b01110 ]\r
272 def create_collector_support\r
273 odd_map = [0b11, 0b110, 0b1100, 0b11000, 0b10000]\r
274 even_map = [0b1, 0b11, 0b110, 0b1100, 0b11000]\r
275 \r
276 all_odds = Array.new(0b100000)\r
277 all_evens = Array.new(0b100000)\r
278 bit_counts = Array.new(0b100000)\r
279 new_regions = Array.new(0b100000)\r
280 0.upto(0b11111) do | i |\r
281 bit_count = odd = even = 0\r
282 0.upto(4) do | bit |\r
283 if (i[bit] == 1) then\r
284 bit_count += 1\r
285 odd |= odd_map[bit]\r
286 even |= even_map[bit]\r
287 end\r
288 end\r
289 all_odds[i] = odd\r
290 all_evens[i] = even\r
291 bit_counts[i] = bit_count\r
292 new_regions[i] = create_regions( i)\r
293 end\r
294 \r
295 $converter = []\r
296 10.times { | row | $converter.push((row % 2 == 0) ? all_evens : all_odds) }\r
297 $bit_counts = bit_counts\r
298 $regions = new_regions.collect { | set | set.collect { | value | [ value, bit_counts[value], value] } }\r
299 end\r
300 \r
301 # determines if a board is punable, meaning that there is no possibility that it\r
302 # can be filled up with pieces. A board is prunable if there is a grouping of unfilled spaces\r
303 # that are not a multiple of five. The following board is an example of a prunable board:\r
304 # 0 0 1 0 0\r
305 # 0 1 0 0 0\r
306 # 1 1 0 0 0\r
307 # 0 1 0 0 0\r
308 # 0 0 0 0 0\r
309 # ...\r
310 #\r
311 # This board is prunable because the top left corner is only 3 bits in area, no piece will ever fit it\r
312 # parameters:\r
313 # board -- an initial bit board (6 bit padded rows, see blank_board for format)\r
314 # location -- starting location, everything above and to the left is already full\r
315 # slotting -- set to true only when testing initial pieces, when filling normally\r
316 # additional assumptions are possible\r
317 #\r
318 # Algorithm:\r
319 # The algorithm starts at the top row (as determined by location) and iterates a row at a time\r
320 # maintainng counts of active open areas (kept in the collector array) each collector contains\r
321 # three values at the start of an iteration:\r
322 # 0: mask of bits that would be adjacent to the collector in this row\r
323 # 1: the number of bits collected so far\r
324 # 2: a scratch space starting as zero, but used during the computation to represent\r
325 # the empty bits in the new row that are adjacent (position 0)\r
326 # The exact procedure is described in-code\r
327 def prunable( board, location, slotting = false)\r
328 collectors = []\r
329 # loop accross the rows\r
330 (location / 6).to_i.upto(9) do | row_on |\r
331 # obtain a set of regions representing the bits of the curent row.\r
332 regions = $regions[(board >> (row_on * 6)) & 0b11111]\r
333 converter = $converter[row_on]\r
334 \r
335 # track the number of collectors at the start of the cycle so that\r
336 # we don't compute against newly created collectors, only existing collectors\r
337 initial_collector_count = collectors.length\r
338 \r
339 # loop against the regions. For each region of the row\r
340 # we will see if it connects to one or more existing collectors.\r
341 # if it connects to 1 collector, the bits from the region are added to the\r
342 # bits of the collector and the mask is placed in collector[2]\r
343 # If the region overlaps more than one collector then all the collectors\r
344 # it overlaps with are merged into the first one (the others are set to nil in the array)\r
345 # if NO collectors are found then the region is copied as a new collector\r
346 regions.each do | region |\r
347 collector_found = nil\r
348 region_mask = region[2]\r
349 initial_collector_count.times do | collector_num |\r
350 collector = collectors[collector_num]\r
351 if (collector) then\r
352 collector_mask = collector[0]\r
353 if (collector_mask & region_mask != 0) then\r
354 if (collector_found) then\r
355 collector_found[0] |= collector_mask\r
356 collector_found[1] += collector[1]\r
357 collector_found[2] |= collector[2]\r
358 collectors[collector_num] = nil\r
359 else\r
360 collector_found = collector\r
361 collector[1] += region[1]\r
362 collector[2] |= region_mask\r
363 end\r
364 end\r
365 end\r
366 end\r
367 if (collector_found == nil) then\r
368 collectors.push(Array.new(region))\r
369 end\r
370 end\r
371 \r
372 # check the existing collectors, if any collector overlapped no bits in the region its [2] value will\r
373 # be zero. The size of any such reaason is tested if it is not a muliple of five true is returned since\r
374 # the board is prunable. if it is a multiple of five it is removed.\r
375 # Collector that are still active have a new adjacent value [0] set based n the matched bits\r
376 # and have [2] cleared out for the next cycle.\r
377 collectors.length.times do | collector_num |\r
378 collector = collectors[collector_num]\r
379 if (collector) then\r
380 if (collector[2] == 0) then\r
381 return true if (collector[1] % 5 != 0)\r
382 collectors[collector_num] = nil\r
383 else\r
384 # if a collector matches all bits in the row then we can return unprunable early for the\r
385 # follwing reasons:\r
386 # 1) there can be no more unavailable bits bince we fill from the top left downward\r
387 # 2) all previous regions have been closed or joined so only this region can fail\r
388 # 3) this region must be good since there can never be only 1 region that is nuot\r
389 # a multiple of five\r
390 # this rule only applies when filling normally, so we ignore the rule if we are "slotting"\r
391 # in pieces to see what configurations work for them (the only other time this algorithm is used).\r
392 return false if (collector[2] == 0b11111 && !slotting)\r
393 collector[0] = converter[collector[2]]\r
394 collector[2] = 0\r
395 end\r
396 end\r
397 end\r
398 \r
399 # get rid of all the empty converters for the next round\r
400 collectors.compact!\r
401 end\r
402 return false if (collectors.length <= 1) # 1 collector or less and the region is fine\r
403 collectors.any? { | collector | (collector[1] % 5) != 0 } # more than 1 and we test them all for bad size\r
404 end\r
405 \r
406 # creates a region given a row mask. see prunable for what a "region" is\r
407 def create_regions( value )\r
408 regions = []\r
409 cur_region = 0\r
410 5.times do | bit |\r
411 if (value[bit] == 0) then\r
412 cur_region |= 1 << bit\r
413 else\r
414 if (cur_region != 0 ) then\r
415 regions.push( cur_region)\r
416 cur_region = 0;\r
417 end\r
418 end\r
419 end\r
420 regions.push(cur_region) if (cur_region != 0)\r
421 regions\r
422 end\r
423 \r
424 # find up to the counted number of solutions (or all solutions) and prints the final result\r
425 def find_all\r
426 find_top( 1)\r
427 find_top( 0)\r
428 print_results\r
429 end\r
430 \r
431 # show the board\r
432 def print_results\r
433 print "#{@boards_found} solutions found\n\n"\r
434 print_full_board( @min_board)\r
435 print "\n"\r
436 print_full_board( @max_board)\r
437 print "\n"\r
438 end\r
439 \r
440 # finds solutions. This special version of the main function is only used for the top level\r
441 # the reason for it is basically to force a particular ordering on how the rotations are tested for\r
442 # the first piece. It is called twice, first looking for placements of the odd rotations and then\r
443 # looking for placements of the even locations.\r
444 #\r
445 # WHY?\r
446 # Since any found solution has an inverse we want to maximize finding solutions that are not already found\r
447 # as an inverse. The inverse will ALWAYS be 3 one of the piece configurations that is exactly 3 rotations away\r
448 # (an odd number). Checking even vs odd then produces a higher probability of finding more pieces earlier\r
449 # in the cycle. We still need to keep checking all the permutations, but our probability of finding one will\r
450 # diminsh over time. Since we are TOLD how many to search for this lets us exit before checking all pieces\r
451 # this bennifit is very great when seeking small numbers of solutions and is 0 when looking for more than the\r
452 # maximum number\r
453 def find_top( rotation_skip)\r
454 board = blank_board\r
455 (@pieces.length-1).times do\r
456 piece = @pieces.shift\r
457 piece.masks[0].each do | mask, imask, cmask |\r
458 if ((rotation_skip += 1) % 2 == 0) then\r
459 piece.placed = mask\r
460 find( 1, 1, board | mask)\r
461 end\r
462 end\r
463 @pieces.push(piece)\r
464 end\r
465 piece = @pieces.shift\r
466 @pieces.push(piece)\r
467 end\r
468 \r
469 # the normail find routine, iterates through the available pieces, checks all rotations at the current location\r
470 # and adds any boards found. depth is acheived via recursion. the overall approach is described\r
471 # here: http://www-128.ibm.com/developerworks/java/library/j-javaopt/\r
472 # parameters:\r
473 # start_location -- where to start looking for place for the next piece at\r
474 # placed -- number of pieces placed\r
475 # board -- current state of the board\r
476 #\r
477 # see in-code comments\r
478 def find( start_location, placed, board)\r
479 # find the next location to place a piece by looking for an empty bit\r
480 while board[start_location] == 1\r
481 start_location += 1\r
482 end\r
483 \r
484 @pieces.length.times do\r
485 piece = @pieces.shift\r
486 piece.masks[start_location].each do | mask, imask, cmask |\r
487 if ( board & cmask == imask) then\r
488 piece.placed = mask\r
489 if (placed == 9) then\r
490 add_board\r
491 else\r
492 find( start_location + 1, placed + 1, board | mask)\r
493 end\r
494 end\r
495 end\r
496 @pieces.push(piece)\r
497 end\r
498 end\r
499 \r
500 # print the board\r
501 def print_full_board( board_string)\r
502 10.times do | row |\r
503 print " " if (row % 2 == 1)\r
504 5.times do | col |\r
505 print "#{board_string[row*5 + col,1]} "\r
506 end\r
507 print "\n"\r
508 end\r
509 end\r
510 \r
511 # when a board is found we "draw it" into a string and then flip that string, adding both to\r
512 # the list (hash) of solutions if they are unique.\r
513 def add_board\r
514 board_string = "99999999999999999999999999999999999999999999999999"\r
515 @all_pieces.each { | piece | piece.fill_string( board_string ) }\r
516 save( board_string)\r
517 save( board_string.reverse)\r
518 end\r
519 \r
520 # adds a board string to the list (if new) and updates the current best/worst board\r
521 def save( board_string)\r
522 if (@all_boards[board_string] == nil) then\r
523 @min_board = board_string if (board_string < @min_board)\r
524 @max_board = board_string if (board_string > @max_board)\r
525 @all_boards.store(board_string,true)\r
526 @boards_found += 1\r
527 \r
528 # the exit motif is a time saver. Ideally the function should return, but those tests\r
529 # take noticable time (performance).\r
530 if (@boards_found == @stop_count) then\r
531 print_results\r
532 exit(0)\r
533 end\r
534 end\r
535 end\r
536 \r
537 \r
538 ##\r
539 ## MAIN BODY :)\r
540 ##\r
541 create_collector_support\r
542 @pieces = [\r
543 Piece.new( [ :nw, :ne, :east, :east ], 2),\r
544 Piece.new( [ :ne, :se, :east, :ne ], 7),\r
545 Piece.new( [ :ne, :east, :ne, :nw ], 1),\r
546 Piece.new( [ :east, :sw, :sw, :se ], 6),\r
547 Piece.new( [ :east, :ne, :se, :ne ], 5),\r
548 Piece.new( [ :east, :east, :east, :se ], 0),\r
549 Piece.new( [ :ne, :nw, :se, :east, :se ], 4),\r
550 Piece.new( [ :se, :se, :se, :west ], 9),\r
551 Piece.new( [ :se, :se, :east, :se ], 8),\r
552 Piece.new( [ :east, :east, :sw, :se ], 3)\r
553 ];\r
554 \r
555 @all_pieces = Array.new( @pieces)\r
556 \r
557 @min_board = "99999999999999999999999999999999999999999999999999"\r
558 @max_board = "00000000000000000000000000000000000000000000000000"\r
559 @stop_count = ARGV[0].to_i || 2089\r
560 @all_boards = {}\r
561 @boards_found = 0\r
562 \r
563 find_all ######## DO IT!!!\r
564 \r