Rotation invariant fingerprinting











up vote
7
down vote

favorite












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]]









share|improve this question






















  • Related.
    – BMO
    2 hours ago















up vote
7
down vote

favorite












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]]









share|improve this question






















  • Related.
    – BMO
    2 hours ago













up vote
7
down vote

favorite









up vote
7
down vote

favorite











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]]









share|improve this question













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]]






code-golf array-manipulation hashing polyomino






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked 2 hours ago









BMO

11.1k21981




11.1k21981












  • Related.
    – BMO
    2 hours ago


















  • Related.
    – BMO
    2 hours ago
















Related.
– BMO
2 hours ago




Related.
– BMO
2 hours ago










5 Answers
5






active

oldest

votes

















up vote
4
down vote













Python 3, 87 77 62 56 bytes



f=lambda l,z=4:z and f(tuple(zip(*l))[::-1],z-1)^hash(l)


Alternate version, XOR 1:



f=lambda l,z=0:z>3or f(tuple(zip(*l))[::-1],z+1)^hash(l)


Hashes each of the 4 rotations, then XORs them together. (Thanks, BMO!)






share|improve this answer























  • f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
    – BMO
    1 hour ago












  • I forgot you could do f=! Thanks.
    – wizzwizz4
    1 hour ago










  • @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
    – wizzwizz4
    1 hour ago






  • 2




    Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
    – Arnauld
    58 mins ago






  • 1




    Answers that will fail for some specific input are invalid.
    – Dennis
    21 mins ago


















up vote
3
down vote














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!






share|improve this answer























  • 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.
    – nedla2004
    1 hour ago










  • @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
    – FlipTack
    1 hour ago










  • @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
    – FlipTack
    1 hour ago










  • I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
    – nedla2004
    1 hour ago


















up vote
1
down vote














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.






share|improve this answer























  • when i read the challenge i knew this would happen :)
    – ngn
    1 hour ago


















up vote
1
down vote














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






share|improve this answer




























    up vote
    0
    down vote














    K (ngn/k), 16 bytes



    {x@*<x:4(+|:)x}


    Try it online!



    min of rotations



    { } function with argument x



    +|: rotate, i.e. transpose (+) composed with reverse (|); the : after the last verb forces it to be monadic, thus making the whole composition monadic; other verbs are implicitly monadic



    4( ) apply 4 times preserving intermediate results



    x: assign to x; the argument is an ordinary variable, here we reuse it



    < ascend, a.k.a. grade up, a.k.a. sort-ascending permutation



    * first



    x@ index x with that






    share|improve this answer























      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ifUsing("editor", function () {
      StackExchange.using("externalEditor", function () {
      StackExchange.using("snippets", function () {
      StackExchange.snippets.init();
      });
      });
      }, "code-snippets");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "200"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: false,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f177662%2frotation-invariant-fingerprinting%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      5 Answers
      5






      active

      oldest

      votes








      5 Answers
      5






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      4
      down vote













      Python 3, 87 77 62 56 bytes



      f=lambda l,z=4:z and f(tuple(zip(*l))[::-1],z-1)^hash(l)


      Alternate version, XOR 1:



      f=lambda l,z=0:z>3or f(tuple(zip(*l))[::-1],z+1)^hash(l)


      Hashes each of the 4 rotations, then XORs them together. (Thanks, BMO!)






      share|improve this answer























      • f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
        – BMO
        1 hour ago












      • I forgot you could do f=! Thanks.
        – wizzwizz4
        1 hour ago










      • @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
        – wizzwizz4
        1 hour ago






      • 2




        Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
        – Arnauld
        58 mins ago






      • 1




        Answers that will fail for some specific input are invalid.
        – Dennis
        21 mins ago















      up vote
      4
      down vote













      Python 3, 87 77 62 56 bytes



      f=lambda l,z=4:z and f(tuple(zip(*l))[::-1],z-1)^hash(l)


      Alternate version, XOR 1:



      f=lambda l,z=0:z>3or f(tuple(zip(*l))[::-1],z+1)^hash(l)


      Hashes each of the 4 rotations, then XORs them together. (Thanks, BMO!)






      share|improve this answer























      • f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
        – BMO
        1 hour ago












      • I forgot you could do f=! Thanks.
        – wizzwizz4
        1 hour ago










      • @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
        – wizzwizz4
        1 hour ago






      • 2




        Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
        – Arnauld
        58 mins ago






      • 1




        Answers that will fail for some specific input are invalid.
        – Dennis
        21 mins ago













      up vote
      4
      down vote










      up vote
      4
      down vote









      Python 3, 87 77 62 56 bytes



      f=lambda l,z=4:z and f(tuple(zip(*l))[::-1],z-1)^hash(l)


      Alternate version, XOR 1:



      f=lambda l,z=0:z>3or f(tuple(zip(*l))[::-1],z+1)^hash(l)


      Hashes each of the 4 rotations, then XORs them together. (Thanks, BMO!)






      share|improve this answer














      Python 3, 87 77 62 56 bytes



      f=lambda l,z=4:z and f(tuple(zip(*l))[::-1],z-1)^hash(l)


      Alternate version, XOR 1:



      f=lambda l,z=0:z>3or f(tuple(zip(*l))[::-1],z+1)^hash(l)


      Hashes each of the 4 rotations, then XORs them together. (Thanks, BMO!)







      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited 1 hour ago

























      answered 1 hour ago









      wizzwizz4

      1,2071034




      1,2071034












      • f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
        – BMO
        1 hour ago












      • I forgot you could do f=! Thanks.
        – wizzwizz4
        1 hour ago










      • @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
        – wizzwizz4
        1 hour ago






      • 2




        Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
        – Arnauld
        58 mins ago






      • 1




        Answers that will fail for some specific input are invalid.
        – Dennis
        21 mins ago


















      • f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
        – BMO
        1 hour ago












      • I forgot you could do f=! Thanks.
        – wizzwizz4
        1 hour ago










      • @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
        – wizzwizz4
        1 hour ago






      • 2




        Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
        – Arnauld
        58 mins ago






      • 1




        Answers that will fail for some specific input are invalid.
        – Dennis
        21 mins ago
















      f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
      – BMO
      1 hour ago






      f=lambda l,z=0,h=hash:z>3or h(l)^f(tuple(zip(*l))[::-1],z+1) should do almost the same, just XORing the it with a 1 in the end.
      – BMO
      1 hour ago














      I forgot you could do f=! Thanks.
      – wizzwizz4
      1 hour ago




      I forgot you could do f=! Thanks.
      – wizzwizz4
      1 hour ago












      @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
      – wizzwizz4
      1 hour ago




      @BMO I've removed the XOR 1 at the end. Unfortunately a space is needed, so it doesn't shave off any bytes.
      – wizzwizz4
      1 hour ago




      2




      2




      Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
      – Arnauld
      58 mins ago




      Does it really enforce the uniqueness of each fingerprint? The larger the polyominoes, the higher the probability of a hash collision. (@BMO Not sure how strict the challenge is about that, though.)
      – Arnauld
      58 mins ago




      1




      1




      Answers that will fail for some specific input are invalid.
      – Dennis
      21 mins ago




      Answers that will fail for some specific input are invalid.
      – Dennis
      21 mins ago










      up vote
      3
      down vote














      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!






      share|improve this answer























      • 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.
        – nedla2004
        1 hour ago










      • @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
        – FlipTack
        1 hour ago










      • @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
        – FlipTack
        1 hour ago










      • I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
        – nedla2004
        1 hour ago















      up vote
      3
      down vote














      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!






      share|improve this answer























      • 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.
        – nedla2004
        1 hour ago










      • @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
        – FlipTack
        1 hour ago










      • @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
        – FlipTack
        1 hour ago










      • I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
        – nedla2004
        1 hour ago













      up vote
      3
      down vote










      up vote
      3
      down vote










      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!






      share|improve this answer















      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!







      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited 1 hour ago

























      answered 1 hour ago









      FlipTack

      9,09834089




      9,09834089












      • 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.
        – nedla2004
        1 hour ago










      • @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
        – FlipTack
        1 hour ago










      • @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
        – FlipTack
        1 hour ago










      • I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
        – nedla2004
        1 hour ago


















      • 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.
        – nedla2004
        1 hour ago










      • @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
        – FlipTack
        1 hour ago










      • @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
        – FlipTack
        1 hour ago










      • I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
        – nedla2004
        1 hour ago
















      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.
      – nedla2004
      1 hour ago




      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.
      – nedla2004
      1 hour ago












      @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
      – FlipTack
      1 hour ago




      @nedla2004 That can only be run once, and then gets dodgy as M is already populated...
      – FlipTack
      1 hour ago












      @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
      – FlipTack
      1 hour ago




      @nedla2004 ... but accounting for the problem with M[-4:] can get you to the same byte count.
      – FlipTack
      1 hour ago












      I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
      – nedla2004
      1 hour ago




      I see, the test I was using was just checking inputs with the same "hash", so I never ran into that. That makes sense.
      – nedla2004
      1 hour ago










      up vote
      1
      down vote














      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.






      share|improve this answer























      • when i read the challenge i knew this would happen :)
        – ngn
        1 hour ago















      up vote
      1
      down vote














      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.






      share|improve this answer























      • when i read the challenge i knew this would happen :)
        – ngn
        1 hour ago













      up vote
      1
      down vote










      up vote
      1
      down vote










      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.






      share|improve this answer















      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.







      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited 2 hours ago

























      answered 2 hours ago









      Erik the Outgolfer

      31.1k429102




      31.1k429102












      • when i read the challenge i knew this would happen :)
        – ngn
        1 hour ago


















      • when i read the challenge i knew this would happen :)
        – ngn
        1 hour ago
















      when i read the challenge i knew this would happen :)
      – ngn
      1 hour ago




      when i read the challenge i knew this would happen :)
      – ngn
      1 hour ago










      up vote
      1
      down vote














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






      share|improve this answer

























        up vote
        1
        down vote














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






        share|improve this answer























          up vote
          1
          down vote










          up vote
          1
          down vote










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






          share|improve this answer













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







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 42 mins ago









          xnor

          89.6k18184439




          89.6k18184439






















              up vote
              0
              down vote














              K (ngn/k), 16 bytes



              {x@*<x:4(+|:)x}


              Try it online!



              min of rotations



              { } function with argument x



              +|: rotate, i.e. transpose (+) composed with reverse (|); the : after the last verb forces it to be monadic, thus making the whole composition monadic; other verbs are implicitly monadic



              4( ) apply 4 times preserving intermediate results



              x: assign to x; the argument is an ordinary variable, here we reuse it



              < ascend, a.k.a. grade up, a.k.a. sort-ascending permutation



              * first



              x@ index x with that






              share|improve this answer



























                up vote
                0
                down vote














                K (ngn/k), 16 bytes



                {x@*<x:4(+|:)x}


                Try it online!



                min of rotations



                { } function with argument x



                +|: rotate, i.e. transpose (+) composed with reverse (|); the : after the last verb forces it to be monadic, thus making the whole composition monadic; other verbs are implicitly monadic



                4( ) apply 4 times preserving intermediate results



                x: assign to x; the argument is an ordinary variable, here we reuse it



                < ascend, a.k.a. grade up, a.k.a. sort-ascending permutation



                * first



                x@ index x with that






                share|improve this answer

























                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote










                  K (ngn/k), 16 bytes



                  {x@*<x:4(+|:)x}


                  Try it online!



                  min of rotations



                  { } function with argument x



                  +|: rotate, i.e. transpose (+) composed with reverse (|); the : after the last verb forces it to be monadic, thus making the whole composition monadic; other verbs are implicitly monadic



                  4( ) apply 4 times preserving intermediate results



                  x: assign to x; the argument is an ordinary variable, here we reuse it



                  < ascend, a.k.a. grade up, a.k.a. sort-ascending permutation



                  * first



                  x@ index x with that






                  share|improve this answer















                  K (ngn/k), 16 bytes



                  {x@*<x:4(+|:)x}


                  Try it online!



                  min of rotations



                  { } function with argument x



                  +|: rotate, i.e. transpose (+) composed with reverse (|); the : after the last verb forces it to be monadic, thus making the whole composition monadic; other verbs are implicitly monadic



                  4( ) apply 4 times preserving intermediate results



                  x: assign to x; the argument is an ordinary variable, here we reuse it



                  < ascend, a.k.a. grade up, a.k.a. sort-ascending permutation



                  * first



                  x@ index x with that







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited 51 mins ago

























                  answered 1 hour ago









                  ngn

                  6,70312459




                  6,70312459






























                      draft saved

                      draft discarded




















































                      If this is an answer to a challenge…




                      • …Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.


                      • …Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
                        Explanations of your answer make it more interesting to read and are very much encouraged.


                      • …Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.



                      More generally…




                      • …Please make sure to answer the question and provide sufficient detail.


                      • …Avoid asking for help, clarification or responding to other answers (use comments instead).






                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f177662%2frotation-invariant-fingerprinting%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Ellipse (mathématiques)

                      Quarter-circle Tiles

                      Mont Emei