Диэдральная группа D4 композиция с нестандартными метками

14

Диэдральная группа D4 является группой симметрии квадрата, то есть движениями, которые преобразуют квадрат в себя посредством поворотов и отражений. Он состоит из 8 элементов: повороты на 0, 90, 180 и 270 градусов и отражения по горизонтальной, вертикальной и двум диагональным осям.

8 элементов D4, действующих на площади.

Изображения все с этой прекрасной страницы Ларри Риддла.

Задача состоит в том, чтобы составить эти ходы: с учетом двух ходов выведите ход, который эквивалентен выполнению их один за другим. Например, ход 7, за которым следует ход 4, аналогичен ходу 5.

Пример композиции

Обратите внимание, что переключение ордера на ход 4, а затем ход 7 производит вместо этого ход 6.

Результаты приведены в таблице ниже; это таблица Кэли группы D4 . Так, например, входы 7,4 должны давать выход 5 .

12345678123456781234567823418756341265874123786557681324685731427685421385762431

Вызов

Ваша цель состоит в том, чтобы реализовать эту операцию как можно меньшим числом байтов, но в дополнение к коду вы также выбираете метки , представляющие ходы с 1 по 8. Метки должны состоять из 8 различных чисел от 0 до 255. или из 8 -байтовые символы, которые представляют их кодовые точки.

Ваш код получит две метки из 8 выбранных вами, и должен вывести метку, соответствующую их составу, в диэдральной группе D4 .

пример

Допустим, вы выбрали символы C, O, M, P, U, T, E, R для ходов с 1 по 8 соответственно. Затем ваш код должен реализовать эту таблицу.

COMPUTERCOMPUTERCOMPUTEROMPCREUTMPCOTUREPCOMERTUUETRCMOPTRUEMCPOETRUPOCMRUETOPMC

Учитывая входы E и P, вы должны вывести U. В качестве входных данных всегда будут две буквы C, O, M, P, U, T, E, R, а выходные данные всегда должны быть одной из этих букв.

Текстовая таблица для копирования

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
источник
Your choice of labels doesn't count against your code length.возражаете? В настоящее время я могу жестко закодировать матрицу в свой код и утверждать, что она не засчитывается в мой счет.
Бенджамин Уркхарт
2
@BenjaminUrquhart Я пытался сказать, что длина вашего кода - это всего лишь длина вашего кода, и, скажем, выбор многозначных меток ничего не стоит. Похоже, эта строка более запутанная, чем полезная, поэтому я ее уберу.
xnor

Ответы:

10

Рубин , 18 байт

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

Попробуйте онлайн!

Использует следующие номера кодирования от 0 до 7

Для того, чтобы родной код:

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

В порядке по вопросу

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

объяснение

/представляет переворот в линии y=xи |представляет переворот по оси Y.

Можно сгенерировать любую из симметрий группы D4, попеременно переворачивая эти две строки. Например, /после следует |задание, /|которое представляет собой поворот на 90 градусов против часовой стрелки.

Общее количество последовательных переворотов дает очень удобное представление для арифметических манипуляций.

Если первый ход - это вращение, мы можем просто добавить количество сальто:

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

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

Если первый ход - это отражение, мы обнаруживаем, что у нас есть несколько одинаковых отражений /и |символов рядом друг с другом. Поскольку отражение самообращено, мы можем отменить эти броски один за другим. Таким образом, мы должны вычесть одно движение из другого

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 ) / 
Уровень реки St
источник
1
Вы можете заменить ~0с 7из - за модульной арифметики.
NieDzejkob
Отличный метод и объяснение! То, как отменяются сальто, позволяет понять, почему надписи либо складываются, либо вычитаются.
xnor
7

Wolfram Language (Mathematica) , 31 байт

Используя целые числа 0,5,2,7,1,3,6,4 качестве меток.

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

Попробуйте онлайн!

Объяснение:

Диэдральная группа D4 изоморфна унитреугольной матричной группе степени три над полем F2 :

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

И у нас есть

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

который может быть легко записан в побитовых операциях.

alephalpha
источник
Прекрасный вывод - я не знал об этом изоморфизме.
xnor
5

Wolfram Language (Mathematica) , 51 байт

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

Попробуйте онлайн!

Использование ярлыков {228, 57, 78, 147, 27, 177, 198, 108}.

Это {3210, 0321, 1032, 2103, 0123, 2301, 3012, 1230}в базе 4. К счастью, 256 = 4 ^ 4.


Реализация нижнего уровня, также 51 байт

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

Попробуйте онлайн!

attinat
источник
4

Python 2 , 26 23 21 байт

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

D3andxnor

 id | r1 | r2 | r3 | s0 | s1 | s2 | s3 
----+----+----+----+----+----+----+----
 0  | 2  | 4  | 6  | 1  | 3  | 5  | 7  
Нил
источник
2
Вы можете заменить (-1)с 7из - за модульной арифметики для -3 байт.
NieDzejkob
@NieDzejkob Спасибо! Позор, что alephalpha проиграл его ответ с 28 до 22 байтов, хотя ...
Нил
Отличное решение! Вы можете сократить символы, изменив приоритет оператора:y+x*7**y&7
xnor
@xnor Спасибо, я снова впереди алефалии!
Нил
3

TI-BASIC, 165 байт

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

Вход представляет собой список длиной два дюйма Ans.
Выход - число по (row, column)индексу в таблице.

Может быть лучший метод сжатия, который бы экономил байты, но я должен рассмотреть это.

Примеры:

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

Объяснение:
(Новые строки были добавлены для удобства чтения.)

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"

Вот 155-байтовое решение, но оно просто жестко кодирует матрицу и получает индекс.
Я нашел это более скучным, поэтому я не сделал это своим официальным представлением:

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

Примечание: TI-BASIC - это токенизированный язык. Количество символов не равно количеству байтов.

Тау
источник
Не могли бы вы брить , как один байт, используя 0-7для1-8
ASCII-только
Я мог бы, но тогда мне пришлось бы использовать еще два, чтобы добавить один к каждому из элементов матрицы. Хорошая мысль, однако!
Тау
неправильно, вы можете использовать любой набор символов lol, так что вам не придется использовать еще два
только ASCII
это может быть правдой, но матрицы TI-BASIC имеют 1 индекс. это представление опирается на это, чтобы получить требуемое значение (если это то, что вы намекаете. поправьте меня, если я ошибаюсь)
Тау
ах, забыл об этом
только ASCII
3

Желе , 6 байт

N⁹¡+%8

Диадическая ссылка, принимающая первое преобразование справа и второе преобразование слева, что приводит к составному преобразованию.

Где преобразования:

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

Попробуйте онлайн! ... Или посмотрите на таблицу, отображенную обратно на метки в вопросе .

(Аргументы могут быть взяты в другом порядке, используя 6 байтов, _+Ḃ?%8)

Как?

Каждая метка - это длина последовательности чередования horи +veпреобразования, которая эквивалентна преобразованию (например 180, эквивалентна hor, +ve, hor, +ve).

Композиция A,Bэквивалентна объединению двух эквивалентных последовательностей и позволяет упростить вычитание или сложение по модулю восемь ...

Используя 7, 4пример вопроса, который мы имеем +ve, 90c:
hor, +ve, hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve, hor, +ve

... но так hor, horкак idу нас есть:
hor, +ve, hor, +ve, hor, +ve , +ve, hor, +ve, hor, +ve

... и так +ve, +veкак idмы имеем:
hor, +ve, hor, +ve, hor , hor, +ve, hor, +ve

... и мы можем повторить эти отмены, чтобы: ...
hor
эквивалентно вычитанию длины (7-6=1 ).

Когда отмены невозможны, мы просто добавляем длины (например, 90a, 180 2+4=6 90c).

Наконец, обратите внимание, что последовательность длиной восемь такова, idчто мы можем взять результирующую длину последовательности по модулю восемь.

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

Он также на 1 байт короче этой реализации с использованием лексикографических индексов перестановки:

œ?@ƒ4Œ¿

... монадическая ссылка принимает [first, second], с метками:

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
Джонатан Аллан
источник
3

JavaScript (Node.js) , 22 17 байт

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

Попробуйте онлайн! Порт моего ответа на Cayley Table группы DihedralD3но проиграл, используя предложения моего ответа на Python. Использует следующее отображение:

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

Старые версии JavaScript могут поддерживаться различными способами для 22 байтов:

(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
Нил
источник
Небольшое улучшение - сохраните байт, каррируя ввод, x=>y=>(y&1?y-x:y+x)&7затем вызовите вашу функцию, используя f(x)(y).
Dana
2

Вяз , 42 байта 19 байтов

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

Порт Нейла Node.js версия

Попробуйте онлайн

Предыдущая версия:

\a b->and 7<|if and 1 a>0 then a-b else a+b
Евгений Малютин
источник
1
Хороший первый ответ! Я не знаю, как программировать в Elm, но возможно ли убрать пробелы?
MilkyWay90
@ MilkyWay90 Нет, это одно из основных отличий языков на основе ML, которое f xзаключается в вызове функций, как и f(x)в C-подобных языках. И вы не можете с этим поделать. Но это может быть действительно приятно и менее загромождено во многих сценариях, не связанных с гольфом. В Elm нет побитовых операторов (например, &), поэтому and x yздесь просто вызов функции.
Евгений Малютин
Понятно, спасибо за объяснение!
MilkyWay90
@ MilkyWay90 на самом деле, мне удалось отрезать один пробел (и байт), используя оператор трубы <|вместо скобок. Спасибо за вопрос!
Евгений Малютин
Пожалуйста! Если вы заинтересованы в создании нового решения, вы можете обратиться за помощью в Девятнадцатый байт (наш чат SE). Если вы создаете задачу по написанию кода, вы можете публиковать ее в «Песочнице» (на мета) и размещать ссылку на вопрос в «Девятнадцатом байте» каждый день.
MilkyWay90
1

Python, 82 71 байт

0-7

-11 байт благодаря только ASCII

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

TIO

Бенджамин Уркхарт
источник
80, python 2 , 76, python 2
только для ASCII
также 76 , и -2, потому что f=могут быть удалены, так как не являются рекурсивными
только ASCII
подожди, это не сработает
только ASCII
2
здесь мы идем, 71
только ASCII
Похоже, что вы могли бы сделать лучше с int.from_bytesкодировкой без UTF, но ... не уверен, как это сделать на TIO
только для ASCII
0

Scala , 161 байт

Выбор COMPUTER в качестве меток.

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)

Попробуйте онлайн!

Питер
источник
1
это код гольф: | Вы должны сделать его как можно короче
только ASCII
88
только ASCII
Да, я поставил перед собой задачу использовать scala и настоящие лейблы, а не просто нативные 0-7. Попробуйте побить это.
Питер
133
только для ASCII
118: P
только ASCII
0

Scala , 70 байт

Выбор 0-7 нативных целых чисел в качестве меток.

Сжатый матрицу в 32-байтовую строку ASCII, каждая пара чисел n0, n1 в 1 символ c = n0 + 8 * n1 + 49. Начиная с 49 до этого у нас нет \ в закодированной строке.

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

Попробуйте онлайн!

Питер
источник
-3

Wolfram Language (Mathematica), 7 байтов (кодировка UTF-8)

#⊙#2&

Чистая функция, принимающая два аргумента. Символ представлен здесь как на самом деле частный Unicode-символ Mathematica F3DE (3 байта), который представляет функциюPermutationProduct .

Mathematica знает о диэдральных группах и представляет элементы различных групп в виде перестановок, написанных с помощью Cyclesкоманды. Например, запустив команду

GroupElements[DihedralGroup[4]]

дает выход:

{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 это функция, которая умножает элементы группы при написании в этой форме.

Поскольку нам разрешено выбирать наши собственные метки, эта функция принимает эти метки для элементов группы; связь между этими ярлыками и ярлыками в сообщении о проблеме определяется следующим образом:

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 Есть встроенный.

Грег Мартин
источник
8
Метки должны быть от 0 до 255 или одиночные байты.
xnor
Достаточно справедливо (я счастлив, что обнаружил эту функцию независимо). Вы можете уточнить это в ОП? Прямо сейчас это звучит как «выберите свои собственные ярлыки» (выделено), а затем пара возможных вариантов («вы можете ...»).
Грег Мартин
1
О, я вижу, как ты это читаешь; извините за то, что вы неясны здесь и ведете вас по неверному пути. Позвольте мне попытаться перефразировать это.
xnor