gcc/testsuite/g++.dg/pph/c1meteor-contest.h

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