Imagine we have some polyomino and would like to uniquely identify them, however the polyominos can be rotated, so blindly hashing them won't give us the same fingerprint for a piece and a rotation thereof (in general).
For example if we have the L-tetromino
x x xx
we would like it to have the same fingerprint as any of these:
xx x x xxx xxx , x or x
Note: We only allow rotations on the plane (ie. they are one-sided polyominos) and therefore the following polyomino would be a different one:
x x xx
The task for this challenge is to implement a fingerprinting-function/program which takes an \$m\times n\$ Boolean/\$0,1\$-valued matrix/list of lists/string/.. encoding a polyomino and returns a string - the fingerprint of a polyomino. The fingerprint must be equal for all of the possible rotations (in general 4).
Input / Output
- \$m \geq 1\$ and \$n \geq 1\$ (ie. no empty polyomino)
- you're guaranteed that \$m,n\$ are as small as possible (ie. all \$0\$ are trimmed to fit \$m\$ and \$n\$
- you're guaranteed that the input is
- simply connected
- has no holes
- output must be a string which is the same for each possible rotation of a polyomino
Here are some equivalence classes, for each class the fingerprint must be the same & for any two polyominos from two distinct classes they must differ.
The rotations of the L-tetromino from the example:
[[1,0],[1,0],[1,1]] [[0,0,1],[1,1,1]] [[1,1],[0,1],[0,1]] [[1,1,1],[1,0,0]]
[[0,1],[0,1],[1,1]] [[1,1,1],[0,0,1]] [[1,1],[1,0],[1,0]] [[1,0,0],[1,1,1]]
The unit polyomino:
A \$5\times 1\$ bar:
A \$2\times 2\$ corner:
[[1,1],[1,0]] [[1,0],[1,1]] [[0,1],[1,1]] [[1,1],[0,1]]
[[1,0,0],[1,1,0],[0,1,1]] [[0,0,1],[0,1,1],[1,1,0]] [[1,1,0],[0,1,1],[0,0,1]] [[0,1,1],[1,1,0],[1,0,0]]