Problem #247

Polyominoes 1
Public 07/03/15 11xp Programming 26.7%

A polyomino is a geometric figure obtained by joining equal squares edge by edge.
We consider that one side of each square is painted: when comparing two polyominoes for symetry, the painted sides must always stay up.
Two polyominoes are equal if they differ only by a rotation of a multiple of $ \frac{\pi}{2} $

To sort the polyominoes, we define the "canonical value" of a polyomino as follow:
  • A polyomino is represented by a matrix of 0 and 1
  • We consider all 4 rotations and keep those where the matrix is such as the number of rows is $\le$ the number of columns.
  • We add a column of 0 at the end, flatten the values and consider them as a binary representation of some integer. The canonical value is the smallest of these integers.
For example, consider the polyomino
It can be represented either by $ \left( \begin{array}{} 0 & 0 & 1 \\ 1 & 1 & 1 \end{array} \right) $ or by $ \left( \begin{array}{} 1 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) $

The first representation yields the values $ \{ 0, 0, 1, 0, 1, 1, 1, 0 \}$ = 46
The second representation yields the values $ \{ 1, 1, 1, 0, 1, 0, 0, 0 \}$ = 232
Thus, the canonical value for this polyomino is 46.

With 4 squares, there are 7 possible polyominoes (sorted by their canonical values):
  • 30
  • 46
  • 54
  • 78
  • 108
  • 142
  • 198

How many polyominoes with 8 squares are there?
What is the canonical value of the 666-th poylyomino?

Format answer: Count,Value

[My timing: 40 sec]



You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]