8
\$\begingroup\$

A rigid transformation of a square array is a mapping from square arrays of a certain size to square arrays of the same size, which rearranges the elements of the array such that the distance to each other element remains the same.

If you printed out the matrix on a sheet of paper these are the transforms you could do to it without tearing or folding the paper. Just rotating or flipping it.

For example on the array:

\$ \begin{bmatrix} 1 & 2 \\ 4 & 3 \end{bmatrix} \$

There are 8 ways to rigidly transform it:

\$ \begin{bmatrix} 1 & 2 \\ 4 & 3 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 1 & 4 \end{bmatrix} \begin{bmatrix} 3 & 4 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 4 & 1 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 4 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} 1 & 4 \\ 2 & 3 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 3 & 4 \end{bmatrix} \$

The first \$4\$ are just rotations of the matrix and the second \$4\$ are rotations of it's mirror image.

The following is not a rigid transform:

\$ \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix} \$

Since the relative position of \$2\$ and \$3\$ has changed. \$2\$ used to be opposite \$4\$ and next to \$1\$ and \$3\$, but now it is opposite \$3\$ and next to \$1\$ and \$4\$.

For some starting arrays "different" transforms will give the same array. For example if the starting array is all zeros, any transform of it will always be identical to the starting array. Similarly if we have

\$ \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix} \$

The transforms which mirror it and rotate it a half turn, although they gave different results on the first example, give the same result in this example.

There are never more than \$8\$ unique transforms, the \$4\$ rotations and \$4\$ mirror rotations. Even when we scale the matrix up. So the number of unique results is always less than or equal to 8. In fact a little bit of math can show that it is always 1, 2, 4, or 8.

Task

Take a non-empty square array of non-negative integers as input and return the number of unique ways to continuously transform it.

This is so the goal is to minimize the size of your source code as measured in bytes.

Test cases

5
=> 1
0 0
0 0
=> 1
0 1
1 0
=> 2
0 1
0 0
=> 4
0 1
0 1
=> 4
2 1
1 3
=> 4
3 4
9 1
=> 8
1 2
1 0
=> 8
0 1 0
1 1 1
0 1 0
=> 1
0 2 0
0 0 0
0 0 0
=> 4
0 2 0
2 0 0
0 0 0
=> 4
0 2 0
6 0 0
0 0 0
=> 8
\$\endgroup\$
10
  • \$\begingroup\$ Could you add an example to show all transform of a 3x3 matrix \$ \begin{matrix}1&2&3\\4&5&6\\7&8&9\end{matrix} \$. I can understand the example of 2x2. But I'm not sure how it work on 3x3 matrix. \$\endgroup\$
    – tsh
    Jan 25, 2022 at 12:16
  • \$\begingroup\$ @tsh The transforms are basically the same on a 3x3. They are just the 4 ways to rotate it and the 4 ways to mirror it. I'll add them to the question. \$\endgroup\$
    – Wheat Wizard
    Jan 25, 2022 at 12:18
  • \$\begingroup\$ Are diagonals neighbours? \$\endgroup\$
    – AnttiP
    Jan 25, 2022 at 12:19
  • \$\begingroup\$ @AnttiP Diagonals are not neighbors in the way that directly adjacent elements are. You can consider them neighbors of distance \$\sqrt{2}\$ or not neighbors at all. It doesn't make a difference to the math. \$\endgroup\$
    – Wheat Wizard
    Jan 25, 2022 at 12:21
  • \$\begingroup\$ So just to clarify this transformation is continuous, right? \$\endgroup\$
    – AnttiP
    Jan 25, 2022 at 12:26

8 Answers 8

4
\$\begingroup\$

Jelly, 8 bytes

UZƭ7СQL

Try it online!

UZƭ alternatively performs U (reverse each row) and Z (transpose).

Doing this 7 times and collecting all intermediate results with 7С gets all 8 transforms: {identity, U, UZ, UZU, … UZUZUZU}, and QL (unique+length) counts distinct ones.

\$\endgroup\$
3
\$\begingroup\$

BQN, 16 bytesSBCS

≠∘⍷·⌽¨⊸∾⍉∘⌽⍟(↕4)

Run online!

⍉∘⌽⍟(↕4) Get the 4 rotations.
⌽¨⊸∾ Add the mirror image of each rotation.
≠∘⍷ Count the unique matrices.

\$\endgroup\$
3
\$\begingroup\$

R, 97 94 83 bytes

Or R>=4.1, 69 bytes by replacing two function occurrences with \s.

function(m)length(unique(Map(function(i)m<<-t("if"(i%%2,m,t(m[ncol(m):1,]))),1:8)))

Try it online!

I'm happy with my discovery that unique works well on a list of matrices.

Explanation:

  1. Repeat 8 times a function returning alternating between:
    1. transposition of previous matrix,
    2. previous matrix with reversed rows.
    • Double transposition is needed for the size-1 edge case.
  2. How many unique matrices?
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 bytes

4FDøDí})Ùg

Try it online or verify all test cases.

Explanation:

4F      # Loop 4 times:
  D     #  Duplicate the current matrix
        #  (which will be the implicit input-matrix the first iteration)
   ø    #  Zip/transpose; swapping rows/columns
    D   #  Duplicate again
     í  #  Reverse each row
 })     # After the loop: wrap all nine matrices into a list
   Ù    # Uniquify this list of matrices
    g   # Pop and push the length
        # (after which it is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 27 bytes

F⁴«⊞υθ⊞υ⮌θ≔EθE⮌θ§μλθ»I÷⁸№υθ

Try it online! Link is to verbose version of code. Explanation:

F⁴«

Repeat for each possible rotation.

⊞υθ⊞υ⮌θ

Push the array and its vertical reflection to the predefined empty list.

≔EθE⮌θ§μλθ

Rotate the array.

»I÷⁸№υθ

Count the number of times the array appears in the list. Each unique array in the list must appear that number of times. Divide that into 8 to give the number of unique arrays, and output the result.

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

Python, 58 bytes

lambda l:len({l:=(l[::-1],(*zip(*l),))[p]for p in(0,1)*4})

Attempt This Online!

Essentially a port of my answer to a related (hexagonal) challenge, It generates all 8 symmetries from 2 reflections (up-down and transpose).

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

JavaScript (ES6),  85  81 bytes

Saved 4 bytes thanks to @l4m2

f=m=>new Set([...f+1].map(c=>(m=m.map((_,y)=>m.map(r=>+c?r[y]:r.pop())))+0)).size

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Could you explain the [...f+1] trick? It seems really interesting but I don't get how it works. \$\endgroup\$
    – ophact
    Jan 25, 2022 at 14:57
  • 2
    \$\begingroup\$ @ThisFieldIsRequired This is just a short way of producing an array of characters. What we really need is [0,0,0,0,1,0,0,0] but we don't care if duplicate rotations and reflections are executed, so the pattern that we get with [...f+1] works just as well. \$\endgroup\$
    – Arnauld
    Jan 25, 2022 at 15:26
  • \$\begingroup\$ Thanks, that seems cool. \$\endgroup\$
    – ophact
    Jan 25, 2022 at 15:40
  • \$\begingroup\$ 81 \$\endgroup\$
    – l4m2
    Jan 25, 2022 at 18:05
1
\$\begingroup\$

Pari/GP, 48 bytes

a->#Set([a=if(i%2,Mat(Vecrev(a)),a~)|i<-[1..8]])

Try it online!

A port of @loopy walt's Python answer.

\$\endgroup\$

Your Answer

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

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