summaryrefslogtreecommitdiff
path: root/gcc/testsuite/go.test/test/bench/meteor-contest.go
diff options
context:
space:
mode:
Diffstat (limited to 'gcc/testsuite/go.test/test/bench/meteor-contest.go')
-rw-r--r--gcc/testsuite/go.test/test/bench/meteor-contest.go665
1 files changed, 665 insertions, 0 deletions
diff --git a/gcc/testsuite/go.test/test/bench/meteor-contest.go b/gcc/testsuite/go.test/test/bench/meteor-contest.go
new file mode 100644
index 000000000..6660810eb
--- /dev/null
+++ b/gcc/testsuite/go.test/test/bench/meteor-contest.go
@@ -0,0 +1,665 @@
+/*
+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)
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-04-22 21:13:13 +0000