Source file src/golang.org/x/exp/shootout/meteor-contest.go

Documentation: golang.org/x/exp/shootout

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

View as plain text