RoseCode

Problem #247

Polyominoes 1
 Public ★(x8) 07/03/15 by Philippe_57721 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?

[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.

## Contact

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