Composición diédrica del grupo D4 con etiquetas personalizadas

14

El grupo diédrico D4 es el grupo de simetría del cuadrado, es decir, los movimientos que transforman un cuadrado a sí mismo a través de rotaciones y reflexiones. Consta de 8 elementos: rotaciones de 0, 90, 180 y 270 grados, y reflexiones a través de los ejes horizontal, vertical y dos diagonales.

Los 8 elementos de D4 actúan sobre el cuadrado.

Las imágenes son todas de esta hermosa página de Larry Riddle.

Este desafío se trata de componer estos movimientos: dados dos movimientos, genera el movimiento que es equivalente a hacerlos uno tras otro. Por ejemplo, hacer el movimiento 7 seguido del movimiento 4 es lo mismo que hacer el movimiento 5.

Ejemplo de composición

Tenga en cuenta que cambiar el orden para mover 4 y luego mover 7 produce el movimiento 6 en su lugar.

Los resultados se tabulan a continuación; Esta es la tabla de Cayley del grupo D4 . Entonces, por ejemplo, las entradas 7,4 4 deberían producir la salida 5 .

12345678123456781234567823418756341265874123786557681324685731427685421385762431

Desafío

Su objetivo es implementar esta operación en la menor cantidad de bytes posible, pero además del código, también elige las etiquetas que representan los movimientos del 1 al 8. Las etiquetas deben ser 8 números distintos del 0 al 255 , o el 8 -byte caracteres que representan sus puntos de código.

Su código recibirá dos de las etiquetas de las 8 que ha elegido, y debe mostrar la etiqueta que corresponde a su composición en el grupo diédrico D4 .

Ejemplo

Supongamos que ha elegido los caracteres C, O, M, P, U, T, E, R para los movimientos 1 a 8 respectivamente. Entonces, su código debe implementar esta tabla.

COMPUTERCOMPUTERCOMPUTEROMPCREUTMPCOTUREPCOMERTUUETRCMOPTRUEMCPOETRUPOCMRUETOPMC

Dadas las entradas E y P, debe generar U. Sus entradas siempre serán dos de las letras C, O, M, P, U, T, E, R, y su salida siempre será una de estas letras.

Tabla de texto para copiar

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
xnor
fuente
Your choice of labels doesn't count against your code length.mente elaborando? Tal como está, puedo codificar la matriz en mi código y afirmar que no cuenta para mi puntaje.
Benjamin Urquhart
2
@BenjaminUrquhart Estaba tratando de decir que la longitud de su código es solo la longitud de su código, y decir, elegir etiquetas multidígitos no cuesta nada extra. Parece que esa línea es más confusa que útil, así que la eliminaré.
xnor

Respuestas:

10

Ruby , 18 bytes

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

Sin golf

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

Pruébalo en línea!

Utiliza los siguientes números de codificación del 0 al 7

En orden nativo al código:

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

En orden por la pregunta

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

Explicación

/representa un giro en la línea y=xy| un giro en el eje y.

Es posible generar cualquiera de las simetrías del grupo D4 volteando alternativamente estas dos líneas. Por ejemplo, /seguido de |dado/| que es una rotación de 90 grados en sentido antihorario.

El número total de vueltas consecutivas proporciona una representación muy conveniente para la manipulación aritmética.

Si el primer movimiento es una rotación, simplemente podemos agregar el número de vueltas:

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

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

Si el primer movimiento es un reflejo, descubrimos que tenemos algunos reflejos /y |símbolos idénticos uno al lado del otro. Como la reflexión es inversa, podemos cancelar estos cambios uno por uno. Entonces necesitamos restar un movimiento del otro

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 ) / 
Level River St
fuente
1
Puede reemplazar el ~0con 7debido a la aritmética modular.
NieDzejkob
Gran método y explicación! La forma en que se cancelan los flips deja muy claro por qué las etiquetas suman o restan.
xnor
7

Wolfram Language (Mathematica) , 31 bytes

Usando enteros 0,5,2,7,1,3,6,4 como etiquetas.

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

Pruébalo en línea!

Explicación:

El grupo Diedro D4 es isomorfo al grupo matriz triangular unitario de grado tres sobre el campo F2 :

D4U(3,2):={(1ab01c001)a,b,cF2}.

Y tenemos

(1a1b101c1001)(1a2b201c2001)=(1a1+a2b1+b2+a1c201c1+c2001),

que se puede escribir fácilmente en operaciones bit a bit.

alephalpha
fuente
Una bonita derivación: no sabía sobre este isomorfismo.
xnor
5

Wolfram Language (Mathematica) , 51 bytes

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

Pruébalo en línea!

Usando etiquetas {228, 57, 78, 147, 27, 177, 198, 108} .

Estos están {3210, 0321, 1032, 2103, 0123, 2301, 3012, 1230}en la base 4. Afortunadamente, 256 = 4 ^ 4.


Implementación de nivel inferior, también 51 bytes

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

Pruébalo en línea!

attinat
fuente
4

Python 2 , 26 23 21 bytes

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

re3andxnor

 id | r1 | r2 | r3 | s0 | s1 | s2 | s3 
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7  
Neil
fuente
2
Puede reemplazar (-1)con 7debido a la aritmética modular para -3 bytes.
NieDzejkob
@NieDzejkob ¡Gracias! Es una pena que alephalpha haya bajado su respuesta de 28 a 22 bytes ...
Neil
Buena solución! Puede cortar los parens cambiando la precedencia del operador:y+x*7**y&7
xnor
@xnor Gracias, estoy por delante de alephalpha otra vez!
Neil
3

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

La entrada es una lista de longitud dos en Ans.
La salida es el número en el (row, column)índice de la tabla.

Podría haber un mejor método de compresión que ahorraría bytes, pero tendré que investigarlo.

Ejemplos:

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

Explicación:
(Se han agregado nuevas líneas para facilitar la lectura).

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"

Aquí hay una solución de 155 bytes , pero solo codifica la matriz y obtiene el índice.
Lo encontré más aburrido, así que no lo hice mi presentación oficial:

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

Nota: TI-BASIC es un lenguaje tokenizado. El recuento de caracteres hace es igual al recuento de bytes.

Tau
fuente
¿No podría afeitarse como un byte mediante el uso 0-7de1-8
ASCII de sólo
Podría, pero luego tendría que usar dos más para agregar uno a cada uno de los elementos de la matriz. Buen pensamiento, sin embargo!
Tau
mal, puedes usar cualquier conjunto de caracteres jajaja, así que no tienes que usar dos más
solo ASCII
eso puede ser cierto, pero las matrices de TI-BASIC están indexadas en 1. esta presentación se basa en eso para obtener el valor deseado (si eso es lo que estás insinuando. corrígeme si me equivoco)
Tau
ah, se olvidó de eso
solo ASCII
3

Jalea , 6 bytes

N⁹¡+%8

Un enlace diádico que acepta la primera transformación a la derecha y la segunda transformación a la izquierda que produce la transformación compuesta.

Donde están las transformaciones:

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

Pruébalo en línea! ... O vea la tabla asignada de nuevo a las etiquetas en la pregunta .

(Los argumentos podrían tomarse en el otro orden usando el byte 6 _+Ḃ?%8)

¿Cómo?

Cada etiqueta es la longitud de una secuencia de alternancia hory +vetransformaciones que es equivalente a la transformación (por ejemplo, 180es equivalente a hor, +ve, hor, +ve).

La composición A,Bes equivalente a la concatenación de las dos secuencias equivalentes, y permite la simplificación de la resta o la suma del módulo ocho ...

Usando el 7, 4ejemplo de la pregunta tenemos +ve, 90ccuál es:
hor, +ve, hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve, hor, +ve

... pero ya hor, hores idque tenemos:
hor, +ve, hor, +ve, hor, +ve , +ve, hor, +ve, hor, +ve

... y como +ve, +vees idque tenemos:
hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve

... y podemos repetir estas cancelaciones para:
hor
..equivalente a la resta de las longitudes (7-6=1 ).

Cuando no hay cancelaciones posibles, solo estamos agregando las longitudes (como 90a, 180 2+4=6 90c)

Por último, tenga en cuenta que una secuencia de longitud ocho es idpara que podamos tomar la secuencia de longitud resultante módulo ocho.

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

También es 1 byte más corto que esta implementación usando índices de permutación lexicográficos:

œ?@ƒ4Œ¿

... un enlace monádico que acepta [first, second], con etiquetas:

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
Jonathan Allan
fuente
3

JavaScript (Node.js) , 22 17 bytes

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

Pruébalo en línea! Puerto de mi respuesta a Cayley Table of the Dihedral Groupre3pero jugué con las sugerencias de mi respuesta de Python. Utiliza el siguiente mapeo:

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

Las versiones anteriores de JavaScript se pueden admitir de varias maneras para 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
Neil
fuente
Pequeña mejora: guarde un byte al curry de entrada y x=>y=>(y&1?y-x:y+x)&7luego llame a su función usando f(x)(y).
dana
2

Olmo , 42 bytes 19 bytes

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

Puerto de los Neil's Versión Node.js

Pruébalo en línea

Versión previa:

\a b->and 7<|if and 1 a>0 then a-b else a+b
Evgeniy Malyutin
fuente
1
Buena primera respuesta! No sé cómo programar en Elm, pero ¿es posible eliminar espacios?
MilkyWay90
@ MilkyWay90 no, es una de las principales diferencias de los lenguajes basados ​​en ML que f xes una llamada de función, al igual que lo que f(x)significa en lenguajes tipo C. Y no puedes evitarlo. Pero puede ser realmente agradable y menos abarrotado en muchos escenarios que no son de golf. Elm no tiene operadores bit a bit (como &), por lo que and x yes solo una llamada de función simple aquí.
Evgeniy Malyutin
Ya veo, gracias por explicar!
MilkyWay90
@ MilkyWay90 en realidad, logré cortar un espacio (y un byte) usando un operador de tubería en <|lugar de paréntesis. Gracias por cuestionar eso!
Evgeniy Malyutin
¡De nada! Si está interesado en hacer una nueva solución, puede pedir ayuda en The Nineteenth Byte (nuestra sala de chat SE). Si está creando un desafío de codificación, puede publicarlo en The Sandbox (en meta) y publicar el enlace a la pregunta en The Nineteenth Byte todos los días.
MilkyWay90
1

Python, 82 71 bytes

0-7

-11 bytes gracias a ASCII de sólo

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

TIO

Benjamin Urquhart
fuente
80, python 2 , 76, python 2
solo ASCII
también 76 , y -2 porque f=se puede eliminar ya que no es recursivo
solo ASCII del
espere rasgadura, no funciona
solo ASCII
2
aquí vamos, 71
solo ASCII
parece que podría hacerlo mejor con int.from_bytesuna codificación que no sea UTF, pero ... no estoy seguro de cómo hacerlo en TIO
solo ASCII
0

Scala , 161 bytes

Elegir ORDENADOR como etiquetas.

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)

Pruébalo en línea!

Peter
fuente
1
este es el código de golf: | se supone que debes hacerlo lo más corto posible
solo ASCII
88
Solo ASCII
Sí, me desafié a mí misma con scala y etiquetas reales, no solo nativas 0-7. Intenta vencerlo.
Peter
133
Solo ASCII
118: P
Solo ASCII del
0

Scala , 70 bytes

Elegir 0-7 enteros nativos como etiquetas.

Comprimió la matriz en una cadena ASCII de 32 bytes, cada par de números n0, n1 en 1 carácter c = n0 + 8 * n1 + 49. Comenzando desde 49 hasta que no tenemos \ en la cadena codificada.

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

Pruébalo en línea!

Peter
fuente
-3

Wolfram Language (Mathematica), 7 bytes (codificación UTF-8)

#⊙#2&

Una función pura que toma dos argumentos. El símbolo representado aquí como en realidad es el símbolo privado Unicode de Mathematica F3DE (3 bytes), que representa la funciónPermutationProduct .

Mathematica sabe sobre grupos diédricos, y representa los elementos de varios grupos como permutaciones, escritos usando el Cyclescomando. Por ejemplo, ejecutando el comando

GroupElements[DihedralGroup[4]]

produce la salida:

{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 es la función que multiplica los elementos del grupo cuando se escribe de esta forma.

Como se nos permite elegir nuestras propias etiquetas, esta función asume estas etiquetas para los elementos del grupo; La asociación entre estas etiquetas y las de la publicación del problema viene dada por:

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 Hay un incorporado.

Greg Martin
fuente
8
Las etiquetas deben ser números del 0 al 255 o bytes individuales.
xnor
Bastante justo (estoy feliz de haber descubierto esta función independientemente). ¿Puedes aclarar eso en el OP? En este momento se lee como "elige tus propias etiquetas" (enfatizado), luego un par de opciones posibles ("puedes ...").
Greg Martin
1
Oh, ya veo cómo lo estás leyendo; perdón por no estar claro aquí y llevarte por el camino equivocado. Déjame intentar reformularlo.
xnor