Komposisi D4 grup dihedral dengan label khusus

14

Kelompok dihedral D4 adalah kelompok simetri dari alun-alun, yang bergerak yang mengubah persegi untuk dirinya sendiri melalui rotasi dan refleksi. Ini terdiri dari 8 elemen: rotasi dengan 0, 90, 180, dan 270 derajat, dan refleksi melintasi sumbu horizontal, vertikal, dan dua diagonal.

8 elemen D4 yang bekerja di alun-alun.

Gambar-gambar tersebut semuanya berasal dari halaman indah oleh Larry Riddle.

Tantangan ini adalah tentang menyusun gerakan ini: diberi dua gerakan, mengeluarkan gerakan yang setara dengan melakukannya satu per satu. Misalnya, melakukan langkah 7 diikuti dengan langkah 4 sama dengan melakukan langkah 5.

Contoh komposisi

Perhatikan bahwa beralih urutan untuk bergerak 4 lalu bergerak 7 menghasilkan langkah 6 sebagai gantinya.

Hasilnya ditabulasikan di bawah ini; ini adalah tabel Cayley dari grup D4 . Jadi misalnya, input 7,4 harus menghasilkan output 5 .

12345678123456781234567823418756341265874123786557681324685731427685421385762431

Tantangan

Tujuan Anda adalah untuk mengimplementasikan operasi ini sesedikit mungkin byte, tetapi selain kode, Anda juga memilih label yang mewakili gerakan 1 hingga 8. Label harus terdiri dari 8 angka berbeda dari 0 hingga 255 , atau 8 karakter -byte mewakili titik kode mereka.

Kode Anda akan diberikan dua label dari 8 yang Anda pilih, dan harus menampilkan label yang sesuai dengan komposisi mereka di grup dihedral D4 .

Contoh

Katakanlah Anda telah memilih karakter C, O, M, P, U, T, E, R untuk masing-masing bergerak 1 hingga 8. Kemudian, kode Anda harus mengimplementasikan tabel ini.

COMPUTERCOMPUTERCOMPUTEROMPCREUTMPCOTUREPCOMERTUUETRCMOPTRUEMCPOETRUPOCMRUETOPMC

Diberikan input E dan P, Anda harus menampilkan U. Input Anda akan selalu dua huruf C, O, M, P, U, T, E, R, dan output Anda harus selalu salah satu dari huruf-huruf ini.

Tabel teks untuk disalin

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
Tidak
sumber
Your choice of labels doesn't count against your code length.keberatan menguraikan? Seperti berdiri, saya dapat mengubah kode matriks ke dalam kode saya dan mengklaim itu tidak dihitung terhadap skor saya.
Benjamin Urquhart
2
@BenjaminUrquhart Saya mencoba mengatakan bahwa panjang kode Anda hanya panjang kode Anda, dan berkata, memilih label multidigit tidak memerlukan biaya tambahan. Sepertinya kalimat itu lebih membingungkan dan membantu, jadi saya akan menghapusnya.
xnor

Jawaban:

10

Ruby , 18 byte

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

Tidak disatukan

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

Cobalah online!

Gunakan nomor kode berikut 0 hingga 7

Agar asli ke kode:

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

Agar per pertanyaan

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

Penjelasan

/mewakili flip di garis y=xdan |mewakili flip di sumbu y.

Dimungkinkan untuk menghasilkan salah satu simetri dari grup D4 dengan membalik secara bergantian dalam dua garis ini. Misalnya /diikuti dengan |memberi /|yang merupakan rotasi 90 derajat berlawanan arah jarum jam.

Jumlah total flips berturut-turut memberikan representasi yang sangat nyaman untuk manipulasi aritmatika.

Jika langkah pertama adalah rotasi, kita cukup menambahkan jumlah flips:

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

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

Jika langkah pertama adalah refleksi, kami menemukan kami memiliki beberapa refleksi /dan |simbol yang identik di sebelah satu sama lain. Karena refleksi adalah terbalik sendiri, kita dapat membatalkan membalik ini satu per satu. Jadi kita perlu mengurangi satu gerakan dari yang lain

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
sumber
1
Anda dapat mengganti ~0dengan 7karena aritmatika modular.
NieDzejkob
Metode dan penjelasan yang bagus! Cara membalik dibatalkan membuat sangat jelas mengapa label menambah atau mengurangi.
xnor
7

Bahasa Wolfram (Mathematica) , 31 byte

Menggunakan bilangan bulat 0,5,2,7,1,3,6,4 sebagai label.

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

Cobalah online!

Penjelasan:

The Dihedral Kelompok D4 isomorfis ke kelompok matriks unitriangular derajat tiga di atas lapangan F2 :

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

Dan kita mempunyai

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

yang dapat dengan mudah ditulis dalam operasi bitwise.

alephalpha
sumber
Derivasi yang cantik - saya belum tahu tentang isomorfisme ini.
xnor
5

Bahasa Wolfram (Mathematica) , 51 byte

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

Cobalah online!

Menggunakan label {228, 57, 78, 147, 27, 177, 198, 108}.

Ini ada {3210, 0321, 1032, 2103, 0123, 2301, 3012, 1230}di basis 4. Untungnya, 256 = 4 ^ 4.


Implementasi tingkat bawah, juga 51 byte

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

Cobalah online!

attinat
sumber
4

Python 2 , 26 23 21 byte

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

Cobalah online! Port jawaban saya untuk Cayley Table dari Grup Dihedral D3 . Sunting: Disimpan 3 byte berkat @NieDzejkob. Disimpan 2 byte berkat @xnor untuk menyarankan operator and(bukan xnor). Gunakan pemetaan berikut:

 id | r1 | r2 | r3 | s0 | s1 | s2 | s3 
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7  
Neil
sumber
2
Anda dapat mengganti (-1)dengan 7karena aritmatika modular untuk -3 byte.
NieDzejkob
@NieDzejkob Terima kasih! Malu alfalpha itu menurunkan jawabannya dari 28 menjadi 22 byte ...
Neil
Solusi bagus! Anda dapat memotong parens dengan mengubah prioritas operator:y+x*7**y&7
xnor
@ xnor Terima kasih, saya di depan alephalpha lagi!
Neil
3

TI-BASIC, 165 byte

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 adalah daftar panjang dua in Ans .
Output adalah angka pada (row, column)indeks dalam tabel.

Mungkin ada metode kompresi yang lebih baik yang akan menghemat byte, tetapi saya harus memeriksanya.

Contoh:

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

Penjelasan:
(Baris baru telah ditambahkan untuk dibaca.)

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"

Berikut ini adalah solusi 155 byte , tetapi hanya hardcodes matriks dan mendapat indeks.
Saya merasa ini lebih membosankan, jadi saya tidak membuatnya sebagai pengajuan resmi:

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

Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.

Tau
sumber
Tidak bisa Anda mencukur seperti salah satu byte dengan menggunakan 0-7ke1-8
ASCII-satunya
Saya bisa, tetapi kemudian saya harus menggunakan dua lagi untuk menambahkan satu ke masing-masing elemen matriks. Namun, pemikiran yang bagus!
Tau
salah, Anda dapat menggunakan sekumpulan karakter lol, jadi Anda tidak harus menggunakan dua karakter lagi
ASCII-only
itu mungkin benar, tetapi matriks TI-BASIC adalah 1-diindeks. pengajuan ini bergantung pada hal itu untuk mendapatkan nilai yang diinginkan (jika itu yang Anda maksudkan. koreksi saya jika saya salah)
Tau
ah, lupa tentang itu
ASCII-hanya
3

Jelly , 6 byte

N⁹¡+%8

Tautan diad menerima transformasi pertama di kanan dan transformasi kedua di sebelah kiri yang menghasilkan transformasi komposit.

Di mana transformasi adalah:

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

Cobalah online! ... Atau lihat tabel dipetakan kembali ke label pada pertanyaan .

(Argumen dapat diambil dalam urutan lain menggunakan 6 byter, _+Ḃ?%8)

Bagaimana?

Setiap label adalah panjang urutan bolak-balik hordan +vetransformasi yang setara dengan transformasi (misalnya 180setara dengan hor, +ve, hor, +ve).

Komposisi A,Bini setara dengan gabungan dari dua sekuens yang setara, dan memungkinkan penyederhanaan untuk pengurangan atau penambahan modulo delapan ...

Menggunakan contoh pertanyaan yang 7, 4kami miliki +ve, 90cyaitu:
hor, +ve, hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve, hor, +ve

... tapi karena hor, horini idkita memiliki:
hor, +ve, hor, +ve, hor, +ve , +ve, hor, +ve, hor, +ve

... dan karena +ve, +veitu idkita punya:
hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve

... dan kami dapat mengulangi pembatalan ini ke:
hor
..setara dengan pengurangan panjang ( 7-6=1).

Ketika tidak ada pembatalan mungkin kami hanya menambahkan panjangnya (seperti 90a, 180 2+4=6 90c).

Terakhir, perhatikan bahwa urutan panjang delapan adalah idsehingga kita dapat mengambil panjang urutan yang dihasilkan modulo delapan.

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

Ini juga 1 byte lebih pendek dari implementasi ini menggunakan indeks permutasi leksikografis:

œ?@ƒ4Œ¿

... Tautan monadik yang menerima [first, second], dengan label:

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
sumber
3

JavaScript (Node.js) , 22 17 byte

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

Cobalah online! Port jawaban saya untuk Cayley Table dari Grup DihedralD3tapi menggunakan saran pada jawaban Python saya. Gunakan pemetaan berikut:

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

Versi JavaScript yang lebih lama dapat didukung dalam beberapa cara selama 22 byte:

(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
sumber
Perbaikan kecil - simpan satu byte dengan mengecek input x=>y=>(y&1?y-x:y+x)&7lalu panggil fungsi Anda menggunakan f(x)(y).
dana
2

Elm , 42 byte 19 byte

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

Port versi Neode Node.js

Cobalah online

Versi sebelumnya:

\a b->and 7<|if and 1 a>0 then a-b else a+b
Evgeniy Malyutin
sumber
1
Jawaban pertama yang bagus! Saya tidak tahu cara memprogram di Elm, tetapi apakah mungkin untuk menghapus spasi?
MilkyWay90
@ MilkyWay90 nggak, itu salah satu perbedaan utama bahasa berbasis ML yang f xmerupakan pemanggilan fungsi, sama seperti apa f(x)artinya dalam bahasa mirip-C. Dan Anda tidak dapat menahannya. Tapi itu bisa sangat bagus dan kurang berantakan di banyak skenario non-golf. Elm tidak memiliki operator bitwise (seperti &) sehingga and x yhanya fungsi panggilan biasa di sini.
Evgeniy Malyutin
Begitu ya, terima kasih sudah menjelaskan!
MilkyWay90
@ MilkyWay90 sebenarnya, saya berhasil memotong satu ruang (dan satu byte) menggunakan operator pipa <|daripada tanda kurung. Terima kasih telah mempertanyakan itu!
Evgeniy Malyutin
Sama-sama! Jika Anda tertarik untuk membuat solusi baru, Anda dapat meminta bantuan The Nineteenth Byte (ruang obrolan SE kami) untuk meminta bantuan. Jika Anda membuat tantangan pengkodean, Anda dapat mempostingnya ke The Sandbox (di meta) dan memposting tautan ke pertanyaan di The Nineteenth Byte setiap hari.
MilkyWay90
1

Python, 82 71 byte

0-7

-11 byte berkat ASCII saja

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

TIO

Benjamin Urquhart
sumber
80, python 2 , 76, python 2
ASCII-hanya
juga 76 , dan -2 karena f=dapat dihapus karena tidak rekursif
ASCII-hanya
tunggu rip, itu tidak berhasil
ASCII-hanya
2
ini dia, 71
ASCII saja
sepertinya Anda bisa melakukan yang lebih baik dengan int.from_bytesdan penyandian non-UTF, tapi ... tidak yakin bagaimana melakukannya di TIO
ASCII-hanya
0

Scala , 161 byte

Memilih KOMPUTER sebagai label.

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)

Cobalah online!

Peter
sumber
1
ini adalah kode golf: | Anda seharusnya membuatnya sesingkat mungkin
ASCII
88
ASCII-satunya
Ya, saya menantang diri saya untuk menggunakan label scala dan asli, bukan hanya asli 0-7. Cobalah untuk mengalahkannya.
Peter
133
ASCII
118: P
ASCII
0

Scala , 70 byte

Memilih 0-7 bilangan bulat asli sebagai label.

Dikompresi matriks menjadi string ASCII 32 byte, masing-masing pasangan angka n0, n1 menjadi 1 karakter c = n0 + 8 * n1 + 49. Mulai dari 49 hingga yang kita tidak miliki \ dalam string yang disandikan.

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

Cobalah online!

Peter
sumber
-3

Bahasa Wolfram (Mathematica), 7 byte (pengodean UTF-8)

#⊙#2&

Fungsi murni mengambil dua argumen. Simbol yang diberikan di sini sebagai adalah simbol Unicode pribadi milik Fatic (3 byte), yang mewakili fungsiPermutationProduct .

Mathematica tahu tentang kelompok dihedral, dan itu mewakili elemen dari berbagai kelompok sebagai permutasi, ditulis menggunakan Cyclesperintah. Misalnya, menjalankan perintah

GroupElements[DihedralGroup[4]]

menghasilkan 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 adalah fungsi yang mengalikan elemen grup ketika ditulis dalam formulir ini.

Karena kami diizinkan memilih label kami sendiri, fungsi ini mengasumsikan label ini untuk elemen grup; hubungan antara label-label ini dan label-label di pos masalah diberikan oleh:

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 Ada bawaan.

Greg Martin
sumber
8
Label harus berupa angka 0 hingga 255 atau satu byte.
xnor
Cukup adil (saya senang telah menemukan fungsi ini terlepas). Bisakah Anda menjelaskannya di OP? Saat ini berbunyi seperti "pilih label Anda sendiri" (ditekankan), kemudian beberapa pilihan yang mungkin ("Anda mungkin ...").
Greg Martin
1
Oh, saya mengerti bagaimana Anda membacanya; maaf karena tidak jelas di sini dan membawa Anda ke jalan yang salah. Biarkan saya mencoba untuk reword.
xnor