В матрицах Паулей представляют собой набор матриц 2х2 , которые появляются очень часто в квантовой физике (нет, вам не нужно знать никакой квантовую физику для этой задачи). Если мы включим тождество в набор, четыре матрицы:

 σ0 =      σ1 =      σ2 =      σ3 = 
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]

Умножение двух из них всегда будет давать другую матрицу Паули, хотя это может быть умножена на один из сложных этапов 1, i, -1, -i. Так , например, .σ1σ3 = -iσ2

Ваша задача - умножить количество матриц Паули и вернуть полученную матрицу и фазу. Входной будет передано как непустая строка цифр 0до 3представляющих матрицы в . Вывод должен быть строкой , содержащей одну цифру для полученной матрицы, необязательно предшествует , или , чтобы указать фазу ( для ).σ0σ3i--i--1

Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Вы не должны использовать какие-либо встроенные (или сторонние) функции, связанные с матрицами Паули.

Это код гольф, самый короткий ответ (в байтах) выигрывает.

Тестовые случаи

1 => 1
13 => -i2
000 => 0
123 => i0
03022 => 3
02132230 => -i3
1320130100032 => i2
311220321030322113103 => -2
0223202330203313021301011023230323 => -i0
1323130203022111323321112122313213130330103202032222223 => -1

Pyth, 47 байтов

Я думаю, что это все еще пригодно для игры в гольф. Но это намного превосходит CJam.

p.U&-=T*q3l{[0bZ)^_1%-Zb3xbZmvdz@+c"i - -i")khT

Попробуйте онлайн: демонстрация или тестовый набор

объяснение

Определение результирующего типа матрицы - это просто сохранение всех чисел.

При умножении 2 матриц A*Bфаза изменяется, если не из матриц есть σ0и A != B.

                                                 implicit: T=10, z=input string
                            mvdz                 evaluate each char of the input 
 .U                                              reduce: b=first value, for Y in mvdz[1:]
    -=T                                            T -= ...
        q3l{[0bZ)                                     (3 == len(set([0,b,Z])))
       *         ^_1%-Zb3                             * (-1)^((Z-b)%3)
   &                                               and
                         xbY                       update b by (b xor Y)
                                 +c"i - -i")k    the list ["i", "-", "-i", ""]
                                @            hT  take the element at index T+1 (modulo wrapping)
p                                                print phase and matrix

Python 2, 108 89 87 86 байт

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`

(Спасибо @grc и @xnor за помощь)

объяснение

Давайте разделим коэффициент и базовую матрицу. Если мы сконцентрируемся только на базовой матрице, мы получим эту таблицу умножения (например, 13есть -i2, мы ставим 2)

  0123

0 0123
1 1032
2 2301
3 3210

что, случается, то же самое, что и битовое xor.

Теперь давайте сосредоточимся на коэффициентах. Если мы позволим 0123обозначить 1,i,-1,-iсоответственно, мы получим:

  0123

0 0000
1 0031
2 0103
3 0310

Для этого мы сначала проверяем, является ли любое число 0, выполняя m*yзаботу о левом столбце и верхней строке. Добавление в (m-y)%3затем дает:

  0123

0 0000
1 0021
2 0102
3 0210

что близко, кроме того, что у нас 2вместо 3. Мы учитываем это, выполняя *3/2.

Для индексации мы замечаем, что если мы возьмем строку "--i"и выберем каждый второй символ, начиная с индексов, 0123мы получим "-i","-","i","".

Сетчатка , 77 байт

Я думал, что воспользуюсь этой возможностью, чтобы показать новую функцию Retina: многоступенчатые петли. Это должно значительно сократить многие задачи (особенно условная замена).

ii
-
+`(.)\1|0

(.)-|(\d)(\d)
-$1$3$2
12
i3
23
i1
31
i2
)`(\d)i
i$1
^\D*$
$&0

Retina - это мой собственный язык программирования на основе регулярных выражений. Исходный код может быть сгруппирован по этапам: каждый этап состоит из двух строк, где первая содержит регулярное выражение (и, возможно, некоторую конфигурацию), а вторая строка является строкой замены. Затем этапы применяются к STDIN по порядку, а окончательный результат выводится на STDOUT.

Вы можете использовать вышеперечисленное непосредственно в качестве исходного файла с параметром -sкомандной строки. Тем не менее, я не считаю переключение, потому что вы также можете просто поместить каждую строку в отдельный файл (тогда вы потеряете 15 байтов для новых строк, но добавите +15 для дополнительных файлов).

объяснение

Новым в этом решении является )предпоследняя стадия. Это закрывает многоступенчатый цикл. Нет соответствия (, что означает, что цикл неявно начинается на первом этапе. Следовательно, первые 7 этапов повторяются до тех пор, пока полный проход через все 7 из них не перестанет изменять результат. Эти 7 этапов просто выполняют различные преобразования, которые постепенно уменьшают количество матриц в строке и объединяют фазы. Как только мы достигаем конечного результата, ни один из семи шаблонов больше не совпадает, и цикл заканчивается. После этого мы добавляем 0, если в результате еще нет цифры (поскольку на предыдущих этапах просто отбрасываются все идентификаторы, включая результат).

Вот что делают отдельные этапы:

ii
-

Объединяет все пары iв, -чтобы уменьшить фазу символов.

+`(.)\1|0
<empty>

Теперь, если осталось два последовательных идентичных символа, это либо одна, --либо две идентичные матрицы. В любом случае, умножение их дает идентичность. Но нам не нужны идентификаторы, поэтому мы просто удаляем их все, а также явные идентификаторы 0. Этот этап повторяется сам по себе, +пока результат не перестанет меняться. Это гарантирует, что такие вещи, как, 123321будут решены полностью, так что следующий шаг может предполагать, что все пары цифр различны.

(.)-|(\d)(\d)
-$1$3$2

На самом деле это две отдельные трансформации в одну (для гольфа). Обратите внимание, что если первая альтернатива совпадает $2и $3пуста, а вторая $1- пуста. Так что это можно разложить на эти два шага:

(\d)(\d)
-$2$1

Это просто меняет все пары цифр и добавляет знак минус. Так как мы удалили все 0с и все одинаковые пары, то это будет соответствовать только 12, 23, 31, 21, 32, 13. Этот шаг может показаться странным, но он позволяет мне проверить только половину этих случаев позже, потому что те, которые я не могу обработать, будут заменены здесь на следующей итерации.

Другая часть вышеупомянутой стадии была:

(.)-
-$1

Это постепенно перемещает -знаки полностью влево (одна позиция на итерацию). Я делаю это так, что в конечном итоге они все рядом и решаются на более раннем этапе.

12
i3
23
i1
31
i2

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

)`(\d)i
i$1

Это последний этап цикла. Это похоже на тот, который сдвигается -влево, за исключением i. Основное отличие состоит в том, что этот обмен iтолько с цифрами. Если бы я использовал (.)iтогда, в случаях, когда я получаю a -iили i-два, меняли местами бесконечно, и программа не заканчивалась. Так что это только меняет их справа от -знаков. Этого достаточно - пока все -и iпоявляются вместе в какой-то момент, они могут быть решены правильно.

^\D*$
$&0

Последний шаг (вне цикла). Помните, что мы всегда удаляли все идентификаторы, поэтому, если результат фактически является идентификатором (умноженным на фазу), у нас больше не будет требуемой цифры в выводе, поэтому мы добавляем ее обратно.

В качестве примера, вот все промежуточные формы 0223202330203313021301011023230323(этапы пропуска, которые не вносят никаких изменений):

0223202330203313021301011023230323

321321312        # Remove identities
-23-31-12-132    # Swap all pairs
-23-31-i3-132    # Resolve 12
-i1-31-i3-132    # Resolve 23
-i1-i2-i3-132    # Resolve 31
-i-1i-2i-3-312   # Move - to the left and swap pairs
-i-1i-2i-3-3i3   # Resolve 12
-i-i1-i2-3-i33   # Move i to the left
-i-i1-i2-3-i     # Remove identities
--ii-1i-2-3i     # Move - to the left
--ii-i1-2-i3     # Move i to the left
----i1-2-i3      # Resolve ii
i1-2-i3          # Remove identities
i-1-2i3          # Move - to the left
i-1-i23          # Move i to the left
-i-1i-32         # Move - to the left and swap pairs
-i-i1-32         # Move i to the left
--ii-1-23        # Move - to the left and swap pairs
--ii-1-i1        # Resolve 23
----1-i1         # Resolve ii
1-i1             # Remove identities
-1i1             # Move - to the left
-i11             # Move i to the left
-i               # Remove identities. Now the loop can't change this any longer.
-i0              # Fix the result by adding in the 0.

CJam, 58 56 байт

Я уверен, что это может быть много в гольфе, но здесь это идет:

L'i'-"-i"]q{+:G$i:XA<X{GiB%_2m8%!+m<XB%gX3%3-z*}?s}*\0=o

Попробуйте онлайн здесь или запустите полный пакет здесь