1 /* 2 Redistribution and use in source and binary forms, with or without 3 modification, are permitted provided that the following conditions are met: 4 5 * Redistributions of source code must retain the above copyright 6 notice, this list of conditions and the following disclaimer. 7 8 * Redistributions in binary form must reproduce the above copyright 9 notice, this list of conditions and the following disclaimer in the 10 documentation and/or other materials provided with the distribution. 11 12 * Neither the name of "The Computer Language Benchmarks Game" nor the 13 name of "The Computer Language Shootout Benchmarks" nor the names of 14 its contributors may be used to endorse or promote products derived 15 from this software without specific prior written permission. 16 17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 /* The Computer Language Benchmarks Game 31 * http://shootout.alioth.debian.org/ 32 * 33 * contributed by The Go Authors. 34 * based on meteor-contest.c by Christian Vosteen 35 */ 36 37 package main 38 39 import ( 40 "flag" 41 "fmt" 42 ) 43 44 var max_solutions = flag.Int("n", 2100, "maximum number of solutions") 45 46 func boolInt(b bool) int8 { 47 if b { 48 return 1 49 } 50 return 0 51 } 52 53 /* The board is a 50 cell hexagonal pattern. For . . . . . 54 * maximum speed the board will be implemented as . . . . . 55 * 50 bits, which will fit into a 64 bit long long . . . . . 56 * int. . . . . . 57 * . . . . . 58 * I will represent 0's as empty cells and 1's . . . . . 59 * as full cells. . . . . . 60 * . . . . . 61 * . . . . . 62 * . . . . . 63 */ 64 65 var board uint64 = 0xFFFC000000000000 66 67 /* The puzzle pieces must be specified by the path followed 68 * from one end to the other along 12 hexagonal directions. 69 * 70 * Piece 0 Piece 1 Piece 2 Piece 3 Piece 4 71 * 72 * O O O O O O O O O O O O O O O 73 * O O O O O O O 74 * O O O 75 * 76 * Piece 5 Piece 6 Piece 7 Piece 8 Piece 9 77 * 78 * O O O O O O O O O O O O O 79 * O O O O O O O O O 80 * O O O 81 * 82 * I had to make it 12 directions because I wanted all of the 83 * piece definitions to fit into the same size arrays. It is 84 * not possible to define piece 4 in terms of the 6 cardinal 85 * directions in 4 moves. 86 */ 87 88 const ( 89 E = iota 90 ESE 91 SE 92 S 93 SW 94 WSW 95 W 96 WNW 97 NW 98 N 99 NE 100 ENE 101 PIVOT 102 ) 103 104 var piece_def = [10][4]int8{ 105 [4]int8{E, E, E, SE}, 106 [4]int8{SE, E, NE, E}, 107 [4]int8{E, E, SE, SW}, 108 [4]int8{E, E, SW, SE}, 109 [4]int8{SE, E, NE, S}, 110 [4]int8{E, E, SW, E}, 111 [4]int8{E, SE, SE, NE}, 112 [4]int8{E, SE, SE, W}, 113 [4]int8{E, SE, E, E}, 114 [4]int8{E, E, E, SW}, 115 } 116 117 /* To minimize the amount of work done in the recursive solve function below, 118 * I'm going to allocate enough space for all legal rotations of each piece 119 * at each position on the board. That's 10 pieces x 50 board positions x 120 * 12 rotations. However, not all 12 rotations will fit on every cell, so 121 * I'll have to keep count of the actual number that do. 122 * The pieces are going to be unsigned long long ints just like the board so 123 * they can be bitwise-anded with the board to determine if they fit. 124 * I'm also going to record the next possible open cell for each piece and 125 * location to reduce the burden on the solve function. 126 */ 127 var ( 128 pieces [10][50][12]uint64 129 piece_counts [10][50]int 130 next_cell [10][50][12]int8 131 ) 132 133 /* Returns the direction rotated 60 degrees clockwise */ 134 func rotate(dir int8) int8 { return (dir + 2) % PIVOT } 135 136 /* Returns the direction flipped on the horizontal axis */ 137 func flip(dir int8) int8 { return (PIVOT - dir) % PIVOT } 138 139 /* Returns the new cell index from the specified cell in the 140 * specified direction. The index is only valid if the 141 * starting cell and direction have been checked by the 142 * out_of_bounds function first. 143 */ 144 func shift(cell, dir int8) int8 { 145 switch dir { 146 case E: 147 return cell + 1 148 case ESE: 149 if ((cell / 5) % 2) != 0 { 150 return cell + 7 151 } else { 152 return cell + 6 153 } 154 case SE: 155 if ((cell / 5) % 2) != 0 { 156 return cell + 6 157 } else { 158 return cell + 5 159 } 160 case S: 161 return cell + 10 162 case SW: 163 if ((cell / 5) % 2) != 0 { 164 return cell + 5 165 } else { 166 return cell + 4 167 } 168 case WSW: 169 if ((cell / 5) % 2) != 0 { 170 return cell + 4 171 } else { 172 return cell + 3 173 } 174 case W: 175 return cell - 1 176 case WNW: 177 if ((cell / 5) % 2) != 0 { 178 return cell - 6 179 } else { 180 return cell - 7 181 } 182 case NW: 183 if ((cell / 5) % 2) != 0 { 184 return cell - 5 185 } else { 186 return cell - 6 187 } 188 case N: 189 return cell - 10 190 case NE: 191 if ((cell / 5) % 2) != 0 { 192 return cell - 4 193 } else { 194 return cell - 5 195 } 196 case ENE: 197 if ((cell / 5) % 2) != 0 { 198 return cell - 3 199 } else { 200 return cell - 4 201 } 202 } 203 return cell 204 } 205 206 /* Returns wether the specified cell and direction will land outside 207 * of the board. Used to determine if a piece is at a legal board 208 * location or not. 209 */ 210 func out_of_bounds(cell, dir int8) bool { 211 switch dir { 212 case E: 213 return cell%5 == 4 214 case ESE: 215 i := cell % 10 216 return i == 4 || i == 8 || i == 9 || cell >= 45 217 case SE: 218 return cell%10 == 9 || cell >= 45 219 case S: 220 return cell >= 40 221 case SW: 222 return cell%10 == 0 || cell >= 45 223 case WSW: 224 i := cell % 10 225 return i == 0 || i == 1 || i == 5 || cell >= 45 226 case W: 227 return cell%5 == 0 228 case WNW: 229 i := cell % 10 230 return i == 0 || i == 1 || i == 5 || cell < 5 231 case NW: 232 return cell%10 == 0 || cell < 5 233 case N: 234 return cell < 10 235 case NE: 236 return cell%10 == 9 || cell < 5 237 case ENE: 238 i := cell % 10 239 return i == 4 || i == 8 || i == 9 || cell < 5 240 } 241 return false 242 } 243 244 /* Rotate a piece 60 degrees clockwise */ 245 func rotate_piece(piece int) { 246 for i := 0; i < 4; i++ { 247 piece_def[piece][i] = rotate(piece_def[piece][i]) 248 } 249 } 250 251 /* Flip a piece along the horizontal axis */ 252 func flip_piece(piece int) { 253 for i := 0; i < 4; i++ { 254 piece_def[piece][i] = flip(piece_def[piece][i]) 255 } 256 } 257 258 /* Convenience function to quickly calculate all of the indices for a piece */ 259 func calc_cell_indices(cell []int8, piece int, index int8) { 260 cell[0] = index 261 for i := 1; i < 5; i++ { 262 cell[i] = shift(cell[i-1], piece_def[piece][i-1]) 263 } 264 } 265 266 /* Convenience function to quickly calculate if a piece fits on the board */ 267 func cells_fit_on_board(cell []int8, piece int) bool { 268 return !out_of_bounds(cell[0], piece_def[piece][0]) && 269 !out_of_bounds(cell[1], piece_def[piece][1]) && 270 !out_of_bounds(cell[2], piece_def[piece][2]) && 271 !out_of_bounds(cell[3], piece_def[piece][3]) 272 } 273 274 /* Returns the lowest index of the cells of a piece. 275 * I use the lowest index that a piece occupies as the index for looking up 276 * the piece in the solve function. 277 */ 278 func minimum_of_cells(cell []int8) int8 { 279 minimum := cell[0] 280 for i := 1; i < 5; i++ { 281 if cell[i] < minimum { 282 minimum = cell[i] 283 } 284 } 285 return minimum 286 } 287 288 /* Calculate the lowest possible open cell if the piece is placed on the board. 289 * Used to later reduce the amount of time searching for open cells in the 290 * solve function. 291 */ 292 func first_empty_cell(cell []int8, minimum int8) int8 { 293 first_empty := minimum 294 for first_empty == cell[0] || first_empty == cell[1] || 295 first_empty == cell[2] || first_empty == cell[3] || 296 first_empty == cell[4] { 297 first_empty++ 298 } 299 return first_empty 300 } 301 302 /* Generate the unsigned long long int that will later be anded with the 303 * board to determine if it fits. 304 */ 305 func bitmask_from_cells(cell []int8) uint64 { 306 var piece_mask uint64 307 for i := 0; i < 5; i++ { 308 piece_mask |= 1 << uint(cell[i]) 309 } 310 return piece_mask 311 } 312 313 /* Record the piece and other important information in arrays that will 314 * later be used by the solve function. 315 */ 316 func record_piece(piece int, minimum int8, first_empty int8, piece_mask uint64) { 317 pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask 318 next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty 319 piece_counts[piece][minimum]++ 320 } 321 322 /* Fill the entire board going cell by cell. If any cells are "trapped" 323 * they will be left alone. 324 */ 325 func fill_contiguous_space(board []int8, index int8) { 326 if board[index] == 1 { 327 return 328 } 329 board[index] = 1 330 if !out_of_bounds(index, E) { 331 fill_contiguous_space(board, shift(index, E)) 332 } 333 if !out_of_bounds(index, SE) { 334 fill_contiguous_space(board, shift(index, SE)) 335 } 336 if !out_of_bounds(index, SW) { 337 fill_contiguous_space(board, shift(index, SW)) 338 } 339 if !out_of_bounds(index, W) { 340 fill_contiguous_space(board, shift(index, W)) 341 } 342 if !out_of_bounds(index, NW) { 343 fill_contiguous_space(board, shift(index, NW)) 344 } 345 if !out_of_bounds(index, NE) { 346 fill_contiguous_space(board, shift(index, NE)) 347 } 348 } 349 350 /* To thin the number of pieces, I calculate if any of them trap any empty 351 * cells at the edges. There are only a handful of exceptions where the 352 * the board can be solved with the trapped cells. For example: piece 8 can 353 * trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0 354 * can split the board in half where both halves are viable. 355 */ 356 func has_island(cell []int8, piece int) bool { 357 temp_board := make([]int8, 50) 358 var i int 359 for i = 0; i < 5; i++ { 360 temp_board[cell[i]] = 1 361 } 362 i = 49 363 for temp_board[i] == 1 { 364 i-- 365 } 366 fill_contiguous_space(temp_board, int8(i)) 367 c := 0 368 for i = 0; i < 50; i++ { 369 if temp_board[i] == 0 { 370 c++ 371 } 372 } 373 if c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) || 374 (c%5 == 0 && piece == 0) { 375 return false 376 } 377 return true 378 } 379 380 /* Calculate all six rotations of the specified piece at the specified index. 381 * We calculate only half of piece 3's rotations. This is because any solution 382 * found has an identical solution rotated 180 degrees. Thus we can reduce the 383 * number of attempted pieces in the solve algorithm by not including the 180- 384 * degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave 385 * me the best time ;) 386 */ 387 func calc_six_rotations(piece, index int) { 388 cell := make([]int8, 5) 389 for rotation := 0; rotation < 6; rotation++ { 390 if piece != 3 || rotation < 3 { 391 calc_cell_indices(cell, piece, int8(index)) 392 if cells_fit_on_board(cell, piece) && !has_island(cell, piece) { 393 minimum := minimum_of_cells(cell) 394 first_empty := first_empty_cell(cell, minimum) 395 piece_mask := bitmask_from_cells(cell) 396 record_piece(piece, minimum, first_empty, piece_mask) 397 } 398 } 399 rotate_piece(piece) 400 } 401 } 402 403 /* Calculate every legal rotation for each piece at each board location. */ 404 func calc_pieces() { 405 for piece := 0; piece < 10; piece++ { 406 for index := 0; index < 50; index++ { 407 calc_six_rotations(piece, index) 408 flip_piece(piece) 409 calc_six_rotations(piece, index) 410 } 411 } 412 } 413 414 /* Calculate all 32 possible states for a 5-bit row and all rows that will 415 * create islands that follow any of the 32 possible rows. These pre- 416 * calculated 5-bit rows will be used to find islands in a partially solved 417 * board in the solve function. 418 */ 419 const ( 420 ROW_MASK = 0x1F 421 TRIPLE_MASK = 0x7FFF 422 ) 423 424 var ( 425 all_rows = [32]int8{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 426 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 427 } 428 bad_even_rows [32][32]int8 429 bad_odd_rows [32][32]int8 430 bad_even_triple [32768]int8 431 bad_odd_triple [32768]int8 432 ) 433 434 func rows_bad(row1, row2 int8, even bool) int8 { 435 /* even is referring to row1 */ 436 var row2_shift int8 437 /* Test for blockages at same index and shifted index */ 438 if even { 439 row2_shift = ((row2 << 1) & ROW_MASK) | 0x01 440 } else { 441 row2_shift = (row2 >> 1) | 0x10 442 } 443 block := ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift) 444 /* Test for groups of 0's */ 445 in_zeroes := false 446 group_okay := false 447 for i := uint8(0); i < 5; i++ { 448 if row1&(1<<i) != 0 { 449 if in_zeroes { 450 if !group_okay { 451 return 1 452 } 453 in_zeroes = false 454 group_okay = false 455 } 456 } else { 457 if !in_zeroes { 458 in_zeroes = true 459 } 460 if (block & (1 << i)) == 0 { 461 group_okay = true 462 } 463 } 464 } 465 if in_zeroes { 466 return boolInt(!group_okay) 467 } 468 return 0 469 } 470 471 /* Check for cases where three rows checked sequentially cause a false 472 * positive. One scenario is when 5 cells may be surrounded where piece 5 473 * or 7 can fit. The other scenario is when piece 2 creates a hook shape. 474 */ 475 func triple_is_okay(row1, row2, row3 int, even bool) bool { 476 if even { 477 /* There are four cases: 478 * row1: 00011 00001 11001 10101 479 * row2: 01011 00101 10001 10001 480 * row3: 011?? 00110 ????? ????? 481 */ 482 return ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) || 483 ((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) || 484 ((row1 == 0x19) && (row2 == 0x11)) || 485 ((row1 == 0x15) && (row2 == 0x11)) 486 } 487 /* There are two cases: 488 * row1: 10011 10101 489 * row2: 10001 10001 490 * row3: ????? ????? 491 */ 492 return ((row1 == 0x13) && (row2 == 0x11)) || 493 ((row1 == 0x15) && (row2 == 0x11)) 494 } 495 496 func calc_rows() { 497 for row1 := int8(0); row1 < 32; row1++ { 498 for row2 := int8(0); row2 < 32; row2++ { 499 bad_even_rows[row1][row2] = rows_bad(row1, row2, true) 500 bad_odd_rows[row1][row2] = rows_bad(row1, row2, false) 501 } 502 } 503 for row1 := 0; row1 < 32; row1++ { 504 for row2 := 0; row2 < 32; row2++ { 505 for row3 := 0; row3 < 32; row3++ { 506 result1 := bad_even_rows[row1][row2] 507 result2 := bad_odd_rows[row2][row3] 508 if result1 == 0 && result2 != 0 && triple_is_okay(row1, row2, row3, true) { 509 bad_even_triple[row1+(row2*32)+(row3*1024)] = 0 510 } else { 511 bad_even_triple[row1+(row2*32)+(row3*1024)] = boolInt(result1 != 0 || result2 != 0) 512 } 513 514 result1 = bad_odd_rows[row1][row2] 515 result2 = bad_even_rows[row2][row3] 516 if result1 == 0 && result2 != 0 && triple_is_okay(row1, row2, row3, false) { 517 bad_odd_triple[row1+(row2*32)+(row3*1024)] = 0 518 } else { 519 bad_odd_triple[row1+(row2*32)+(row3*1024)] = boolInt(result1 != 0 || result2 != 0) 520 } 521 } 522 } 523 } 524 } 525 526 /* Calculate islands while solving the board. 527 */ 528 func boardHasIslands(cell int8) int8 { 529 /* Too low on board, don't bother checking */ 530 if cell >= 40 { 531 return 0 532 } 533 current_triple := (board >> uint((cell/5)*5)) & TRIPLE_MASK 534 if (cell/5)%2 != 0 { 535 return bad_odd_triple[current_triple] 536 } 537 return bad_even_triple[current_triple] 538 } 539 540 /* The recursive solve algorithm. Try to place each permutation in the upper- 541 * leftmost empty cell. Mark off available pieces as it goes along. 542 * Because the board is a bit mask, the piece number and bit mask must be saved 543 * at each successful piece placement. This data is used to create a 50 char 544 * array if a solution is found. 545 */ 546 var ( 547 avail uint16 = 0x03FF 548 sol_nums [10]int8 549 sol_masks [10]uint64 550 solutions [2100][50]int8 551 solution_count = 0 552 ) 553 554 func record_solution() { 555 for sol_no := 0; sol_no < 10; sol_no++ { 556 sol_mask := sol_masks[sol_no] 557 for index := 0; index < 50; index++ { 558 if sol_mask&1 == 1 { 559 solutions[solution_count][index] = sol_nums[sol_no] 560 /* Board rotated 180 degrees is a solution too! */ 561 solutions[solution_count+1][49-index] = sol_nums[sol_no] 562 } 563 sol_mask = sol_mask >> 1 564 } 565 } 566 solution_count += 2 567 } 568 569 func solve(depth, cell int8) { 570 if solution_count >= *max_solutions { 571 return 572 } 573 574 for board&(1<<uint(cell)) != 0 { 575 cell++ 576 } 577 578 for piece := int8(0); piece < 10; piece++ { 579 var piece_no_mask uint16 = 1 << uint(piece) 580 if avail&piece_no_mask == 0 { 581 continue 582 } 583 avail ^= piece_no_mask 584 max_rots := piece_counts[piece][cell] 585 piece_mask := pieces[piece][cell] 586 for rotation := 0; rotation < max_rots; rotation++ { 587 if board&piece_mask[rotation] == 0 { 588 sol_nums[depth] = piece 589 sol_masks[depth] = piece_mask[rotation] 590 if depth == 9 { 591 /* Solution found!!!!!11!!ONE! */ 592 record_solution() 593 avail ^= piece_no_mask 594 return 595 } 596 board |= piece_mask[rotation] 597 if boardHasIslands(next_cell[piece][cell][rotation]) == 0 { 598 solve(depth+1, next_cell[piece][cell][rotation]) 599 } 600 board ^= piece_mask[rotation] 601 } 602 } 603 avail ^= piece_no_mask 604 } 605 } 606 607 /* pretty print a board in the specified hexagonal format */ 608 func pretty(b *[50]int8) { 609 for i := 0; i < 50; i += 10 { 610 fmt.Printf("%c %c %c %c %c \n %c %c %c %c %c \n", b[i]+'0', b[i+1]+'0', 611 b[i+2]+'0', b[i+3]+'0', b[i+4]+'0', b[i+5]+'0', b[i+6]+'0', 612 b[i+7]+'0', b[i+8]+'0', b[i+9]+'0') 613 } 614 fmt.Printf("\n") 615 } 616 617 /* Find smallest and largest solutions */ 618 func smallest_largest() (smallest, largest *[50]int8) { 619 smallest = &solutions[0] 620 largest = &solutions[0] 621 for i := 1; i < solution_count; i++ { 622 candidate := &solutions[i] 623 for j, s := range *smallest { 624 c := candidate[j] 625 if c == s { 626 continue 627 } 628 if c < s { 629 smallest = candidate 630 } 631 break 632 } 633 for j, s := range *largest { 634 c := candidate[j] 635 if c == s { 636 continue 637 } 638 if c > s { 639 largest = candidate 640 } 641 break 642 } 643 } 644 return 645 } 646 647 func main() { 648 flag.Parse() 649 calc_pieces() 650 calc_rows() 651 solve(0, 0) 652 fmt.Printf("%d solutions found\n\n", solution_count) 653 smallest, largest := smallest_largest() 654 pretty(smallest) 655 pretty(largest) 656 } 657