编程竞赛问题：计数多项式

请看我自己的答案，我想我做到了！

---

嗨，

编程竞赛的一个示例问题是编写一个程序，找出给定数量的gem可能有多少多边形。

所以对于两块石头（ n = 2 ），只有一块多边形：

 XX 

您可能认为这是第二种解决方案：

 X X 

但事实并非如此。 如果您可以旋转多边形，则它们不是唯一的。

因此，对于4颗gem（ n = 4 ），有7种解决方案：

 X X XX XXXX XX XX X XX XX XX XXX XX XX XX 

应用程序必须能够找到1 <= n <=10的解决方案

PS：不允许在维基百科上使用polyominos列表 ;）

编辑：当然问题是：如何在Java，C / C ++，C＃中做到这一点

---

我用Java开始这个项目。 但后来我不得不承认我不知道如何使用有效的算法构建多边形。

这是我到目前为止所做的：

 import java.util.ArrayList; import java.util.List; public class Main { private int countPolyminos(int n) { hashes.clear(); count = 0; boolean[][] matrix = new boolean[n][n]; createPolyominos(matrix, n); return count; } private List hashes = new ArrayList(); private int count; private void createPolyominos(boolean[][] matrix, int n) { if (n == 0) { boolean[][] cropped = cropMatrix(matrix); int hash = hashMatrixOrientationIndependent(matrix); if (!hashes.contains(hash)) { count++; hashes.add(hash); } return; } // Here is the real trouble!! // Then here something like; createPolyominos(matrix, n-1); // But, we need to keep in mind that the polyominos can have ramifications } public boolean[][] copy(boolean[][] matrix) { boolean[][] b = new boolean[matrix.length][matrix[0].length]; for (int i = 0; i < matrix.length; ++i) { System.arraycopy(matrix[i], 0, b, 0, matrix[i].length); } return b; } public boolean[][] cropMatrix(boolean[][] matrix) { int l = 0, t = 0, r = 0, b = 0; // Left left: for (int x = 0; x < matrix.length; ++x) { for (int y = 0; y = 0; --x) { for (int y = 0; y < matrix[x].length; ++y) { if (matrix[x][y]) { break right; } } r++; } // Top top: for (int y = 0; y < matrix[0].length; ++y) { for (int x = 0; x = 0; --y) { for (int x = 0; x < matrix.length; ++x) { if (matrix[x][y]) { break bottom; } } b++; } // Perform the real crop boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b]; for (int x = l; x < matrix.length - r; ++x) { System.arraycopy(matrix[x - l], t, cropped, 0, matrix[x].length - t - b); } return cropped; } public int hashMatrix(boolean[][] matrix) { int hash = 0; for (int x = 0; x < matrix.length; ++x) { for (int y = 0; y < matrix[x].length; ++y) { hash += matrix[x][y] ? (((x + 7) << 4) * ((y + 3) << 6) * 31) : ((((x+5) << 9) * (((y + x) + 18) << 7) * 53)); } } return hash; } public int hashMatrixOrientationIndependent(boolean[][] matrix) { int hash = 0; hash += hashMatrix(matrix); for (int i = 0; i < 3; ++i) { matrix = rotateMatrixLeft(matrix); hash += hashMatrix(matrix); } return hash; } public boolean[][] rotateMatrixRight(boolean[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; boolean[][] ret = new boolean[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[w - j - 1][i]; } } return ret; } public boolean[][] rotateMatrixLeft(boolean[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; boolean[][] ret = new boolean[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[j][h - i - 1]; } } return ret; } } 

Answer 1

刚刚在java中解决了这个问题。 因为这里似乎都有性能问题。 我也给你了。

董事会代表：

2个整数数组。 1表示行，1表示列。

• 旋转： column[i]=row[size-(i+1)] ， row[i] = reverse(column[i])其中反向是根据大小反转的位（对于大小= 4和前2位是采取： rev(1100) = 0011 ）
• 移位块： row[i-1] = row[i] ， col[i]<<=1
• 检查位是否设置： (row[r] & (1< 0
• 电路板唯一性：当arrays行是唯一的时，电路板是唯一的。
• Board hash：数组行的Hashcode
• ..

所以这使得所有操作都很快。 它们中的许多在2Darrays表示中将是O(size²)而不是现在的O(size) 。

算法：

• 从大小为1的块开始
• 对于每个尺寸从块少开始1块石头。
• 如果可以添加石头。 检查它是否已添加到集合中。
• 如果它还没有添加。 将其添加到此大小的解决方案中。
  • 将块添加到集合及其所有旋转。 （3次轮换，共4次）
  • 重要的是，每次旋转后，块尽可能向左/向上移动。
• +特殊情况：为接下来的两个案例做同样的逻辑
  • 向右移动一个块并在第一列中添加石头
  • 将一个块移到底部并在第一行中添加石头

性能：

• N=5 ，时间：3ms
• N=10 ，时间：58ms
• N=11 ，时间：166ms
• N=12 ，时间：538ms
• N=13 ，时间：2893ms
• N=14 ，时间：17266ms
• N=15 ，NA（超出堆空间）

代码： https ： //github.com/Samjayyy/logicpuzzles/tree/master/polyominos

Answer 2

只有4,461个大小为10的多项式，所以我们可以全部枚举它们。

从一块石头开始。 要将它扩展到一块石头，请尝试在与现有石头相邻的所有空单元中添加新石头。 递归执行此操作直到达到所需大小。

为了避免重复，请保留我们已经枚举的每个大小的所有多项式的哈希表。 当我们组合一个新的多项式时，我们检查它是否已经在哈希表中。 我们还需要检查它的3个旋转（可能还有它的镜像）。 虽然最终大小的重复检查是唯一严格必要的检查，但在每个步骤检查修剪将产生新多项式的递归分支。

这是一些伪代码：

 polynomino = array of n hashtables function find_polynominoes(n, base): if base.size == n: return for stone in base: for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: new_stone.x = stone.x + dx new_stone.y = stone.y + dy if new_stone not in base: new_polynomino = base + new_stone is_new = true for rotation in [0, 90, 180, 270]: if new_polynomino.rotate(rotation) in polynomino[new_polynomino.size]: is_new = false break if is_new: polynomino[new_polynomino.size].add(new_polynomino) 

Answer 3

最天真的解决方案是从单个X开始，并且对于每次迭代，构建唯一可能的下一状态列表。 从该列表中，通过添加另一个X构建唯一状态列表。 继续这个直到你想要的迭代。

然而，我不确定这是否在N = 10的合理时间内运行。 它可能会根据您的要求而定。

Answer 4

我想我做到了！

编辑：我正在使用SHA-256算法来散列它们，现在它正常工作。

结果如下：

 numberOfStones -> numberOfPolyominos 1 -> 1 2 -> 1 3 -> 2 4 -> 7 5 -> 18 6 -> 60 7 -> 196 8 -> 704 9 -> 2500 10 -> terminated 

这是代码（Java）：

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; /* VPW Template */ public class Main { /** * @param args */ public static void main(String[] args) throws IOException { new Main().start(); } public void start() throws IOException { /* Read the stuff */ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = new String[Integer.parseInt(br.readLine())]; for (int i = 0; i < input.length; ++i) { input[i] = br.readLine(); } /* Process each line */ for (int i = 0; i < input.length; ++i) { processLine(input[i]); } } public void processLine(String line) { int n = Integer.parseInt(line); System.out.println(countPolyminos(n)); } private int countPolyminos(int n) { hashes.clear(); count = 0; boolean[][] matrix = new boolean[n][n]; matrix[n / 2][n / 2] = true; createPolyominos(matrix, n - 1); return count; } private List hashes = new ArrayList(); private int count; private void createPolyominos(boolean[][] matrix, int n) { if (n == 0) { boolean[][] cropped = cropMatrix(matrix); BigInteger hash = hashMatrixOrientationIndependent(cropped); if (!hashes.contains(hash)) { // System.out.println(count + " Found!"); // printMatrix(cropped); // System.out.println(); count++; hashes.add(hash); } return; } for (int x = 0; x < matrix.length; ++x) { for (int y = 0; y < matrix[x].length; ++y) { if (matrix[x][y]) { if (x > 0 && !matrix[x - 1][y]) { boolean[][] clone = copy(matrix); clone[x - 1][y] = true; createPolyominos(clone, n - 1); } if (x < matrix.length - 1 && !matrix[x + 1][y]) { boolean[][] clone = copy(matrix); clone[x + 1][y] = true; createPolyominos(clone, n - 1); } if (y > 0 && !matrix[x][y - 1]) { boolean[][] clone = copy(matrix); clone[x][y - 1] = true; createPolyominos(clone, n - 1); } if (y < matrix[x].length - 1 && !matrix[x][y + 1]) { boolean[][] clone = copy(matrix); clone[x][y + 1] = true; createPolyominos(clone, n - 1); } } } } } public boolean[][] copy(boolean[][] matrix) { boolean[][] b = new boolean[matrix.length][matrix[0].length]; for (int i = 0; i < matrix.length; ++i) { System.arraycopy(matrix[i], 0, b[i], 0, matrix[i].length); } return b; } public void printMatrix(boolean[][] matrix) { for (int y = 0; y < matrix.length; ++y) { for (int x = 0; x < matrix[y].length; ++x) { System.out.print((matrix[y][x] ? 'X' : ' ')); } System.out.println(); } } public boolean[][] cropMatrix(boolean[][] matrix) { int l = 0, t = 0, r = 0, b = 0; // Left left: for (int x = 0; x < matrix.length; ++x) { for (int y = 0; y < matrix[x].length; ++y) { if (matrix[x][y]) { break left; } } l++; } // Right right: for (int x = matrix.length - 1; x >= 0; --x) { for (int y = 0; y < matrix[x].length; ++y) { if (matrix[x][y]) { break right; } } r++; } // Top top: for (int y = 0; y < matrix[0].length; ++y) { for (int x = 0; x < matrix.length; ++x) { if (matrix[x][y]) { break top; } } t++; } // Bottom bottom: for (int y = matrix[0].length - 1; y >= 0; --y) { for (int x = 0; x < matrix.length; ++x) { if (matrix[x][y]) { break bottom; } } b++; } // Perform the real crop boolean[][] cropped = new boolean[matrix.length - l - r][matrix[0].length - t - b]; for (int x = l; x < matrix.length - r; ++x) { System.arraycopy(matrix[x], t, cropped[x - l], 0, matrix[x].length - t - b); } return cropped; } public BigInteger hashMatrix(boolean[][] matrix) { try { MessageDigest md = MessageDigest.getInstance("SHA-256"); md.update((byte) matrix.length); md.update((byte) matrix[0].length); for (int x = 0; x < matrix.length; ++x) { for (int y = 0; y < matrix[x].length; ++y) { if (matrix[x][y]) { md.update((byte) x); } else { md.update((byte) y); } } } return new BigInteger(1, md.digest()); } catch (NoSuchAlgorithmException e) { System.exit(1); return null; } } public BigInteger hashMatrixOrientationIndependent(boolean[][] matrix) { BigInteger hash = hashMatrix(matrix); for (int i = 0; i < 3; ++i) { matrix = rotateMatrixLeft(matrix); hash = hash.add(hashMatrix(matrix)); } return hash; } public boolean[][] rotateMatrixRight(boolean[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; boolean[][] ret = new boolean[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[w - j - 1][i]; } } return ret; } public boolean[][] rotateMatrixLeft(boolean[][] matrix) { /* W and H are already swapped */ int w = matrix.length; int h = matrix[0].length; boolean[][] ret = new boolean[h][w]; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { ret[i][j] = matrix[j][h - i - 1]; } } return ret; } 

Answer 5

这是我在Java中解决同样问题的解决方案。 我可以确认Martijn的数字（见下文）。 我还在粗略的时间内添加了计算结果（2012年中期的Macbook Retina Core i7）。 我认为通过并行化可以实现显着的性能改进。

 numberOfStones -> numberOfPolyominos 1 -> 1 2 -> 1 3 -> 2 4 -> 7 5 -> 18 6 -> 60 7 -> 196 8 -> 704 (3 seconds) 9 -> 2500 (46 seconds) 10 -> 9189 (~14 minutes) 

。

  /* * This class is a solution to the Tetris unique shapes problem. * That is, the game of Tetris has 7 unique shapes. These 7 shapes * are all the possible unique combinations of any 4 adjoining blocks * (ie ignoring rotations). * * How many unique shapes are possible with, say, 7 or n blocks? * * The solution uses recursive back-tracking to construct all the possible * shapes. It uses a HashMap to store unique shapes and to ignore rotations. * It also uses a temporary HashMap so that the program does not needlessly * waste time checking the same path multiple times. * * Even so, this is an exponential run-time solution, with n=10 taking a few * minutes to complete. */ package com.glugabytes.gbjutils; import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TetrisBlocks { private HashMap uShapes; private HashMap tempShapes; /* Get a map of unique shapes for n squares. The keys are string-representations * of each shape, and values are corresponding boolean[][] arrays. * @param squares - number of blocks to use for shapes, eg n=4 has 7 unique shapes */ public Map getUniqueShapes(int squares) { uShapes = new HashMap(); tempShapes = new HashMap(); boolean[][] data = new boolean[squares*2+1][squares*2+1]; data[squares][squares] = true; make(squares, data, 1); //start the process with a single square in the center of a boolean[][] matrix return uShapes; } /* Recursivelly keep adding blocks to the data array until number of blocks(squares) = required size (eg n=4) * Make sure to eliminate rotations. Also make sure not to enter infinite backtracking loops, and also not * needlessly recompute the same path multiple times. */ private void make(int squares, boolean[][] data, int size) { if(size == squares) { //used the required number of squares //get a trimmed version of the array boolean[][] trimmed = trimArray(data); if(!isRotation(trimmed)) { //if a unique piece, add it to unique map uShapes.put(arrayToString(trimmed), trimmed); } } else { //go through the grid 1 element at a time and add a block next to an existing block //do this for all possible combinations for(int iX = 0; iX < data.length; iX++) { for(int iY = 0; iY < data.length; iY++) { if(data[iX][iY] == true) { //only add a block next to an existing block if(data[iX+1][iY] != true) { //if no existing block to the right, add one and recuse data[iX+1][iY] = true; if(!isTempRotation(data)) { //only recurse if we haven't already been on this path before make(squares, data, size+1); tempShapes.put(arrayToString(data), data); //store this path so we don't repeat it later } data[iX+1][iY] = false; } if(data[iX-1][iY] != true) { //repeat by adding a block on the left data[iX-1][iY] = true; if(!isTempRotation(data)) { make(squares, data, size+1); tempShapes.put(arrayToString(data), data); } data[iX-1][iY] = false; } if(data[iX][iY+1] != true) { //repeat by adding a block down data[iX][iY+1] = true; if(!isTempRotation(data)) { make(squares, data, size+1); tempShapes.put(arrayToString(data), data); } data[iX][iY+1] = false; } if(data[iX][iY-1] != true) { //repeat by adding a block up data[iX][iY-1] = true; if(!isTempRotation(data)) { make(squares, data, size+1); tempShapes.put(arrayToString(data), data); } data[iX][iY-1] = false; } } } } } } /** * This function basically removes all rows and columns that have no 'true' flags, * leaving only the portion of the array that contains useful data. * * @param data * @return */ private boolean[][] trimArray(boolean[][] data) { int maxX = 0; int maxY = 0; int firstX = data.length; int firstY = data.length; for(int iX = 0; iX < data.length; iX++) { for (int iY = 0; iY < data.length; iY++) { if(data[iX][iY]) { if(iY < firstY) firstY = iY; if(iY > maxY) maxY = iY; } } } for(int iY = 0; iY < data.length; iY++) { for (int iX = 0; iX < data.length; iX++) { if(data[iX][iY]) { if(iX < firstX) firstX = iX; if(iX > maxX) maxX = iX; } } } boolean[][] trimmed = new boolean[maxX-firstX+1][maxY-firstY+1]; for(int iX = firstX; iX <= maxX; iX++) { for(int iY = firstY; iY <= maxY; iY++) { trimmed[iX-firstX][iY-firstY] = data[iX][iY]; } } return trimmed; } /** * Return a string representation of the 2D array. * * @param data * @return */ private String arrayToString(boolean[][] data) { StringBuilder sb = new StringBuilder(); for(int iX = 0; iX < data.length; iX++) { for(int iY = 0; iY < data[0].length; iY++) { sb.append(data[iX][iY] ? '#' : ' '); } sb.append('\n'); } return sb.toString(); } /** * Rotate an array clockwise by 90 degrees. * @param data * @return */ public boolean[][] rotate90(boolean[][] data) { boolean[][] rotated = new boolean[data[0].length][data.length]; for(int iX = 0; iX < data.length; iX++) { for(int iY = 0; iY < data[0].length; iY++) { rotated[iY][iX] = data[data.length - iX - 1][iY]; } } return rotated; } /** * Checks to see if two 2d boolean arrays are the same * @param a * @param b * @return */ public boolean equal(boolean[][] a, boolean[][] b) { if(a.length != b.length || a[0].length != b[0].length) { return false; } else { for(int iX = 0; iX < a.length; iX++) { for(int iY = 0; iY < a[0].length; iY++) { if(a[iX][iY] != b[iX][iY]) { return false; } } } } return true; } public boolean isRotation(boolean[][] data) { //check to see if it's a rotation of a shape that we already have data = rotate90(data); //+90* String str = arrayToString(data); if(!uShapes.containsKey(str)) { data = rotate90(data); //180* str = arrayToString(data); if(!uShapes.containsKey(str)) { data = rotate90(data); //270* str = arrayToString(data); if(!uShapes.containsKey(str)) { return false; } } } return true; } public boolean isTempRotation(boolean[][] data) { //check to see if it's a rotation of a shape that we already have data = rotate90(data); //+90* String str = arrayToString(data); if(!tempShapes.containsKey(str)) { data = rotate90(data); //180* str = arrayToString(data); if(!tempShapes.containsKey(str)) { data = rotate90(data); //270* str = arrayToString(data); if(!tempShapes.containsKey(str)) { return false; } } } return true; } /** * @param args the command line arguments */ public static void main(String[] args) { TetrisBlocks tetris = new TetrisBlocks(); long start = System.currentTimeMillis(); Map shapes = tetris.getUniqueShapes(8); long end = System.currentTimeMillis(); Iterator it = shapes.keySet().iterator(); while(it.hasNext()) { String shape = (String)it.next(); System.out.println(shape); } System.out.println("Unique Shapes: " + shapes.size()); System.out.println("Time: " + (end-start)); } } 

Answer 6

这是一些计算答案的python。 似乎同意维基百科。 它不是非常快，因为它使用大量的数组搜索而不是哈希表，但它仍然只需要一分钟左右的时间来完成。

 #!/usr/bin/python # compute the canonical representation of polyomino p. # (minimum x and y coordinate is zero, sorted) def canonical(p): mx = min(map(lambda v: v[0], p)) my = min(map(lambda v: v[1], p)) return sorted(map(lambda v: (v[0]-mx, v[1]-my), p)) # rotate p 90 degrees def rotate(p): return canonical(map(lambda v: (v[1], -v[0]), p)) # add one tile to p def expand(p): result = [] for (x,y) in p: for (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)): if p.count((x+dx,y+dy)) == 0: result.append(canonical(p + [(x+dx,y+dy)])) return result polyominos = [[(0,0)]] for i in xrange(1,10): new_polyominos = [] for p in polyominos: for q in expand(p): dup = 0 for r in xrange(4): if new_polyominos.count(q) != 0: dup = 1 break q = rotate(q) if not dup: new_polyominos.append(q) polyominos = new_polyominos print i+1, len(polyominos) 

Answer 7

这是我的完整Python解决方案，灵感来自@ marcog的答案。 它在我的笔记本电脑上打印大小为2..10的多段数，大约2s。

算法很简单：

• 大小1：从一个方格开始
• 大小n + 1 ：取所有大小为n片段并尝试在所有可能的相邻位置添加单个方块。 这样你就可以获得所有新作品。 跳过重复。

主要的加速来自哈希碎片，以快速检查我们是否已经看过一块。

 import itertools from collections import defaultdict n = 10 print("Number of Tetris pieces up to size", n) # Times: # n is number of blocks # - Python O(exp(n)^2): 10 blocks 2.5m # - Python O(exp(n)): 10 blocks 2.5s, 11 blocks 10.9s, 12 block 33s, 13 blocks 141s (800MB memory) # - Other implementation: smallest_piece = [(0, 0)] # We represent a piece as a list of block positions pieces_of_size = { 1: [smallest_piece], } # Returns a list of all possible pieces made by adding one block to given piece def possible_expansions(piece): # No flatMap in Python 2/3: # https://stackoverflow.com/questions/21418764/flatmap-or-bind-in-python-3 positions = set(itertools.chain.from_iterable( [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)] for (x, y) in piece )) # Time complexity O(n^2) can be improved # For each valid position, append to piece expansions = [] for p in positions: if not p in piece: expansions.append(piece + [p]) return expansions def rotate_90_cw(piece): return [(y, -x) for (x, y) in piece] def canonical(piece): min_x = min(x for (x, y) in piece) min_y = min(y for (x, y) in piece) res = sorted((x - min_x, y - min_y) for (x, y) in piece) return res def hash_piece(piece): return hash(tuple(piece)) def expand_pieces(pieces): expanded = [] #[ # 332322396: [[(1,0), (0,-1)], [...]], # 323200700000: [[(1,0), (0,-2)]] #] # Multimap because two different pieces can happen to have the same hash expanded_hashes = defaultdict(list) for piece in pieces: for e in possible_expansions(piece): exp = canonical(e) is_new = True if exp in expanded_hashes[hash_piece(exp)]: is_new = False for rotation in range(3): exp = canonical(rotate_90_cw(exp)) if exp in expanded_hashes[hash_piece(exp)]: is_new = False if is_new: expanded.append(exp) expanded_hashes[hash_piece(exp)].append(exp) return expanded for i in range(2, n + 1): pieces_of_size[i] = expand_pieces(pieces_of_size[i - 1]) print("Pieces with {} blocks: {}".format(i, len(pieces_of_size[i])))