14
\$\begingroup\$

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]]
\$\endgroup\$
5
  • \$\begingroup\$ Related. \$\endgroup\$ Dec 16, 2018 at 17:20
  • \$\begingroup\$ If I always output "" (the empty string), have I satisfied all the requirements? \$\endgroup\$ Dec 17, 2018 at 12:13
  • \$\begingroup\$ @DanielWagner: "[..] for any two polyominos from two distinct classes [the fingerprints] must differ" - so no, that would be invalid. \$\endgroup\$ Dec 17, 2018 at 14:59
  • \$\begingroup\$ Is outputting all possible rotations of an array, consistently sorted valid? Example \$\endgroup\$
    – Shaggy
    Dec 17, 2018 at 17:12
  • 1
    \$\begingroup\$ @Shaggy: Yes, that would meet all the criteria. \$\endgroup\$ Dec 17, 2018 at 17:15

8 Answers 8

7
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ Rewriting as a lambda can get you to 58. lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M). Works because exec always returns None. \$\endgroup\$
    – nedla2004
    Dec 16, 2018 at 17:54
  • \$\begingroup\$ @nedla2004 That can only be run once, and then gets dodgy as M is already populated... \$\endgroup\$
    – FlipTack
    Dec 16, 2018 at 17:55
  • \$\begingroup\$ @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count. \$\endgroup\$
    – FlipTack
    Dec 16, 2018 at 18:10
  • \$\begingroup\$ I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense. \$\endgroup\$
    – nedla2004
    Dec 16, 2018 at 18:11
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ when i read the challenge i knew this would happen :) \$\endgroup\$
    – ngn
    Dec 16, 2018 at 18:18
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

Japt -g, 6 bytes

4Æ=zÃñ

Try it

           :Implicit input of 2d-array U
4Æ         :Map the range [0,4)
   z       :  Rotate U 90 degrees
  =        :  Reassign to U
    Ã      :End map
     ñ     :Sort
           :Implicit output of first element
\$\endgroup\$
3
  • \$\begingroup\$ Is the -g flag necessary? Sort should mean that all initial rotations end up with the same list so that full list should work fine as the fingerprint unless I'm missing something. \$\endgroup\$ Dec 17, 2018 at 15:58
  • \$\begingroup\$ @KamilDrakari, you could well be right - like I said, I'm not sure I fully understood the challenge. No harm leaving it in, though, it's not costing any bytes. \$\endgroup\$
    – Shaggy
    Dec 17, 2018 at 17:11
  • \$\begingroup\$ @KamilDrakari: It is not necessary, but it's no harm either as it's not counted towards the bytecount. \$\endgroup\$ Dec 17, 2018 at 17:17
1
\$\begingroup\$

J, 16 bytes

-2 bytes thanks to Shaggy

[:/:~|.@|:^:(<4)

Try it online!

J, 18 bytes

0{[:/:~|.@|:^:(<4)

Try it online!

Returns the first item in the list of the lexicograpically sorted rotations of the polyomino.

Explanation:

            ^:(<4)  - do the verb on the left 4 times, storing all the steps
       |.@|:        - tranpose and reverse
    /:~             - sort up the 4 matrices
  [:                - cap the fork
0{                  - take the first matrix  
\$\endgroup\$
0
0
\$\begingroup\$

05AB1E, 10 8 bytes

3FÂø})Σ˜

-2 bytes thanks to @Shaggy.

Try it online or verify all test cases.

Explanation:

3F  }       # Loop 3 times
  Â         #  Bifurcate (short for Duplicate & Reverse) the top of the stack
            #  (which is the input-matrix implicitly the first iteration)
   ø        #  Transpose: swap rows/columns
     )      # After the loop, wrap everything on the stack in a list
      Σ˜    # Sort this list of matrices by their flattened array (and output implicitly)

NOTE: Taking the minimum with ß or W will implicitly flatten, so will output 0. And sorting with { doesn't seem to work for a list of matrices, which is why I use Σ˜ instead.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @Shaggy Thanks! :) In that case the last two bytes can be removed, since the } is done implicitly if nothing comes after it. \$\endgroup\$ Dec 17, 2018 at 17:31
  • 1
    \$\begingroup\$ Today I learned something about 05AB1E! :) It's the same in Japt. \$\endgroup\$
    – Shaggy
    Dec 17, 2018 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.