Является ли этот квадрат симметричным?

22

Напишите программу или функцию, которая принимает текстовую сетку 4 × 4, состоящую из ровно 4 A, 4 B, 4 Cи 4 D, например:

ACDC
BBCA
BADD
ABCD

Они ABCDмогут быть в любом порядке, но всегда будет 4 каждого. Вы можете предположить, что ввод действителен. При желании вы также можете предположить, что у него есть завершающий символ новой строки и / или что он идет одной строкой в ​​порядке чтения, например ACDCBBCABADDABCD. Вы также можете заменить символы ABCDна 0123или 1234соответственно, если хотите (но это все).

Выведите истинное значение, если текстовая сетка имеет отражательную или вращательную симметрию. В частности:

  • Если есть центральная горизонтальная линия симметрии. например

    BACD
    BACD 
    BACD \___ bottom mirrors top
    BACD /
    
  • Если есть центральная вертикальная линия симметрии. например

    BCCB
    DAAD
    CAAC
    BDDB
      \/___ right mirrors left
    
  • Если есть диагональная линия симметрии (в любом направлении). например

         ___ diagonally mirrored
        /
    ABDC
    BACD
    DCAB
    CDBA
        \___ diagonally mirrored
    
  • Если есть вращательная симметрия 90 °. например

    BDAB
    ACCD    same if rotated 90 degrees (or 180 or 270)
    DCCA
    BADB
    
  • Если есть вращательная симметрия 180 °. например

    DBCA
    BDCA    same if rotated 180 degrees
    ACDB
    ACBD
    

(Обратите внимание, что трансляционная симметрия здесь не играет роли.)

Выведите ложное значение, если сетка не имеет одну из симметрий, упомянутых выше. например, самый первый пример сетки.

Самый короткий код в байтах побеждает.

Кальвин Хобби
источник
Можем ли мы взять список из четырех строк в качестве входных данных?
Мартин Эндер
@MartinEnder Да, хорошо.
Увлечения Кельвина
4
Я только что прочитал это и подумал: «Нет», лол
Шон Уайлд,
Если бы вы думали возвести квадрат в квадрат, вы могли бы также принять во внимание трансляционную симметрию.
Нил
1
@ Adám Нет. Нет больше форматов ввода. Я чувствую, что не должен был позволять Мартину.
Увлечения Кэлвина

Ответы:

16

CJam, 16 байтов

{{z_W%_}4*;])e=}

Безымянный блок, который ожидает входные данные в виде списка из четырех строк в верхней части стека и оставляет 0(ложное значение) для асимметричных входных данных и положительное целое число (истинное значение) для симметричных входных данных.

Проверьте это здесь. Или запустить полный набор тестов.

объяснение

Симметрии квадрата - это элементы диэдральной группы порядка 8 (которые представляют собой всего лишь 4 поворота квадрата и те же 4 поворота некоторой отраженной версии квадрата). Невозможно создать эту группу из многократного применения одной перестановки. Но два отражения всегда дают некоторое вращение. Следовательно, вся группа может быть создана путем чередования двух отражений четыре раза. (Нам просто нужно убедиться, что два отражения дают поворот на 90 или 270 градусов, а не на 0 или 180.)

Задача спрашивает, равен ли входной квадрат какой-либо из 7 других симметрий. Таким образом, этот ответ просто генерирует их все, а затем проверяет, входит ли вход среди других.

{      e# Run this block 4 times.
  z_   e# Transpose the grid and duplicate it. (This is one type of reflection.)
  W%_  e# Reverse the lines and duplicate it. (This is another type of
       e# reflection. Together they rotate the grid by 90 degrees.)
}4*    e# The last element will be the original grid again.
;      e# Discard one copy of that original grid.
]      e# Wrap all symmetries in a list.
)      e# Pull off the original grid.
e=     e# Count how many times it appears among the other symmetries.

Чтобы увидеть, как повторное применение zи W%генерирует все симметрии, взгляните на эту «диаграмму»:

     0123
     4567
     89ab
     cdef

     original

 z   048c       W%       37bf
-->  159d  ----------->  26ae
     26ae                159d
     37bf                048c

     diag. refl.         rot. 90 degrees ccw

 z   3210       W%       fedc
-->  7654  ----------->  ba98
     ba98                7654
     fedc                3210

     vert. refl.        rot. 180 degrees

 z   fb73       W%       c840
-->  ea62  ----------->  d951
     d951                ea62
     c840                fb73

     antidiag. refl.     rot. 270 degrees ccw

 z   cdef       W%       0123
-->  89ab  ----------->  4567
     4567                89ab
     0123                cdef

     horiz. refl.        original
Мартин Эндер
источник
Вау, можешь объяснить это? У вас есть встроенный для всех вращений / сальто?
Адам
@ Adám Немного добавлю полное объяснение, но zоно транспонировано и W%переворачивает линии, поэтому я просто генерирую все симметрии путем их повторного применения.
Мартин Эндер
4
Конечно, в первом значении нет ничего особенного, но, к сожалению, более пуристический подход к подсчету, получаете ли вы 8 различных значений, стоит на один символ больше.
Питер Тейлор
8

Pyth, 11 байт

<7.u?%Y2CN_

Тестирование

При этом используется метод транспонирования и реверса Мартина, но с изюминкой. В то время как другие решения явно сгенерировали все 8 симметрий, а затем подсчитали количество появлений оригинала, эта программа использует .uфункцию Пита .

.uФункция «Применить до повтора не найден». В этом случае мы поочередно транспонируем и обращаемся до тех пор, пока не произойдет повторение, а затем накапливаем результаты в список. Затем я удаляю последние 7 значений, так что останется значение, только если не было симметрии, и первое повторение произошло после того, как все 8 отражений и повторений были сгенерированы.

Объяснение:

<7.u?%Y2CN_
<7.u?%Y2CN_NQ    Implicit variables
                 Q = eval(input())
  .u        Q    Starting with Q, apply the following until a repeat occurs, 
                 then accumulate all values into a list.
    ?%Y2         If the iteration number is odd
        CN       Transpose
          _N     Else reverse
<7               Remove the last 7 results
isaacg
источник
4

Perl 61 60 байт

Включает +3 для -p0a

Дайте входной квадрат на STDIN, печатает 0 для отсутствия симметрии, в противном случае некоторое положительное число

./symmetry.pl
DBCA
BDCA
ACDB
ACBD
^D

symmetry.pl:

#!/usr/bin/perl -p0a
s,.,chop$F[$i++/($j-4?1:4)%4],eg;$\+=$$_++;++$j<8&&redo}{
Тон Хоспел
источник
3

Брахилог , 38 36 байт

@eL:1fbeL
(L;?:raL)(.;L$\.;L$/.;Lr.)

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

Это ожидает список строк в качестве ввода. Это печатает либо true.или false..

объяснение

  • Основной предикат:

    @eL    Split each line into a list of chars ; call that list of lists L
    :1f    Find all symmetries
    b      Remove the first one (the identity)
    eL     L is an element of that list of symmetries
    
  • Предикат 1: Выход является одной из 8 симметрий входа.

    (
        L             L = Input
    ;             Or
        ?:raL         L = reverse all lines of the input
    )
    (
        .             Output = L
    ;             Or
        L$\.          Output = transpose of L    
    ;             Or
        L$/.          Output = antitranspose of L
    ;             Or
        Lr.           Output = reverse of L
    )
    
Fatalize
источник
3

TSQL, 229 байт

Имейте в виду, что TSQL не имеет встроенной функции для поворота, так что это включено в код.

Golfed:

DECLARE @1 char(16)=
'BCCBDAADCAACBDDB'

,@i INT=0,@ varchar(16)=''WHILE @i<16SELECT @+=substring(@1,@i*4%16+@i/4+1,1),@i+=1SELECT sign(count(*))FROM(SELECT LEFT(x,8)a,RIGHT(x,4)b,substring(x,9,4)c FROM(values(@1),(@))x(x))x WHERE c+b=reverse(a)or a=reverse(b+c)or a=b+c

Ungolfed:

DECLARE @1 char(16)=
'BCCBDAADCAACBDDB'

,@i INT=0,@ varchar(16)=''
WHILE @i<16
  SELECT @+=substring(@1,@i*4%16+@i/4+1,1),@i+=1

SELECT sign(count(*))
FROM
  (SELECT LEFT(x,8)a,RIGHT(x,4)b,substring(x,9,4)c
   FROM(values(@1),(@))x(x))x
WHERE c+b=reverse(a)or a=reverse(b+c)or a=b+c

скрипка

t-clausen.dk
источник
2

Python 2, 154 146 байт

Проверяет, является ли любое из необходимых преобразований эквивалентным оригиналу, используя массивы numpy. Ввод принимается как список из четырех строк.

from numpy import*
A=array(map(list,input()))
R=rot90
T=transpose(A)
print any([all(A==Z)for Z in(A[:,::-1],A[::-1],R(A),R(A,2),R(A,3),T,R(T,2))])

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

Принятие ввода в виде одной строки на один символ длиннее, с A=array(list(input())).reshape(4,4). A[:,::-1]так же, как fliplr(A). A[::-1]так же, как flipud(A).

mbomb007
источник
Может быть, использовать map(list,input())вместо[list(r)for r in input()]
Cyoce
@Cyoce Спасибо. ИДК, как я это пропустил.
mbomb007
anyпринимает выражение генератора, поэтому вы можете сохранить несколько байтов, отбросив внешнюю пару квадратных скобок.
TheBikingViking
@TheBikingViking Я уже пробовал это. Если вы передадите генератор, он вернет генератор, и printоператор не будет работать. Попробуйте разветвить мой онлайн-код и запустить его таким образом, чтобы увидеть.
mbomb007
Ах хорошо. Я не понимал, что это сломает print.
TheBikingViking
2

Python 3, 99 байт

def f(x):
 t=x;c=[]
 for i in range(7):*t,=[map(''.join,zip(*t)),t[::-1]][i%2];c+=t,
 return x in c

Функция, которая принимает через аргумент ввод списка строк и возвращает Trueили Falseкак релевантный.

Это использует тот же подход, что и ответ @ MartinEnder .

Как это работает

def f(x)                Function with input list of strings x
 t=x;c=[]               Initilaise temporary square t and combination list c
 for i in range(7):...  For i in range [0,6]:
 [...][i%2]              If i is even:
 zip(*t)                  transpose(t)
 *t,=map(''.join,...)     t = t with each line concatenated (such that t is in the same
                          format as x)
                         Else:
 *t,=t[::-1]              t = reverse(t)
 c+=t,                   Append t to c
 return x in c           Return True if x is in c else return False

Попробуйте это на Ideone

TheBikingViking
источник
2

JavaScript (ES6), 131 байт

s=>[...`0101010`].map(c=>+c?``+b.reverse():`${b=b.map((s,i)=>s.replace(/./g,(_,j)=>b[j][i]))}`,b=a=s.match(/..../g)).includes(``+a)

17 байтов могут быть удалены, если вы передадите массив из 4 строк напрямую. Я попробовал бит-тиддлинг (ввод в "0123301223011230"формате), но это заняло у меня 199 байт:

s=>[...'0101010'].map(c=>r=+c?r<<24&255<<24|r<<8&255<<16|r>>8&255<<8|r>>>24:r&0xc0300c03|r<<6&806093568|r<<12&3075<<16|r<<18&3<<24|r>>6&0xc0300c|r>>12&49200|r>>18&192,r=n=parseInt(s,4)|0).includes(n)
Нил
источник