15
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
Challenge
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
Examples
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]]
The J-tetromino:
[[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:
[[1]]
A \$5\times 1\$ bar:
[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]
A \$2\times 2\$ corner:
[[1,1],[1,0]]
[[1,0],[1,1]]
[[0,1],[1,1]]
[[1,1],[0,1]]
W-pentomino:
[[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]]
Related. – ბიმო – 2018-12-16T17:20:14.327
If I always output
""
(the empty string), have I satisfied all the requirements? – Daniel Wagner – 2018-12-17T12:13:05.743@DanielWagner: "[..] for any two polyominos from two distinct classes [the fingerprints] must differ" - so no, that would be invalid. – ბიმო – 2018-12-17T14:59:31.430
Is outputting all possible rotations of an array, consistently sorted valid? Example
– Shaggy – 2018-12-17T17:12:40.4171@Shaggy: Yes, that would meet all the criteria. – ბიმო – 2018-12-17T17:15:38.587