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 $mtimes 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 $5times 1$ bar:

[[1,1,1,1,1]]

[[1],[1],[1],[1],[1]]

A $2times 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]]

Python 2, 48 bytes

f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1))

Try it online!

Takes the largest of the four rotations in terms of list comparison. Based on FlipTack's solution.

The code uses Python 2's ability to compare objects of different types. The base case value of 0 is harmless for max because it's smaller than any list. Also, zip produces a list of tuples while the input is a list of lists, but tuples are bigger than lists so the input list-of-lists is never a contender. This is why we rotate 5 times rather than 4, so that we get back to a tuplified version of the initial list. (Taking a list of tuples would also work, if that's an allowed form of input.)

Python 3, 63 bytes

def f(m):M=;exec("m=[*zip(*m[::-1])];M+=m,;"*4);return min(M)

Try it online!

Finds the rotation with the lexographical minimum, and prints that.

A lambda form comes in at the same byte count:

lambda m,M=:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M[-4:])

Try it online!

Jelly, 5 bytes

ZU$ƬṂ

Try it online!

Full program.

Simply generates all possible rotations and picks the lexicographical minimum.

Note that singleton lists aren't wrapped in in the output. That doesn't matter, since the only case where singleton lists would exist in the input would be a vertical line (including the unit polyomino), which is the same as a horizontal line with the same size (where the ones aren't wrapped). The only case where the outer will not exist either is the unit polyomino.

Clean, 136 bytes

import StdEnv,Data.List

r=reverse;t=transpose;f=flatten

$l=[if((a==b)==(c==d))'x''X'\a<-f l&b<-f(r(map r l))&c<-f(r(t l))&d<-f(t(r l))]

Try it online!

Includes test verifier.

K (ngn/k), 16 bytes

{a@*<a:3{+|x}x}

Try it online!

min of rotations

{ } function with argument x

{+|x} rotate, i.e. reverse (|) and transpose (+)

3{ } apply 3 times preserving intermediate results; this returns a list of the 4 rotations

a: assign to a

< ascend (compute the sort-ascending permutation)

* first

a@ index a with that