Patchwork [pph] Split c1meteor-contest.cc (issue4654087)

login
register
mail settings
Submitter Diego Novillo
Date July 4, 2011, 8:52 p.m.
Message ID <20110704205254.7B2B11DA1D1@topo.tor.corp.google.com>
Download mbox | patch
Permalink /patch/103167/
State New
Headers show

Comments

Diego Novillo - July 4, 2011, 8:52 p.m.
The test c1meteor-contest.cc had similar issues as c1eabi1.cc.  The
inclusion of system headers that have been PPH'd confuse the compiler.
I split the test so we have one version without additional includes
and another with the standard includes.

The version without additional includes works fine.

Tested on x86_64.  Committed.


Diego.

	* g++.dg/pph/c1meteor-contest.cc: Make executable.
	Move function main() from c1meteor-contest.h.
	* g++.dg/pph/c1meteor-contest.h: Do not include stdlib.h nor
	stdio.h.
	Add prototype for system functions qsort, printf and atoi.
	* g++.dg/pph/c2meteor-contest.cc: New.
	* g++.dg/pph/c2meteor-contest.h: New.
	* g++.dg/pph/pph.map: Add c2meteor-contest.h


--
This patch is available for review at http://codereview.appspot.com/4654087

Patch

diff --git a/gcc/testsuite/g++.dg/pph/c1meteor-contest.cc b/gcc/testsuite/g++.dg/pph/c1meteor-contest.cc
index e745afe..ff1765c 100644
--- a/gcc/testsuite/g++.dg/pph/c1meteor-contest.cc
+++ b/gcc/testsuite/g++.dg/pph/c1meteor-contest.cc
@@ -1,4 +1,17 @@ 
-/* { dg-timeout 2 { target *-*-* } }  */
-// { dg-xfail-if "INFINITE" { "*-*-*" } { "-fpph-map=pph.map" } }
 /* { dg-options "-w" }  */
+/* { dg-do run } */
+
 #include "c1meteor-contest.h"
+
+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/gcc/testsuite/g++.dg/pph/c1meteor-contest.h b/gcc/testsuite/g++.dg/pph/c1meteor-contest.h
index 3c465ab..698ccf5 100644
--- a/gcc/testsuite/g++.dg/pph/c1meteor-contest.h
+++ b/gcc/testsuite/g++.dg/pph/c1meteor-contest.h
@@ -36,8 +36,16 @@  POSSIBILITY OF SUCH DAMAGE.
  * contributed by Christian Vosteen
  */
 
-#include <stdlib.h>
-#include <stdio.h>
+/* Simplified version of c2meteor-contest.h - Do not include other system
+   headers here.  Simply forward declare the library functions used
+   by this header.  */
+extern  "C" {
+  typedef __SIZE_TYPE__ size_t;
+  void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
+  int printf(const char *, ...);
+  int atoi(const char *);
+}
+
 #define TRUE 1
 #define FALSE 0
 
@@ -614,17 +622,4 @@  void pretty(signed char *b) {
    }
    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;
-}
 #endif
diff --git a/gcc/testsuite/g++.dg/pph/c2meteor-contest.cc b/gcc/testsuite/g++.dg/pph/c2meteor-contest.cc
new file mode 100644
index 0000000..e35cca4
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pph/c2meteor-contest.cc
@@ -0,0 +1,17 @@ 
+/* { dg-timeout 2 { target *-*-* } }  */
+// { dg-xfail-if "INFINITE" { "*-*-*" } { "-fpph-map=pph.map" } }
+/* { dg-options "-w" }  */
+#include "c2meteor-contest.h"
+
+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/gcc/testsuite/g++.dg/pph/c2meteor-contest.h b/gcc/testsuite/g++.dg/pph/c2meteor-contest.h
new file mode 100644
index 0000000..33a9907
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pph/c2meteor-contest.h
@@ -0,0 +1,617 @@ 
+/* { dg-options "-w" }  */
+#ifndef __PPH_GUARD_H
+#define __PPH_GUARD_H
+/*
+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");
+}
+#endif
diff --git a/gcc/testsuite/g++.dg/pph/pph.map b/gcc/testsuite/g++.dg/pph/pph.map
index f456005..48c2452 100644
--- a/gcc/testsuite/g++.dg/pph/pph.map
+++ b/gcc/testsuite/g++.dg/pph/pph.map
@@ -18,6 +18,7 @@  c1guarded2.h	c1guarded2.pph
 c1guarded3.h	c1guarded3.pph
 c1limits-externalid.h	c1limits-externalid.pph
 c1meteor-contest.h	c1meteor-contest.pph
+c2meteor-contest.h	c2meteor-contest.pph
 c1multinc1.h	c1multinc1.pph
 c1multinc2.h	c1multinc2.pph
 c1pr36533.h	c1pr36533.pph