Dihedral group D4 composition with custom labels

Question

The dihedral group \$D_4\$ is the symmetry group of the square, that is the moves that transform a square to itself via rotations and reflections. It consists of 8 elements: rotations by 0, 90, 180, and 270 degrees, and reflections across the horizontal, vertical, and two diagonal axes.

The images are all from this lovely page by Larry Riddle.

This challenge is about composing these moves: given two moves, output the move that's equivalent to doing them one after another. For instance, doing move 7 followed by move 4 is the same as doing move 5.

Note that switching the order to move 4 then move 7 produces move 6 instead.

The results are tabulated below; this is the Cayley table of the group \$D_4\$. So for example, inputs \$7, 4\$ should produce output \$5\$.

\begin{array}{*{20}{c}} {} & {\begin{array}{*{20}{c}} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \end{array} } \\ {\begin{array}{*{20}{c}} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ \end{array} } & {\boxed{\begin{array}{*{20}{c}} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 4 & 1 & 8 & 7 & 5 & 6\\ 3 & 4 & 1 & 2 & 6 & 5 & 8 & 7\\ 4 & 1 & 2 & 3 & 7 & 8 & 6 & 5\\ 5 & 7 & 6 & 8 & 1 & 3 & 2 & 4\\ 6 & 8 & 5 & 7 & 3 & 1 & 4 & 2\\ 7 & 6 & 8 & 5 & 4 & 2 & 1 & 3\\ 8 & 5 & 7 & 6 & 2 & 4 & 3 & 1\\ \end{array} }} \\ \end{array}

Challenge

Your goal is to implement this operation in as few bytes as possible, but in addition to the code, you also choose the labels that represent the moves 1 through 8. The labels must be 8 distinct numbers from 0 to 255, or the 8 one-byte characters their code points represent.

Your code will be given two of the labels from the 8 you've chosen, and must output the label that corresponds to their composition in the dihedral group \$D_4\$.

Example

Say you've chosen the characters C, O, M, P, U, T, E, R for moves 1 through 8 respectively. Then, your code should implement this table.

\begin{array}{*{20}{c}} {} & {\begin{array}{*{20}{c}} \, C \, & \, O \, & M \, & P \, & U \, & \, T \, & \, E \, & R \, \\ \end{array} } \\ {\begin{array}{*{20}{c}} C \\ O \\ M \\ P \\ U \\ T \\ E \\ R \\ \end{array} } & {\boxed{\begin{array}{*{20}{c}} C & O & M & P & U & T & E & R \\ O & M & P & C & R & E & U & T\\ M & P & C & O & T & U & R & E\\ P & C & O & M & E & R & T & U\\ U & E & T & R & C & M & O & P\\ T & R & U & E & M & C & P & O\\ E & T & R & U & P & O & C & M\\ R & U & E & T & O & P & M & C\\ \end{array} }} \\ \end{array}

Given inputs E and P, you should output U. Your inputs will always be two of the letters C, O, M, P, U, T, E, R, and your output should always be one of these letters.

Text table for copying

1 2 3 4 5 6 7 8
2 3 4 1 8 7 5 6
3 4 1 2 6 5 8 7
4 1 2 3 7 8 6 5
5 7 6 8 1 3 2 4
6 8 5 7 3 1 4 2
7 6 8 5 4 2 1 3
8 5 7 6 2 4 3 1

Answer 1

Ruby, 18 bytes

->a,b{a+b*~0**a&7}

Ungolfed

->a,b{ (a+b*(-1)**a) % 8}  
# for operator precedence reasons, 
#-1 is represented as ~0 in the golfed version 

Try it online!

Uses the following coding numbers 0 to 7

In order native to the code:

Native     Effect                    Codes per
Code                                 Question
0          rotate 0 anticlockwise    1C
1 /        flip in y=x               7E
2 /|       rotate 90 anticlockwise   2O
3 /|/      flip in x axis            5U
4 /|/|     rotate 180 anticlockwise  3M
5 /|/|/    flip in y=-x              8R
6 /|/|/|   rotate 270 anticlockwise  4P
7 /|/|/|/  flip in y axis            6T

In order per the question

Native     Effect                    Codes per
Code                                 Question
0          rotate 0 anticlockwise    1C
2 /|       rotate 90 anticlockwise   2O
4 /|/|     rotate 180 anticlockwise  3M
6 /|/|/|   rotate 270 anticlockwise  4P
3 /|/      flip in x axis            5U
7 /|/|/|/  flip in y axis            6T
1 /        flip in y=x               7E
5 /|/|/    flip in y=-x              8R

Explanation

/ represents a flip in the line y=x and | represents a flip in the y axis.

It is possible to generate any of the symmetries of the group D4 by alternately flipping in these two lines For example / followed by | gives /| which is a rotation of 90 degrees anticlockwise.

The total number of consecutive flips gives a very convenient representation for arithmetic manipulation.

If the first move is a rotation, we can simply add the number of flips:

Rotate 90 degrees   +  Rotate 180 degrees = Rotate 270 degrees
/|                     /|/|                 /|/|/|

Rotate 90 degress   +  Flip in y=x        = Flip in x axis   
/|                    /                     /|/

If the first move is a reflection, we find we have some identical reflections / and | symbols next to each other. As reflection is self inverse we can cancel out these flips one by one. So we need to subtract one move from the other

Flip in x axis     +  Flip in y=x        = Rotate 90 degrees
/|/                   /                    /|/ / (cancels to) /|

Flip in x axis     +  Rotate 90 degrees  = Flip in y=x
/|/                   /|                   /|/ /| (cancels to ) / 

Answer 2

Wolfram Language (Mathematica), 31 bytes

Using integers \$0, 5, 2, 7, 1, 3, 6, 4\$ as labels.

BitXor[##,2Mod[#,2]⌊#2/4⌋]&

Try it online!

Explanation:

The Dihedral group \$D_4\$ is isomorphic to the unitriangular matrix group of degree three over the field \$\mathbb{F}_2\$:

$$D_4 \cong U(3,2) := \left\{\begin{pmatrix} 1 & a & b \\ 0 & 1 & c \\ 0 & 0 & 1 \end{pmatrix} \mid a,b,c \in \mathbb{F}_2\right\}.$$

And we have

$$\begin{pmatrix} 1 & a_1 & b_1 \\ 0 & 1 & c_1 \\ 0 & 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 & a_2 & b_2 \\ 0 & 1 & c_2 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & a_1+a_2 & b_1+b_2+a_1c_2 \\ 0 & 1 & c_1+c_2 \\ 0 & 0 & 1 \end{pmatrix},$$

which can easily be written in bitwise operations.

Answer 3

Wolfram Language (Mathematica), 51 bytes

⌊#/4^IntegerDigits[#2,4,4]⌋~Mod~4~FromDigits~4&

Try it online!

Using labels {228, 57, 78, 147, 27, 177, 198, 108}.

These are {3210, 0321, 1032, 2103, 0123, 2301, 3012, 1230} in base 4. Fortunately, 256=4^4.

---

Lower-level implementation, also 51 bytes

Sum[4^i⌊#/4^⌊#2/4^i⌋~Mod~4⌋~Mod~4,{i,0,3}]&

Try it online!

Answer 4

Python 2, 22 bytes

A port of my Mathematica answer. Using integers \$0, 6, 1, 7, 2, 3, 5, 4\$ as labels.

lambda a,b:a^b^a/2&b/4

Try it online!

Answer 5

Python 2, 26 23 21 bytes

lambda x,y:y+x*7**y&7

Try it online! Port of my answer to Cayley Table of the Dihedral Group \$D_3\$. Edit: Saved 3 bytes thanks to @NieDzejkob. Saved 2 bytes thanks to @xnor for suggesting the and (rather than xnor) operator. Uses the following mapping:

 id | r1 | r2 | r3 | s0 | s1 | s2 | s3 
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7  

Answer 6

TI-BASIC, 165 bytes

Ans→L₁:{.12345678,.23417865,.34126587,.41238756,.58671342,.67583124,.75862413,.86754231→L₂:For(I,1,8:10fPart(.1int(L₂(I)₁₀^(seq(X,X,1,8:List▶matr(Ans,[B]:If I=1:[B]→[A]:If I-1:augment([A],[B]→[A]:End:[A](L₁(1),L₁(2

Input is a list of length two in Ans.
Output is the number at the (row, column) index in the table.

There could be a better compression method which would save bytes, but I'll have to look into that.

Examples:

{1,2
           {1 2}
prgmCDGF1B
               2
{7,4
           {7 4}
prgmCDGF1B
               5

Explanation:
(Newlines have been added for readability.)

Ans→L₁                              ;store the input list into L₁
{.123456 ... →L₂                    ;store the compressed matrix into L₂
                                    ; (line shortened for brevity)
For(I,1,8                           ;loop 8 times
10fPart(.1int(L₂(I)₁₀^(seq(X,X,1,8  ;decompress the "I"-th column of the matrix
List▶matr(Ans,[B]                   ;convert the resulting list into a matrix column and
                                    ; then store it into the "[B]" matrix variable
If I=1                              ;if the loop has just started...
[B]→[A]                             ;then store this column into "[A]", another matrix
                                    ; variable
If I-1                              ;otherwise...
augment([A],[B]→[A]                 ;append this column onto "[A]"
End
[A](L₁(1),L₁(2                      ;get the index and keep it in "Ans"
                                    ;implicit print of "Ans"

Here's a 155 byte solution, but it just hardcodes the matrix and gets the index.
I found it to be more boring, so I didn't make it my official submission:

Ans→L₁:[[1,2,3,4,5,6,7,8][2,3,4,1,8,7,5,6][3,4,1,2,6,5,8,7][4,1,2,3,7,8,6,5][5,7,6,8,1,3,2,4][6,8,5,7,3,1,4,2][7,6,8,5,4,2,1,3][8,5,7,6,2,4,3,1:Ans(L₁(1),L₁(2

---

Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

Answer 7

JavaScript (Node.js), 22 17 bytes

(x,y)=>y+x*7**y&7

Try it online! Port of my answer to Cayley Table of the Dihedral Group \$D_3\$ but golfed down using the suggestions on my Python answer. Uses the following mapping:

 id | r1 | r2 | r3 | s0 | s1 | s2 | s3 
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7  

Older versions of JavaScript can be supported in a number of ways for 22 bytes:

(x,y)=>(y&1?y-x:y+x)&7
(x,y)=>y-x*(y&1||-1)&7
(x,y)=>y+x*(y<<31|1)&7

Answer 8

Jelly, 6 bytes

N⁹¡+%8

A dyadic Link accepting the first transform on the right and the second transform on the left which yields the composite transform.

Where the transforms are:

as in question:  1    2    3    4    5    6    7    8
transformation: id  90a  180  90c  hor  ver  +ve  -ve
  code's label:  0    2    4    6    1    5    7    3

Try it online! ...Or see the table mapped back onto the labels in the question.

(The arguments could be taken in the other order using the 6 byter, _+Ḃ?%8)

How?

Each label is the length of a sequence of alternating hor and +ve transforms which is equivalent to the transform (e.g. 180 is equivalent to hor, +ve, hor, +ve).

The composition A,B is equivalent to the concatenation of the two equivalent sequences, and allows simplification to subtraction or addition modulo eight...

Using the question's 7, 4 example we have +ve, 90c which is:
hor, +ve, hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve, hor, +ve

...but since hor, hor is id we have:
hor, +ve, hor, +ve, hor, +ve , +ve, hor, +ve, hor, +ve

...and since +ve, +ve is id we have:
hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve

...and we can repeat these cancellations to:
hor
..equivalent to subtraction of the lengths (7-6=1).

When no cancellations are possible we are just adding the lengths (like 90a, 180 \$\rightarrow\$ 2+4=6 \$\rightarrow\$ 90c).

Lastly, note that a sequence of length eight is id so we can take the resulting sequence length modulo eight.

N⁹¡+%8 - Link: B, A
  ¡    - repeat (applied to chain's left argument, B)...
 ⁹     - ...times: chain's right argument, A
N      - ...action: negate  ...i.e. B if A is even, otherwise -B
   +   - add (A)
    %8 - modulo eight

---

It's also 1 byte shorter than this implementation using lexicographical permutation indexes:

œ?@ƒ4Œ¿

...a monadic Link accepting [first, second], with labels:

as in question:  1    2    3    4    5    6    7    8
transformation: id  90a  180  90c  hor  ver  +ve  -ve
  code's label:  1   10   17   19   24    8   15    6

Answer 9

Rust, 16 bytes

|a,b|a^b^a/2&b/4

Try it online!

Port of alephalpha's Python answer. But shorter.

Answer 10

Elm, 42 bytes 19 bytes

\a b->and 7<|b+a*7^b

Port of the Neil's Node.js version

Try it online

Previous version:

\a b->and 7<|if and 1 a>0 then a-b else a+b

Answer 11

Python, 82 71 bytes

0-7

-11 bytes thanks to ASCII-only

lambda a,b:int("27pwpxvfcobhkyqu1wrun3nu1fih0x8svriq0",36)>>3*(a*8+b)&7

TIO

Answer 12

C# (Visual C# Interactive Compiler), 17 bytes

a=>b=>a^b^a/2&b/4

Port of alpehalpha's Python answer.

Try it online!

Answer 13

Scala, 161 bytes

Choosing COMPUTER as labels.

val m="0123456712307645230154763012675446570213574620316574310274651320"
val s="COMPUTER"
val l=s.zipWithIndex.toMap
def f(a: Char, b: Char)=s(m(l(a)*8+l(b))-48)

Try it online!

Answer 14

Scala, 70 bytes

Choosing 0-7 native integers as labels.

Compressed the matrix into 32 byte ASCII string, each pair of numbers n0, n1 into 1 character c = n0 + 8*n1 + 49. Starting from 49 to that we don't have \ in the encoded string.

(a:Int,b:Int)=>"9K]oB4h]K9Vh4BoVenAJne3<_X<AX_J3"(a*4+b/2)-49>>b%2*3&7

Try it online!

Answer 15

Perl 6, 19 bytes

{($^x*7**$^y+$y)%8}

Port of Neil's Python solution.

Try it online!

Answer 16

Wolfram Language (Mathematica), 7 bytes (UTF-8 encoding)

#⊙#2&

A pure function taking two arguments. The symbol rendered here as ⊙ is actually Mathematica's private Unicode symbol F3DE (3 bytes), which represents the function PermutationProduct.

Mathematica knows about dihedral groups, and it represents the elements of various groups as permutations, written using the Cycles command. For example, running the command

GroupElements[DihedralGroup[4]]

yields the output:

{Cycles[{}], Cycles[{{2, 4}}], Cycles[{{1, 2}, {3, 4}}], 
 Cycles[{{1, 2, 3, 4}}], Cycles[{{1, 3}}], Cycles[{{1, 3}, {2, 4}}], 
 Cycles[{{1, 4, 3, 2}}], Cycles[{{1, 4}, {2, 3}}]}

PermutationProduct is the function that multiplies group elements when written in this form.

Since we are allowed to choose our own labels, this function assumes these labels for the group elements; the assocation between these labels and the ones in the problem post is given by:

Cycles[{}] -> 1
Cycles[{{1, 2, 3, 4}}] -> 2
Cycles[{{1, 3}, {2, 4}}] -> 3
Cycles[{{1, 4, 3, 2}}] -> 4
Cycles[{{2, 4}}] -> 5
Cycles[{{1, 3}}] -> 6
Cycles[{{1, 2}, {3, 4}}] -> 7
Cycles[{{1, 4}, {2, 3}}] -> 8

tl;dr There's a builtin.