Programming Contest Question: Counting Polyominos

Question

Please see my own answer, I think I did it!

---

Hi,

An example question for a programming contest was to write a program that finds out how much polyominos are possible with a given number of stones.

So for two stones (n = 2) there is only one polyominos:

XX

You might think this is a second solution:

X
X

But it isn't. The polyominos are not unique if you can rotate them.

So, for 4 stones (n = 4), there are 7 solutions:

X
X   XX   X    X     X   X
X   X    XX   X    XX   XX   XX
X   X    X    XX   X     X   XX

The application has to be able to find the solution for 1 <= n <=10

PS: Using the list of polyominos on Wikipedia isn't allowed ;)

EDIT: Of course the question is: How to do this in Java, C/C++, C#

---

I started this project in Java. But then I had to admit I didn't know how to build polyominos using an efficient algorithm.

This is what I had so far:

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

Just solved this as well in java. Since all here appear to have performance issues. I give you mine as well.

Board reprsentation:

2 arrays of integers. 1 for the rows and 1 for the columns.

• Rotation: column[i]=row[size-(i+1)], row[i] = reverse(column[i]) where reverse is the bits reversed according to the size (for size = 4 and first 2 bits are taken: rev(1100) = 0011)
• Shifting block: row[i-1] = row[i], col[i]<<=1
• Check if bit is set: (row[r] & (1<<c)) > 0
• Board uniqueness: The board is unique when the array row is unique.
• Board hash: Hashcode of the array row
• ..

So this makes all operations fast. Many of them would have been O(size²) in the 2D array representation instead of now O(size).

Algorithm:

• Start with the block of size 1
• For each size start from the blocks with 1 stone less.
• If it's possible to add the stone. Check if it was already added to the set.
• If it's not yet added. Add it to the solution of this size.
  • add the block to the set and all its rotations. (3 rotations, 4 in total)
  • Important, after each rotation shift the block as left/top as possible.
• +Special cases: do the same logic for the next 2 cases
  • shift block one to the right and add stone in first column
  • shift block one to the bottom and add stone in first row

Performance:

• N=5 , time: 3ms
• N=10, time: 58ms
• N=11, time: 166ms
• N=12, time: 538ms
• N=13, time: 2893ms
• N=14, time:17266ms
• N=15, NA (out of heapspace)

Code: https://github.com/Samjayyy/logicpuzzles/tree/master/polyominos

Answer 2

There are only 4,461 polynominoes of size 10, so we can just enumerate them all.

Start with a single stone. To expand it by one stone, try add the new stone in at all empty cells that neighbour an existing stone. Do this recursively until reaching the desired size.

To avoid duplicates, keep a hash table of all polynominoes of each size we've already enumerated. When we put together a new polynomino, we check that its not already in the hash table. We also need to check its 3 rotations (and possibly its mirror image). While duplicate checking at the final size is the only strictly necessary check, checking at each step prunes recursive branches that will yield a new polynomino.

Here's some pseudo-code:

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)