source code
/* The Computer Language Benchmarks Game
* http://benchmarksgame.alioth.debian.org/
*
* contributed by The Go Authors.
* based on meteor-contest.c by Christian Vosteen
* flag.Arg hack by Isaac Gouy
*/
package main
import (
"flag"
"fmt"
"strconv"
)
var max_solutions = 0
func boolInt(b bool) int8 {
if b {
return 1
}
return 0
}
/* The board is a 50 cell hexagonal pattern. For . . . . .
* maximum speed the board will be implemented as . . . . .
* 50 bits, which will fit into a 64 bit long long . . . . .
* int. . . . . .
* . . . . .
* I will represent 0's as empty cells and 1's . . . . .
* as full cells. . . . . .
* . . . . .
* . . . . .
* . . . . .
*/
var board uint64 = 0xFFFC000000000000
/* The puzzle pieces must be specified by the path followed
* from one end to the other along 12 hexagonal directions.
*
* Piece 0 Piece 1 Piece 2 Piece 3 Piece 4
*
* O O O O O O O O O O O O O O O
* O O O O O O O
* O O O
*
* Piece 5 Piece 6 Piece 7 Piece 8 Piece 9
*
* O O O O O O O O O O O O O
* O O O O O O O O O
* O O O
*
* I had to make it 12 directions because I wanted all of the
* piece definitions to fit into the same size arrays. It is
* not possible to define piece 4 in terms of the 6 cardinal
* directions in 4 moves.
*/
const (
E = iota
ESE
SE
S
SW
WSW
W
WNW
NW
N
NE
ENE
PIVOT
)
var piece_def = [10][4]int8{
[4]int8{E, E, E, SE},
[4]int8{SE, E, NE, E},
[4]int8{E, E, SE, SW},
[4]int8{E, E, SW, SE},
[4]int8{SE, E, NE, S},
[4]int8{E, E, SW, E},
[4]int8{E, SE, SE, NE},
[4]int8{E, SE, SE, W},
[4]int8{E, SE, E, E},
[4]int8{E, E, E, SW},
}
/* To minimize the amount of work done in the recursive solve function below,
* I'm going to allocate enough space for all legal rotations of each piece
* at each position on the board. That's 10 pieces x 50 board positions x
* 12 rotations. However, not all 12 rotations will fit on every cell, so
* I'll have to keep count of the actual number that do.
* The pieces are going to be unsigned long long ints just like the board so
* they can be bitwise-anded with the board to determine if they fit.
* I'm also going to record the next possible open cell for each piece and
* location to reduce the burden on the solve function.
*/
var (
pieces [10][50][12]uint64
piece_counts [10][50]int
next_cell [10][50][12]int8
)
/* Returns the direction rotated 60 degrees clockwise */
func rotate(dir int8) int8 { return (dir + 2) % PIVOT }
/* Returns the direction flipped on the horizontal axis */
func flip(dir int8) int8 { return (PIVOT - dir) % PIVOT }
/* Returns the new cell index from the specified cell in the
* specified direction. The index is only valid if the
* starting cell and direction have been checked by the
* out_of_bounds function first.
*/
func shift(cell, dir int8) int8 {
switch dir {
case E:
return cell + 1
case ESE:
if ((cell / 5) % 2) != 0 {
return cell + 7
} else {
return cell + 6
}
case SE:
if ((cell / 5) % 2) != 0 {
return cell + 6
} else {
return cell + 5
}
case S:
return cell + 10
case SW:
if ((cell / 5) % 2) != 0 {
return cell + 5
} else {
return cell + 4
}
case WSW:
if ((cell / 5) % 2) != 0 {
return cell + 4
} else {
return cell + 3
}
case W:
return cell - 1
case WNW:
if ((cell / 5) % 2) != 0 {
return cell - 6
} else {
return cell - 7
}
case NW:
if ((cell / 5) % 2) != 0 {
return cell - 5
} else {
return cell - 6
}
case N:
return cell - 10
case NE:
if ((cell / 5) % 2) != 0 {
return cell - 4
} else {
return cell - 5
}
case ENE:
if ((cell / 5) % 2) != 0 {
return cell - 3
} else {
return cell - 4
}
}
return cell
}
/* Returns wether the specified cell and direction will land outside
* of the board. Used to determine if a piece is at a legal board
* location or not.
*/
func out_of_bounds(cell, dir int8) bool {
switch dir {
case E:
return cell%5 == 4
case ESE:
i := cell % 10
return i == 4 || i == 8 || i == 9 || cell >= 45
case SE:
return cell%10 == 9 || cell >= 45
case S:
return cell >= 40
case SW:
return cell%10 == 0 || cell >= 45
case WSW:
i := cell % 10
return i == 0 || i == 1 || i == 5 || cell >= 45
case W:
return cell%5 == 0
case WNW:
i := cell % 10
return i == 0 || i == 1 || i == 5 || cell < 5
case NW:
return cell%10 == 0 || cell < 5
case N:
return cell < 10
case NE:
return cell%10 == 9 || cell < 5
case ENE:
i := cell % 10
return i == 4 || i == 8 || i == 9 || cell < 5
}
return false
}
/* Rotate a piece 60 degrees clockwise */
func rotate_piece(piece int) {
for i := 0; i < 4; i++ {
piece_def[piece][i] = rotate(piece_def[piece][i])
}
}
/* Flip a piece along the horizontal axis */
func flip_piece(piece int) {
for i := 0; i < 4; i++ {
piece_def[piece][i] = flip(piece_def[piece][i])
}
}
/* Convenience function to quickly calculate all of the indices for a piece */
func calc_cell_indices(cell []int8, piece int, index int8) {
cell[0] = index
for i := 1; i < 5; i++ {
cell[i] = shift(cell[i-1], piece_def[piece][i-1])
}
}
/* Convenience function to quickly calculate if a piece fits on the board */
func cells_fit_on_board(cell []int8, piece int) bool {
return !out_of_bounds(cell[0], piece_def[piece][0]) &&
!out_of_bounds(cell[1], piece_def[piece][1]) &&
!out_of_bounds(cell[2], piece_def[piece][2]) &&
!out_of_bounds(cell[3], piece_def[piece][3])
}
/* Returns the lowest index of the cells of a piece.
* I use the lowest index that a piece occupies as the index for looking up
* the piece in the solve function.
*/
func minimum_of_cells(cell []int8) int8 {
minimum := cell[0]
for i := 1; i < 5; i++ {
if cell[i] < minimum {
minimum = cell[i]
}
}
return minimum
}
/* Calculate the lowest possible open cell if the piece is placed on the board.
* Used to later reduce the amount of time searching for open cells in the
* solve function.
*/
func first_empty_cell(cell []int8, minimum int8) int8 {
first_empty := minimum
for first_empty == cell[0] || first_empty == cell[1] ||
first_empty == cell[2] || first_empty == cell[3] ||
first_empty == cell[4] {
first_empty++
}
return first_empty
}
/* Generate the unsigned long long int that will later be anded with the
* board to determine if it fits.
*/
func bitmask_from_cells(cell []int8) uint64 {
var piece_mask uint64
for i := 0; i < 5; i++ {
piece_mask |= 1 << uint(cell[i])
}
return piece_mask
}
/* Record the piece and other important information in arrays that will
* later be used by the solve function.
*/
func record_piece(piece int, minimum int8, first_empty int8, piece_mask uint64) {
pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask
next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty
piece_counts[piece][minimum]++
}
/* Fill the entire board going cell by cell. If any cells are "trapped"
* they will be left alone.
*/
func fill_contiguous_space(board []int8, index int8) {
if board[index] == 1 {
return
}
board[index] = 1
if !out_of_bounds(index, E) {
fill_contiguous_space(board, shift(index, E))
}
if !out_of_bounds(index, SE) {
fill_contiguous_space(board, shift(index, SE))
}
if !out_of_bounds(index, SW) {
fill_contiguous_space(board, shift(index, SW))
}
if !out_of_bounds(index, W) {
fill_contiguous_space(board, shift(index, W))
}
if !out_of_bounds(index, NW) {
fill_contiguous_space(board, shift(index, NW))
}
if !out_of_bounds(index, NE) {
fill_contiguous_space(board, shift(index, NE))
}
}
/* To thin the number of pieces, I calculate if any of them trap any empty
* cells at the edges. There are only a handful of exceptions where the
* the board can be solved with the trapped cells. For example: piece 8 can
* trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0
* can split the board in half where both halves are viable.
*/
func has_island(cell []int8, piece int) bool {
temp_board := make([]int8, 50)
var i int
for i = 0; i < 5; i++ {
temp_board[cell[i]] = 1
}
i = 49
for temp_board[i] == 1 {
i--
}
fill_contiguous_space(temp_board, int8(i))
c := 0
for i = 0; i < 50; i++ {
if temp_board[i] == 0 {
c++
}
}
if c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) ||
(c%5 == 0 && piece == 0) {
return false
}
return true
}
/* Calculate all six rotations of the specified piece at the specified index.
* We calculate only half of piece 3's rotations. This is because any solution
* found has an identical solution rotated 180 degrees. Thus we can reduce the
* number of attempted pieces in the solve algorithm by not including the 180-
* degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave
* me the best time ;)
*/
func calc_six_rotations(piece, index int) {
cell := make([]int8, 5)
for rotation := 0; rotation < 6; rotation++ {
if piece != 3 || rotation < 3 {
calc_cell_indices(cell, piece, int8(index))
if cells_fit_on_board(cell, piece) && !has_island(cell, piece) {
minimum := minimum_of_cells(cell)
first_empty := first_empty_cell(cell, minimum)
piece_mask := bitmask_from_cells(cell)
record_piece(piece, minimum, first_empty, piece_mask)
}
}
rotate_piece(piece)
}
}
/* Calculate every legal rotation for each piece at each board location. */
func calc_pieces() {
for piece := 0; piece < 10; piece++ {
for index := 0; index < 50; index++ {
calc_six_rotations(piece, index)
flip_piece(piece)
calc_six_rotations(piece, index)
}
}
}
/* Calculate all 32 possible states for a 5-bit row and all rows that will
* create islands that follow any of the 32 possible rows. These pre-
* calculated 5-bit rows will be used to find islands in a partially solved
* board in the solve function.
*/
const (
ROW_MASK = 0x1F
TRIPLE_MASK = 0x7FFF
)
var (
all_rows = [32]int8{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
}
bad_even_rows [32][32]int8
bad_odd_rows [32][32]int8
bad_even_triple [32768]int8
bad_odd_triple [32768]int8
)
func rows_bad(row1, row2 int8, even bool) int8 {
/* even is referring to row1 */
var row2_shift int8
/* Test for blockages at same index and shifted index */
if even {
row2_shift = ((row2 << 1) & ROW_MASK) | 0x01
} else {
row2_shift = (row2 >> 1) | 0x10
}
block := ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift)
/* Test for groups of 0's */
in_zeroes := false
group_okay := false
for i := uint8(0); i < 5; i++ {
if row1&(1<<i) != 0 {
if in_zeroes {
if !group_okay {
return 1
}
in_zeroes = false
group_okay = false
}
} else {
if !in_zeroes {
in_zeroes = true
}
if (block & (1 << i)) == 0 {
group_okay = true
}
}
}
if in_zeroes {
return boolInt(!group_okay)
}
return 0
}
/* Check for cases where three rows checked sequentially cause a false
* positive. One scenario is when 5 cells may be surrounded where piece 5
* or 7 can fit. The other scenario is when piece 2 creates a hook shape.
*/
func triple_is_okay(row1, row2, row3 int, even bool) bool {
if even {
/* There are four cases:
* row1: 00011 00001 11001 10101
* row2: 01011 00101 10001 10001
* row3: 011?? 00110 ????? ?????
*/
return ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) ||
((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) ||
((row1 == 0x19) && (row2 == 0x11)) ||
((row1 == 0x15) && (row2 == 0x11))
}
/* There are two cases:
* row1: 10011 10101
* row2: 10001 10001
* row3: ????? ?????
*/
return ((row1 == 0x13) && (row2 == 0x11)) ||
((row1 == 0x15) && (row2 == 0x11))
}
func calc_rows() {
for row1 := int8(0); row1 < 32; row1++ {
for row2 := int8(0); row2 < 32; row2++ {
bad_even_rows[row1][row2] = rows_bad(row1, row2, true)
bad_odd_rows[row1][row2] = rows_bad(row1, row2, false)
}
}
for row1 := 0; row1 < 32; row1++ {
for row2 := 0; row2 < 32; row2++ {
for row3 := 0; row3 < 32; row3++ {
result1 := bad_even_rows[row1][row2]
result2 := bad_odd_rows[row2][row3]
if result1 == 0 && result2 != 0 && triple_is_okay(row1, row2, row3, true) {
bad_even_triple[row1+(row2*32)+(row3*1024)] = 0
} else {
bad_even_triple[row1+(row2*32)+(row3*1024)] = boolInt(result1 != 0 || result2 != 0)
}
result1 = bad_odd_rows[row1][row2]
result2 = bad_even_rows[row2][row3]
if result1 == 0 && result2 != 0 && triple_is_okay(row1, row2, row3, false) {
bad_odd_triple[row1+(row2*32)+(row3*1024)] = 0
} else {
bad_odd_triple[row1+(row2*32)+(row3*1024)] = boolInt(result1 != 0 || result2 != 0)
}
}
}
}
}
/* Calculate islands while solving the board.
*/
func boardHasIslands(cell int8) int8 {
/* Too low on board, don't bother checking */
if cell >= 40 {
return 0
}
current_triple := (board >> uint((cell/5)*5)) & TRIPLE_MASK
if (cell/5)%2 != 0 {
return bad_odd_triple[current_triple]
}
return bad_even_triple[current_triple]
}
/* The recursive solve algorithm. Try to place each permutation in the upper-
* leftmost empty cell. Mark off available pieces as it goes along.
* Because the board is a bit mask, the piece number and bit mask must be saved
* at each successful piece placement. This data is used to create a 50 char
* array if a solution is found.
*/
var (
avail uint16 = 0x03FF
sol_nums [10]int8
sol_masks [10]uint64
solutions [2100][50]int8
solution_count = 0
)
func record_solution() {
for sol_no := 0; sol_no < 10; sol_no++ {
sol_mask := sol_masks[sol_no]
for index := 0; index < 50; index++ {
if sol_mask&1 == 1 {
solutions[solution_count][index] = sol_nums[sol_no]
/* Board rotated 180 degrees is a solution too! */
solutions[solution_count+1][49-index] = sol_nums[sol_no]
}
sol_mask = sol_mask >> 1
}
}
solution_count += 2
}
func solve(depth, cell int8) {
if solution_count >= max_solutions {
return
}
for board&(1<<uint(cell)) != 0 {
cell++
}
for piece := int8(0); piece < 10; piece++ {
var piece_no_mask uint16 = 1 << uint(piece)
if avail&piece_no_mask == 0 {
continue
}
avail ^= piece_no_mask
max_rots := piece_counts[piece][cell]
piece_mask := pieces[piece][cell]
for rotation := 0; rotation < max_rots; rotation++ {
if board&piece_mask[rotation] == 0 {
sol_nums[depth] = piece
sol_masks[depth] = piece_mask[rotation]
if depth == 9 {
/* Solution found!!!!!11!!ONE! */
record_solution()
avail ^= piece_no_mask
return
}
board |= piece_mask[rotation]
if boardHasIslands(next_cell[piece][cell][rotation]) == 0 {
solve(depth+1, next_cell[piece][cell][rotation])
}
board ^= piece_mask[rotation]
}
}
avail ^= piece_no_mask
}
}
/* pretty print a board in the specified hexagonal format */
func pretty(b *[50]int8) {
for i := 0; i < 50; i += 10 {
fmt.Printf("%c %c %c %c %c \n %c %c %c %c %c \n", b[i]+'0', b[i+1]+'0',
b[i+2]+'0', b[i+3]+'0', b[i+4]+'0', b[i+5]+'0', b[i+6]+'0',
b[i+7]+'0', b[i+8]+'0', b[i+9]+'0')
}
fmt.Printf("\n")
}
/* Find smallest and largest solutions */
func smallest_largest() (smallest, largest *[50]int8) {
smallest = &solutions[0]
largest = &solutions[0]
for i := 1; i < solution_count; i++ {
candidate := &solutions[i]
for j, s := range *smallest {
c := candidate[j]
if c == s {
continue
}
if c < s {
smallest = candidate
}
break
}
for j, s := range *largest {
c := candidate[j]
if c == s {
continue
}
if c > s {
largest = candidate
}
break
}
}
return
}
func main() {
flag.Parse()
if flag.NArg() > 0 { max_solutions,_ = strconv.Atoi( flag.Arg(0) ) }
calc_pieces()
calc_rows()
solve(0, 0)
fmt.Printf("%d solutions found\n\n", solution_count)
smallest, largest := smallest_largest()
pretty(smallest)
pretty(largest)
}