/mobile Handheld Friendly website

 performance measurements

Each table row shows performance measurements for this Go program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,0980.140.14?2986  0% 100% 0% 0%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read meteor-contest benchmark to see what this program should do.

 notes

go version go1.1.1 linux/amd64

 meteor-contest Go program 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)
}

 make, command-line, and program output logs

Thu, 13 Jun 2013 18:13:58 GMT

MAKE:
/usr/local/src/go/bin/go build -o meteor.go_run
0.31s to complete and log all make actions

COMMAND LINE:
./meteor.go_run 2098

PROGRAM OUTPUT:
2098 solutions found

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

9 9 9 9 8 
 9 6 6 8 5 
6 6 8 8 5 
 6 8 2 5 5 
7 7 7 2 5 
 7 4 7 2 0 
1 4 2 2 0 
 1 4 4 0 3 
1 4 0 0 3 
 1 1 3 3 3

Revised BSD license

  Home   Conclusions   License   Play