14
\$\begingroup\$

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 8 elements of D4 acting on the square.

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.

Composition example

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
\$\endgroup\$
  • \$\begingroup\$ Your choice of labels doesn't count against your code length. mind elaborating? As it stands, I can hardcode the matrix into my code and claim it doesn't count against my score. \$\endgroup\$ – Benjamin Urquhart May 4 at 2:04
  • 2
    \$\begingroup\$ @BenjaminUrquhart I was trying to say the length of your code is just the length of your code, and say, choosing multidigit labels doesn't cost anything extra. Looks like that line is more confusing that helpful, so I'll remove it. \$\endgroup\$ – xnor May 4 at 2:06

16 Answers 16

10
\$\begingroup\$

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 ) / 
\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace the ~0 with 7 because of modular arithmetic. \$\endgroup\$ – NieDzejkob May 4 at 17:41
  • \$\begingroup\$ Great method and explanation! The way the flips cancel makes it really clear why the labels either add or subtract. \$\endgroup\$ – xnor May 9 at 0:17
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ A pretty derivation -- I had not known about this isomorphism. \$\endgroup\$ – xnor May 9 at 0:16
5
\$\begingroup\$

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!

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

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!

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

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  
\$\endgroup\$
  • 2
    \$\begingroup\$ You can replace (-1) with 7 because of modular arithmetic for -3 bytes. \$\endgroup\$ – NieDzejkob May 4 at 14:09
  • \$\begingroup\$ @NieDzejkob Thanks! Shame that alephalpha golfed his answer down from 28 to 22 bytes though... \$\endgroup\$ – Neil May 4 at 16:50
  • \$\begingroup\$ Nice solution! You can cut the parens by changing the operator precedence: y+x*7**y&7 \$\endgroup\$ – xnor May 9 at 0:15
  • \$\begingroup\$ @xnor Thanks, I'm ahead of alephalpha again! \$\endgroup\$ – Neil May 9 at 8:48
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Couldn't you shave like one byte by using 0-7 to 1-8 \$\endgroup\$ – ASCII-only May 4 at 5:03
  • \$\begingroup\$ I could, but then I'd have to use two more to add one to each of the matrix's elements. Good thought, however! \$\endgroup\$ – Tau May 4 at 16:38
  • \$\begingroup\$ wrong, you can use any set of characters lol, so you don't havev to use two more \$\endgroup\$ – ASCII-only May 5 at 2:44
  • \$\begingroup\$ that may be true, but TI-BASIC's matrices are 1-indexed. this submission relies on that to get the wanted value (if that's what you're implying. correct me if i'm wrong) \$\endgroup\$ – Tau May 5 at 3:32
  • \$\begingroup\$ ah, forgot about that \$\endgroup\$ – ASCII-only May 5 at 3:46
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Small improvement - save a byte by currying input x=>y=>(y&1?y-x:y+x)&7 then call your function using f(x)(y). \$\endgroup\$ – dana May 5 at 12:19
2
\$\begingroup\$

Rust, 16 bytes

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

Try it online!

Port of alephalpha's Python answer. But shorter.

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

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice first answer! I don't know how to program in Elm, but is it possible to remove spaces? \$\endgroup\$ – MilkyWay90 May 6 at 1:17
  • \$\begingroup\$ @MilkyWay90 nope, it's one of the main differences of ML-based languages that f x is a function call, just like what f(x) means in C-like languages. And you can't help it. But it can be really nice and less cluttered in many non-golf scenarios. Elm doesn't have bitwise operators (like &) so and x y is just a plain function call here. \$\endgroup\$ – Evgeniy Malyutin May 6 at 7:28
  • \$\begingroup\$ I see, thanks for explaining! \$\endgroup\$ – MilkyWay90 May 6 at 11:24
  • \$\begingroup\$ @MilkyWay90 actually, I managed to cut off one space (and a byte) using pipe operator <| instead of parenthesis. Thanks for questioning that! \$\endgroup\$ – Evgeniy Malyutin May 8 at 19:17
  • \$\begingroup\$ You're welcome! If you are interested in making a new solution, you could ask over on The Nineteenth Byte (our SE chatroom) for help. If you are creating a coding challenge, you could post it to The Sandbox (on meta) and post the link to the question on The Nineteenth Byte every day. \$\endgroup\$ – MilkyWay90 May 8 at 23:56
1
\$\begingroup\$

Python, 82 71 bytes

0-7

-11 bytes thanks to ASCII-only

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

TIO

\$\endgroup\$
  • \$\begingroup\$ 80, python 2, 76, python 2 \$\endgroup\$ – ASCII-only May 4 at 3:10
  • \$\begingroup\$ also 76, and -2 because f= can be removed since it isn't recursive \$\endgroup\$ – ASCII-only May 4 at 3:15
  • \$\begingroup\$ wait rip, it doesn't work \$\endgroup\$ – ASCII-only May 4 at 3:29
  • 2
    \$\begingroup\$ here we go, 71 \$\endgroup\$ – ASCII-only May 4 at 3:31
  • \$\begingroup\$ seems like you could do better with int.from_bytes and non-UTF encoding, but... not sure how to do that on TIO \$\endgroup\$ – ASCII-only May 4 at 5:05
0
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ this is code golf :| you're supposed to make it as short as possible \$\endgroup\$ – ASCII-only May 4 at 3:31
  • \$\begingroup\$ 88 \$\endgroup\$ – ASCII-only May 4 at 3:34
  • \$\begingroup\$ Yeah, I challenged myself to go with scala and real labels, not just native 0-7. Try to beat it. \$\endgroup\$ – Peter May 4 at 3:41
  • \$\begingroup\$ 133 \$\endgroup\$ – ASCII-only May 4 at 3:43
  • \$\begingroup\$ 118 :P \$\endgroup\$ – ASCII-only May 4 at 3:49
0
\$\begingroup\$

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!

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

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

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

Port of alpehalpha's Python answer.

Try it online!

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

Perl 6, 19 bytes

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

Port of Neil's Python solution.

Try it online!

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

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.

\$\endgroup\$
  • 8
    \$\begingroup\$ The labels have to be numbers 0 to 255 or single bytes. \$\endgroup\$ – xnor May 4 at 8:06
  • \$\begingroup\$ Fair enough (I'm happy to have discovered this function regardless). Can you clarify that in the OP? Right now it reads like "choose your own labels" (emphasized), then a couple of possible choices ("you may..."). \$\endgroup\$ – Greg Martin May 4 at 18:32
  • 1
    \$\begingroup\$ Oh, I see how you're reading it; sorry for being unclear here and leading you down the wrong path. Let me try to reword it. \$\endgroup\$ – xnor May 4 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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