Ротационная инвариантная дактилоскопия

15

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

Например, если у нас есть L-тетромино

x
x
xx

мы хотели бы иметь такой же отпечаток пальца, как любой из них:

         xx
  x       x      xxx
xxx  ,    x  or  x

Примечание. Мы допускаем только повороты на плоскости (т. Е. Они являются односторонними многочленами), и поэтому следующий полиомино будет другим:

 x
 x
xx 

Вызов

Задача для этой задачи состоит в том, чтобы реализовать функцию / программу снятия отпечатков пальцев, которая принимает булеву / -значную матрицу / список списков / строку / .., кодирующую polyomino, и возвращает строку - отпечаток пальца Полимин. Отпечаток пальца должен быть одинаковым для всех возможных поворотов (в общем 4).м×N0,1

Ввод, вывод

  • m1n 1 и (т. е. нет пустого polyomino)n1
  • вы гарантировано, что настолько малы, насколько это возможно (т.е. все обрезаются, чтобы соответствовать иm,n0mn
  • вы гарантировано, что вход
    • просто подключен
    • не имеет отверстий
  • вывод должен быть строкой, которая является одинаковой для каждого возможного поворота polyomino

Примеры

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

Вращения L-тетромино из примера:

[[1,0],[1,0],[1,1]]
[[0,0,1],[1,1,1]]
[[1,1],[0,1],[0,1]]
[[1,1,1],[1,0,0]]

J-тетромино:

[[0,1],[0,1],[1,1]]
[[1,1,1],[0,0,1]]
[[1,1],[1,0],[1,0]]
[[1,0,0],[1,1,1]]

Блок полиомино:

[[1]]

5×1 бар:

[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]

2×2 угол:

[[1,1],[1,0]]
[[1,0],[1,1]]
[[0,1],[1,1]]
[[1,1],[0,1]]

W-пентомино:

[[1,0,0],[1,1,0],[0,1,1]]
[[0,0,1],[0,1,1],[1,1,0]]
[[1,1,0],[0,1,1],[0,0,1]]
[[0,1,1],[1,1,0],[1,0,0]]
ბიმო
источник
Относящиеся .
მოიმო
Если я всегда выводил ""(пустую строку), удовлетворял ли я всем требованиям?
Даниэль Вагнер
@DanielWagner: «[..] для любых двух полиоминиумов из двух разных классов [отпечатки пальцев] должны отличаться » - так нет, это будет недопустимо.
მოიმო
Действительно ли вывод всех возможных вращений массива, последовательно отсортированных? Пример
Лохматый
1
@ Shaggy: Да, это будет соответствовать всем критериям.
მოიმო

Ответы:

7

Python 2 , 48 байт

f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1))

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

Принимает самое большое из четырех вращений с точки зрения сравнения списка. Основано на решении FlipTack .

Код использует способность Python 2 сравнивать объекты разных типов. Базовое значение 0безвредно, maxпоскольку оно меньше любого списка. Кроме того, zipвыдает список кортежей, в то время как входные данные представляют собой список списков, но кортежи больше, чем списки, поэтому входной список списков никогда не является претендентом. Вот почему мы вращаемся 5 раз, а не 4, чтобы мы вернулись к дублированной версии исходного списка. (Взятие списка кортежей также будет работать, если это допустимая форма ввода.)

XNOR
источник
4

Python 3 , 63 байта

def f(m):M=[];exec("m=[*zip(*m[::-1])];M+=m,;"*4);return min(M)

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

Находит вращение с лексографическим минимумом и печатает его.

Лямбда-форма входит с тем же количеством байтов:

lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M[-4:])

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

FlipTack
источник
Переписать как lambdaможно добраться до 58 lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M). Работает потому что execвсегда возвращается None.
Недла2004
@ nedla2004 Это может быть выполнено только один раз, а затем становится хитрым, так как Mуже заполнено ...
FlipTack
@ nedla2004 ... но учет проблемы M[-4:]может привести к тому же количеству байтов.
FlipTack
Я вижу, что тест, который я использовал, был просто проверкой входных данных с тем же "хешем", поэтому я никогда не сталкивался с этим. Это имеет смысл.
Недла2004
2

Желе , 5 байт

ZU$ƬṂ

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

Полная программа.

Просто генерирует все возможные повороты и выбирает лексикографический минимум.

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

Эрик Outgolfer
источник
когда я прочитал вызов, я знал, что это произойдет :)
ngn
2

К (нгн / к) , 16 байт

{a@*<a:3{+|x}\x}

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

мин оборотов

{ } функция с аргументом x

{+|x}повернуть, т.е. перевернуть ( |) и переставить ( +)

3{ }\применять 3 раза, сохраняя промежуточные результаты; это возвращает список из 4 вращений

a: назначить в a

< вознесение (вычисление сортировки по возрастанию)

* первый

a@индекс aс этим

СПП
источник
1

Japt -g, 6 байт

4Æ=zÃñ

Попытайся

           :Implicit input of 2d-array U
4Æ         :Map the range [0,4)
   z       :  Rotate U 90 degrees
  =        :  Reassign to U
    Ã      :End map
     ñ     :Sort
           :Implicit output of first element
мохнатый
источник
Нужен ли -gфлаг? Сортировка должна означать, что все начальные повороты заканчиваются одним и тем же списком, поэтому полный список должен работать как отпечаток пальца, если я что-то не пропустил.
Камил Дракари
@KamilDrakari, вы могли бы быть правы - как я уже сказал, я не уверен, что полностью понял проблему. Не беда, оставляя это внутри, хотя, это не стоит никаких байтов.
Лохматый
@KamilDrakari: Это не обязательно, но это и не вредно, поскольку не учитывается в счетах.
ბიმო
1

J , 16 байт

-2 байта благодаря Shaggy

[:/:~|.@|:^:(<4)

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

J , 18 байт

0{[:/:~|.@|:^:(<4)

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

Возвращает первый элемент в списке лексикографически отсортированных вращений полиомино.

Объяснение:

            ^:(<4)  - do the verb on the left 4 times, storing all the steps
       |.@|:        - tranpose and reverse
    /:~             - sort up the 4 matrices
  [:                - cap the fork
0{                  - take the first matrix  
Гален Иванов
источник
@ Shaggy Спасибо!
Гален Иванов
0

05AB1E , 10 8 байт

3FÂø})Σ˜

-2 байта благодаря @Shaggy .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

3F  }       # Loop 3 times
  Â         #  Bifurcate (short for Duplicate & Reverse) the top of the stack
            #  (which is the input-matrix implicitly the first iteration)
   ø        #  Transpose: swap rows/columns
     )      # After the loop, wrap everything on the stack in a list
      Σ˜    # Sort this list of matrices by their flattened array (and output implicitly)

ПРИМЕЧАНИЕ. Принятие минимума с ßили Wбудет неявно сглаживаться, поэтому будет выводиться 0. И сортировка с помощью {, кажется, не работает для списка матриц, поэтому я использую Σ˜вместо этого.

Кевин Круйссен
источник
1
@ Shaggy Спасибо! :) В этом случае последние два байта могут быть удалены, поскольку }выполняется неявно, если после этого ничего не происходит.
Кевин Круйссен
1
Сегодня я узнал кое-что о 05AB1E! :) То же самое в Japt.
Лохматый