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