meteor-contest

R=rsc
DELTA=1276  (1275 added, 0 deleted, 1 changed)
OCL=32851
CL=32854

5 files changed, 1334 insertions, 1 deletions

diff --git a/test/bench/meteor-contest.c b/test/bench/meteor-contest.c
new file mode 100644
index 000000000..19c43402c
--- /dev/null
+++ b/test/bench/meteor-contest.c
@@ -0,0 +1,626 @@
+/*
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+
+    * Neither the name of "The Computer Language Benchmarks Game" nor the
+    name of "The Computer Language Shootout Benchmarks" nor the names of
+    its contributors may be used to endorse or promote products derived
+    from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * contributed by Christian Vosteen
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#define TRUE 1
+#define FALSE 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.                                    . . . . .
+ *                                                    . . . . .
+ *                                                   . . . . .
+ *                                                    . . . . .
+ */
+
+unsigned long long board = 0xFFFC000000000000ULL;
+
+/* 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.
+ */
+
+#define E     0
+#define ESE   1
+#define SE    2
+#define S     3
+#define SW    4
+#define WSW   5
+#define W     6
+#define WNW   7
+#define NW    8
+#define N     9
+#define NE    10
+#define ENE   11
+#define PIVOT 12
+
+char piece_def[10][4] = {
+   {  E,  E,  E, SE},
+   { SE,  E, NE,  E},
+   {  E,  E, SE, SW},
+   {  E,  E, SW, SE},
+   { SE,  E, NE,  S},
+   {  E,  E, SW,  E},
+   {  E, SE, SE, NE},
+   {  E, SE, SE,  W},
+   {  E, SE,  E,  E},
+   {  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.
+ */
+unsigned long long pieces[10][50][12];
+int piece_counts[10][50];
+char next_cell[10][50][12];
+
+/* Returns the direction rotated 60 degrees clockwise */
+char rotate(char dir) {
+   return (dir + 2) % PIVOT;
+}
+
+/* Returns the direction flipped on the horizontal axis */
+char flip(char dir) {
+   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.
+ */
+char shift(char cell, char dir) {
+   switch(dir) {
+      case E:
+         return cell + 1;
+      case ESE:
+         if((cell / 5) % 2)
+            return cell + 7;
+         else
+            return cell + 6;
+      case SE:
+         if((cell / 5) % 2)
+            return cell + 6;
+         else
+            return cell + 5;
+      case S:
+         return cell + 10;
+      case SW:
+         if((cell / 5) % 2)
+            return cell + 5;
+         else
+            return cell + 4;
+      case WSW:
+         if((cell / 5) % 2)
+            return cell + 4;
+         else
+            return cell + 3;
+      case W:
+         return cell - 1;
+      case WNW:
+         if((cell / 5) % 2)
+            return cell - 6;
+         else
+            return cell - 7;
+      case NW:
+         if((cell / 5) % 2)
+            return cell - 5;
+         else
+            return cell - 6;
+      case N:
+         return cell - 10;
+      case NE:
+         if((cell / 5) % 2)
+            return cell - 4;
+         else
+            return cell - 5;
+      case ENE:
+         if((cell / 5) % 2)
+            return cell - 3;
+         else
+            return cell - 4;
+      default:
+         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.
+ */
+char out_of_bounds(char cell, char dir) {
+   char i;
+   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;
+      default:
+         return FALSE;
+   }
+}
+
+/* Rotate a piece 60 degrees clockwise */
+void rotate_piece(int piece) {
+   int i;
+   for(i = 0; i < 4; i++)
+      piece_def[piece][i] = rotate(piece_def[piece][i]);
+}
+
+/* Flip a piece along the horizontal axis */
+void flip_piece(int piece) {
+   int i;
+   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 */
+void calc_cell_indices(char *cell, int piece, char index) {
+   cell[0] = index;
+   cell[1] = shift(cell[0], piece_def[piece][0]);
+   cell[2] = shift(cell[1], piece_def[piece][1]);
+   cell[3] = shift(cell[2], piece_def[piece][2]);
+   cell[4] = shift(cell[3], piece_def[piece][3]);
+}
+
+/* Convenience function to quickly calculate if a piece fits on the board */
+int cells_fit_on_board(char *cell, int piece) {
+   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.
+ */
+char minimum_of_cells(char *cell) {
+   char minimum = cell[0];
+   minimum = cell[1] < minimum ? cell[1] : minimum;
+   minimum = cell[2] < minimum ? cell[2] : minimum;
+   minimum = cell[3] < minimum ? cell[3] : minimum;
+   minimum = cell[4] < minimum ? cell[4] : minimum;
+   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.
+ */
+char first_empty_cell(char *cell, char minimum) {
+   char first_empty = minimum;
+   while(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.
+ */
+unsigned long long bitmask_from_cells(char *cell) {
+   unsigned long long piece_mask = 0ULL;
+   int i;
+   for(i = 0; i < 5; i++)
+      piece_mask |= 1ULL << cell[i];
+   return piece_mask;
+}
+
+/* Record the piece and other important information in arrays that will
+ * later be used by the solve function.
+ */
+void record_piece(int piece, int minimum, char first_empty,
+      unsigned long long piece_mask) {
+   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.
+ */
+void fill_contiguous_space(char *board, int index) {
+   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.
+ */
+int has_island(char *cell, int piece) {
+   char temp_board[50];
+   char c;
+   int i;
+   for(i = 0; i < 50; i++)
+      temp_board[i] = 0;
+   for(i = 0; i < 5; i++)
+      temp_board[((int)cell[i])] = 1;
+   i = 49;
+   while(temp_board[i] == 1)
+      i--;
+   fill_contiguous_space(temp_board, 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;
+   else
+      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 ;)
+ */
+ void calc_six_rotations(char piece, char index) {
+   char rotation, cell[5];
+   char minimum, first_empty;
+   unsigned long long piece_mask;
+
+   for(rotation = 0; rotation < 6; rotation++) {
+      if(piece != 3 || rotation < 3) {
+         calc_cell_indices(cell, piece, 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. */
+void calc_pieces(void) {
+   char piece, index;
+
+   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.
+ */
+#define ROW_MASK 0x1F
+#define TRIPLE_MASK 0x7FFF
+char all_rows[32] = {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};
+int bad_even_rows[32][32];
+int bad_odd_rows[32][32];
+int bad_even_triple[32768];
+int bad_odd_triple[32768];
+
+int rows_bad(char row1, char row2, int even) {
+   /* even is referring to row1 */
+   int i, in_zeroes, group_okay;
+   char block, row2_shift;
+   /* 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 = 0; i < 5; i++) {
+      if(row1 & (1 << i)) {
+         if(in_zeroes) {
+            if(!group_okay)
+               return TRUE;
+            in_zeroes = FALSE;
+            group_okay = FALSE;
+         }
+      } else {
+         if(!in_zeroes)
+            in_zeroes = TRUE;
+         if(!(block & (1 << i)))
+            group_okay = TRUE;
+      }
+   }
+   if(in_zeroes)
+      return !group_okay;
+   else
+      return FALSE;
+}
+
+/* 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.
+ */
+int triple_is_okay(char row1, char row2, char row3, int even) {
+   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));
+   } else {
+      /* There are two cases:
+       * row1: 10011  10101
+       * row2: 10001  10001
+       * row3: ?????  ?????
+       */
+      return ((row1 == 0x13) && (row2 == 0x11)) ||
+            ((row1 == 0x15) && (row2 == 0x11));
+   }
+}
+
+
+void calc_rows(void) {
+   int row1, row2, row3;
+   int result1, result2;
+   for(row1 = 0; row1 < 32; row1++) {
+      for(row2 = 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 == FALSE && result2 == TRUE
+                  && triple_is_okay(row1, row2, row3, TRUE))
+               bad_even_triple[row1+(row2*32)+(row3*1024)] = FALSE;
+            else
+               bad_even_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
+
+            result1 = bad_odd_rows[row1][row2];
+            result2 = bad_even_rows[row2][row3];
+            if(result1 == FALSE && result2 == TRUE
+                  && triple_is_okay(row1, row2, row3, FALSE))
+               bad_odd_triple[row1+(row2*32)+(row3*1024)] = FALSE;
+            else
+               bad_odd_triple[row1+(row2*32)+(row3*1024)] = result1 || result2;
+         }
+      }
+   }
+}
+
+
+
+/* Calculate islands while solving the board.
+ */
+int boardHasIslands(char cell) {
+   /* Too low on board, don't bother checking */
+   if(cell >= 40)
+      return FALSE;
+   int current_triple = (board >> ((cell / 5) * 5)) & TRIPLE_MASK;
+   if((cell / 5) % 2)
+      return bad_odd_triple[current_triple];
+   else
+      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.
+ */
+short avail = 0x03FF;
+char sol_nums[10];
+unsigned long long sol_masks[10];
+signed char solutions[2100][50];
+int solution_count = 0;
+int max_solutions = 2100;
+
+void record_solution(void) {
+   int sol_no, index;
+   unsigned long long sol_mask;
+   for(sol_no = 0; sol_no < 10; sol_no++) {
+      sol_mask = sol_masks[sol_no];
+      for(index = 0; index < 50; index++) {
+         if(sol_mask & 1ULL) {
+            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;
+}
+
+void solve(int depth, int cell) {
+   int piece, rotation, max_rots;
+   unsigned long long *piece_mask;
+   short piece_no_mask;
+
+   if(solution_count >= max_solutions)
+      return;
+
+   while(board & (1ULL << cell))
+      cell++;
+
+   for(piece = 0; piece < 10; piece++) {
+      piece_no_mask = 1 << piece;
+      if(!(avail & piece_no_mask))
+         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))) {
+            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]))
+               solve(depth + 1, next_cell[piece][cell][rotation]);
+            board ^= *(piece_mask + rotation);
+         }
+      }
+      avail ^= piece_no_mask;
+   }
+}
+
+
+/* qsort comparator - used to find first and last solutions */
+int solution_sort(const void *elem1, const void *elem2) {
+   signed char *char1 = (signed char *) elem1;
+   signed char *char2 = (signed char *) elem2;
+   int i = 0;
+   while(i < 50 && char1[i] == char2[i])
+      i++;
+   return char1[i] - char2[i];
+}
+
+
+/* pretty print a board in the specified hexagonal format */
+void pretty(signed char *b) {
+   int i;
+   for(i = 0; i < 50; i += 10) {
+      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');
+   }
+   printf("\n");
+}
+
+int main(int argc, char **argv) {
+   if(argc > 1)
+      max_solutions = atoi(argv[1]);
+   calc_pieces();
+   calc_rows();
+   solve(0, 0);
+   printf("%d solutions found\n\n", solution_count);
+   qsort(solutions, solution_count, 50 * sizeof(signed char), solution_sort);
+   pretty(solutions[0]);
+   pretty(solutions[solution_count-1]);
+   return 0;
+}
diff --git a/test/bench/meteor-contest.go b/test/bench/meteor-contest.go
new file mode 100644
index 000000000..d1b1a62cf
--- /dev/null
+++ b/test/bench/meteor-contest.go
@@ -0,0 +1,669 @@
+/*
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+
+    * Neither the name of "The Computer Language Benchmarks Game" nor the
+    name of "The Computer Language Shootout Benchmarks" nor the names of
+    its contributors may be used to endorse or promote products derived
+    from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* The Computer Language Benchmarks Game
+ * http://shootout.alioth.debian.org/
+ *
+ * contributed by The Go Authors.
+ * based on meteor-contest.c by Christian Vosteen
+ */
+
+package main
+
+import (
+	"flag";
+	"fmt";
+)
+
+var max_solutions = flag.Int("n", 2100, "maximum number of solutions")
+
+
+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();
+	calc_pieces();
+	calc_rows();
+	solve(0, 0);
+	fmt.Printf("%d solutions found\n\n", solution_count);
+	smallest, largest := smallest_largest();
+	pretty(smallest);
+	pretty(largest);
+}
diff --git a/test/bench/meteor-contest.txt b/test/bench/meteor-contest.txt
new file mode 100644
index 000000000..38d9783d6
--- /dev/null
+++ b/test/bench/meteor-contest.txt
@@ -0,0 +1,24 @@
+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 
+
diff --git a/test/bench/timing.log b/test/bench/timing.log
index 520b18dd0..1d7bdd6a3 100644
--- a/test/bench/timing.log
+++ b/test/bench/timing.log
@@ -80,3 +80,9 @@ mandelbrot 5500
 	gccgo -O2 mandelbrot.go	57.49u 0.01s 57.51r
 	gc mandelbrot	74.32u 0.00s 74.35r
 	gc_B mandelbrot	74.28u 0.01s 74.31r
+
+meteor 16000
+	gcc -O2 meteor-contest.c	0.10u 0.00s 0.10r
+	gccgo -O2 meteor-contest.go	0.12u 0.00s 0.14r
+	gc meteor-contest	0.24u 0.00s 0.26r
+	gc_B meteor-contest	0.23u 0.00s 0.24r
diff --git a/test/bench/timing.sh b/test/bench/timing.sh
index 600cacb91..9d95a06f8 100755
--- a/test/bench/timing.sh
+++ b/test/bench/timing.sh
@@ -103,9 +103,17 @@ mandelbrot() {
 	run 'gc_B mandelbrot' $O.out -n 16000
 }
 
+meteor() {
+	echo 'meteor 16000'
+	run 'gcc -O2 meteor-contest.c' a.out
+	run 'gccgo -O2 meteor-contest.go' a.out
+	run 'gc meteor-contest' $O.out
+	run 'gc_B  meteor-contest' $O.out
+}
+
 case $# in
 0)
-	run="fasta revcom nbody binarytree fannkuch regexdna spectralnorm knucleotide mandelbrot"
+	run="fasta revcom nbody binarytree fannkuch regexdna spectralnorm knucleotide mandelbrot meteor"
 	;;
 *)
 	run=$*