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

Question

请看我自己的答案,我想我做到了!

---

嗨,

编程竞赛的一个示例问题是编写一个程序,找出给定数量的宝石可能有多少多边形.

所以对于两块石头(n = 2),只有一个多面体:

XX

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

X
X

但事实并非如此.如果您可以旋转它们,则polyominos不是唯一的.

因此,对于4个宝石(n = 4),有7个解决方案:

X
X   XX   X    X     X   X
X   X    XX   X    XX   XX   XX
X   X    X    XX   X     X   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<Integer> hashes = new ArrayList<Integer>();
    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 < 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; 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 - 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

只有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 2

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

\n\n

董事会代表：

\n\n

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

\n\n

\n
• 旋转： column[i]=row[size-(i+1)]，row[i] = reverse(column[i])其中反向是根据大小反转的位（对于大小 = 4 且采用前 2 位rev(1100) = 0011：）
\n
• 移动块： row[i-1] = row[i] ,col[i]<<=1
\n
• 检查位是否已设置： (row[r] & (1<<c)) > 0
\n
• 板唯一性：当阵列行唯一时，板是唯一的。
\n
• Board hash：数组行的哈希码
\n
• ..
\n

\n\n

所以这使得所有操作都变得很快。其中许多本来是O(size\xc2\xb2)二维数组表示形式，而不是现在O(size)。

\n\n

算法：

\n\n

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

\n\n

表现：

\n\n

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

\n\n

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

\n