Что это за тетромино?

54

Учитывая 16-разрядное целое число без знака N , ваша задача состоит в том, чтобы определить, соответствует ли его двоичное представление, отображенное в матрице 4x4, форме тетромино , и если да, то какой это форма.

матрица

Каждый бит N отображается в матрице 4x4 слева направо и сверху вниз, начиная с самого старшего.

Пример :

N = 17600
binary representation: 0100010011000000
matrix: [ [ 0, 1, 0, 0 ],
          [ 0, 1, 0, 0 ],
          [ 1, 1, 0, 0 ],
          [ 0, 0, 0, 0 ] ]

Тетромино формы

Основные формы

Существует 7 форм тетромино, обозначенных буквами O , I , S , Z , L , J и T :

тетромино

Вращения и переводы

Если форма переведена и / или повернута в матрице 4x4, она все еще считается действительным вариантом того же тетромино. Например, 17600, 1136, 2272 и 1604 должны быть обозначены как J- тетромино:

действительные примеры J

Не оборачивайся!

Однако формы не могут быть обернуты или сдвинуты за пределы какой-либо границы матрицы. Например, ни 568, ни 688 не должны идентифицироваться как J- тетромино (не говоря уже о любой другой форме):

неверные примеры J

Разъяснения и правила

  • Вы можете принимать входные данные как целое число или непосредственно как 16 двоичных цифр в любом приемлемом формате, таком как двумерный массив, плоский массив или строка с разделителями.
  • Входными данными гарантированно является 16-разрядное целое число без знака (или его эквивалентное представление в виде массива или строки).
  • Когда правильная форма определена, вы должны напечатать или вернуть букву, идентифицирующую форму, в нижнем или верхнем регистре.
  • Если фигура не определена, вы должны напечатать или вернуть значение, которое не соответствует ни одной букве тетромино. Вы также можете вообще ничего не возвращать.
  • Чтобы считаться действительной, матрица должна содержать точную форму тетромино без каких-либо дополнительных ячеек (см. 1911 и 34953 в тестовых примерах).
  • Это , поэтому выигрывает самый короткий ответ в байтах!

Контрольные примеры

Вы можете перейти по этой ссылке, чтобы получить тестовые наборы в виде 2D-массивов.

0      -> false
50     -> false
51     -> 'O'
1911   -> false
15     -> 'I'
34952  -> 'I'
34953  -> false
1122   -> 'S'
3168   -> 'Z'
785    -> 'L'
1136   -> 'J'
568    -> false
688    -> false
35968  -> 'T'
19520  -> 'T'
Arnauld
источник
Интересно, что на днях я работал над чрезвычайно похожей проблемой, прежде чем отвлекся, создав технику использования цепочек функций func1 . func2 . func3в JS: P
ETHproductions
Могу ли я принять ввод как четыре строки, соединенные с 0, то есть 1111011110111101111для 65535?
ETHproductions
@ETHproductions Кажется, все в порядке. Я отредактировал задачу с немного смягченным форматом ввода.
Арно
3
I: 15,240,3840,4369,8738,17476,34952,61440J: 71,113,142,226,275,550,802,1100,1136,1604,1808,2272,3208,3616,4400,8800,12832,17600,18176,25664,28928,36352,51328,57856L: 23,46,116,232,368,547,736,785,1094,1570,1856,2188,3140,3712,5888,8752,11776,12560,17504,25120,29696,35008,50240,59392O: 51,102,204,816,1632,3264,13056,26112,52224S: 54,108,561,864,1122,1728,2244,8976,13824,17952,27648,35904T: 39,78,114,228,305,562,610,624,1124,1220,1248,1824,2248,3648,4880,8992,9760,9984,17984,19520,19968,29184,35968,58368Z:99,198,306,612,1224,1584,3168,4896,9792,19584,25344,50688
Тост инженера
^ Сгенерировано с использованием ответа Lynn's Python 3, потому что у него были удобные форматы ввода / вывода.
Тост инженера

Ответы:

6

Желе ,  54 43 42  41 байт

-1 байт благодаря Эрику Аутгольферу (перенести транспонирование в повторяющуюся цепь)

T€FṀ⁸ṙ€Zµ⁺F
ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵»

Монадическая ссылка, берущая двумерный массив целых чисел ( 1s и 0s) и возвращающая строчную букву oiszljtдля соответствующего tetromino или, wесли она недействительна.

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

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

Как?

Это сначала берет все четыре вращения входа. Затем он сдвигает установленные биты каждого из них вправо, а затем как можно ниже, и преобразует результаты в двоичные числа. Затем он ищет минимальный результат в списке минимальных таких представлений каждого действительного тетромино и использует уменьшенный результат для индексации в два сцепленных словарных слова zoist+ jowl, получая результат, wкогда совпадение не найдено.

T€FṀ⁸ṙ€Zµ⁺F - Link 1, shift set bits right & then down : list of lists of bits          
        µ⁺  - perform the following twice, 1st with x=input, then with x=result of that):
T€          -   truthy indexes of €ach
  F         -   flatten into a single list
   Ṁ        -   maximum (the index of the right-most bit)
    ⁸       -   chain's left argument, x
     ṙ€     -   rotate €ach left by that amount
       Z    -   transpose the result
          F - flatten (avoids an € in the main link moving this into here)

ZU$3СǀḄṂ“çc3Ð6'G‘i’ị“¥Çıƭ⁵» - Main link: list of lists of bits (the integers 0 or 1)
   3С                        - repeat this 3 times collecting the 4 results:
  $                           -   last two links as a monad:
Z                             -     transpose
 U                            -     upend (reverse each) -- net effect rotate 90° CW
      Ç€                      - call the last link as a monad for €ach
        Ḅ                     - convert from binary (vectorises)
         Ṃ                    - minimum (of the four results)
          “çc3Ð6'G‘           - code-page indexes = [23,99,51,15,54,39,71]
                              -   ...the minimal such results for l,z,o,i,s,t,j shapes
                   i          - 1-based index of minimum in there or 0 if not found
                    ’         - decrement
                      “¥Çıƭ⁵» - compressed words: "zoist"+"jowl" = "zoistjowl"
                     ị        - index into (1 indexed & modular, so -1 yields 'w',
                              -             0 yields 'l', 1 yields 'z', ...)

Предыдущий метод (54 байта)

Fœr0Ḅ“çc3Ðñ'G‘i
;Z$Ḅ©f“¦µ½¿Æ‘ȯ®¬S>2ȧZU$3СǀṀ’ị“¥Çıƭ⁵»

Монадическая ссылка, берущая двумерный массив целых чисел ( 1s и 0s) и возвращающая строчную букву oiszljtдля соответствующего tetromino или, wесли она недействительна.

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

При этом проверяется наличие как минимум трех пустых строк (строк + столбцов) и того, что определенные последовательности битов не присутствуют ни в одной строке (в частности, числа 5, 9, 10, 11 и 13), что вместе гарантирует, что следующий шаг не приведет к ложные срабатывания. Затем он выравнивает, а затем сдвигает по полу двоичное число (чередуя конечные нули перед преобразованием) каждого из четырех поворотов и ищет минимальный результат в списке чисел, используя уменьшенный результат для индексации в двух составных словарных словах. zoist+ jowl, уступая, wкогда не найдено ни одного совпадения.

Джонатан Аллан
источник
И я знал, что есть лучший способ, чем жесткое программирование ...
Эрик Аутгольфер
Кстати, я думаю, что этот код зависит от совпадения (потому что, zoistjowlв противном случае, обычно не подходит для строки, в противном случае: p)
Эрик Outgolfer
Что вы имеете в виду "зависит от совпадения"? (поиск по словарю в ...Ṁị“LZOISTJWлюбом случае сохраняет только один байт )
Джонатан Аллан
Хм ... да, я знал, что это не продлится долго ... Кстати, я думаю, что ты украл мой ZU$3С: p
Эрик Outgolfer
Я пытался сделать тот же метод вчера после отправки предыдущего, но думаю, что я немного устал.
Джонатан Аллан
28

Python 3 , 124 байта

def f(n):
 while n&4369<n/n:n>>=1
 while n&15<1:n>>=4
 return'TJLZSIO'["rēȣc63ıGtIJȱᄑ@'̢̑@@@@Ȳq".index(chr(n))%7]

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

Ожидается целое число n, представляющее двоичную матрицу 4 × 4. Выдает, если тетромино не найдено.

Линия 2 перемещает форму вправо, пока 1 не окажется в крайнем правом столбце. (4369 0001 0001 0001 0001в двоичном виде.) Линия 3 понижает форму, пока 1 не окажется в нижнем ряду. Вместе это превращается, например:

    0 1 0 0        0 0 0 0
    1 1 1 0  into  0 0 0 0
    0 0 0 0        0 0 1 0
    0 0 0 0        0 1 1 1

Затем мы ищем индекс nв этом списке:

 [114  275  547   99   54   15   51
  305   71  116  306  561 4369   64
   39  802  785   64   64   64   64
  562  113   23]
#   T    J    L    Z    S    I    O

Каждый столбец индексов, эквивалентных по модулю 7, соответствует форме тетромино. 64 ( @) используется как значение заполнения, так как nв этот момент в коде не может быть 64.

NB. Исключение выдается для ввода 0путем вычисления n/nвместо 1.

Линн
источник
Почему ваша двоичная строка работает? У меня были проблемы с этим в Python 3, см. Комментарии codegolf.stackexchange.com/a/85201/53667
Карл Напф
Python использует UTF-8 в качестве кодировки по умолчанию для исходного кода и для вывода текста. Но файлы PPM не читаются в UTF-8. При запуске print("ÿ"), байты , которые получают письменные есть c3 bf 0a, а не ff 0a, и изображения PPM превращается в мусор.
Линн
8

APL (Dyalog) , 95 94 93 89 87 байт

-2 благодаря Захари

Требуется ⎕IO←0по умолчанию во многих системах. Принимает булеву матрицу (любой формы!) В качестве аргумента. Ничего не возвращает, если заданное количество битов не равно четырем, и пустая строка, если четыре заданных бита не образуют тетромино.

{4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K2J),(⍳3)⊖¨⊂J1,⍪K31)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}

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

Работает, создавая все четыре вращения входа, а затем ищет каждое тетромино в каждом вращении.

{} Анонимная функция, в которой аргумент представлен :

,⍵ рассуждать

+/ подвести итог

4= четыре равны этому?

: если так, то (иначе ничего не вернуть):

  ⍳4 Первые четыре ɩ ndices; [0,1,2,3]

  ⍵∘{ Применить следующую функцию к каждому, используя ввод как фиксированный левый аргумент

    левый аргумент т.е. вход

   ⊢⍺ дать это (отделяется от )

   ⌽∘⍉⍣⍵ отразить и переставить (т.е. повернуть на 90 °) раз

  ()∘.⍷ Внешний «продукт», но с использованием Find *, следующего списка и поворотов:

   3↑1 взять три элемента из одного, дополнив нулями; [1,0,0]

   K← сохранить это как K

    таблица (превратить в вектор-столбец); [[1],[0],[0]]

   1, добавить один; [[1,1],[1,0],[1,0]]( "J")

   J← хранить как J

   ()⊖¨⊂ Поверните весь J вертикально, каждый из следующих шагов:

    ⍳3 Первые три ɩ ntegers;[0,1,2]

   у нас есть [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]](«J», «L», «T»)

   (), Добавьте следующий список:

    2⊖J поверните Jдва шага вертикально; [[1,0],[1,1],[1,0]]( "Т")

    K⌽ поверните строки этого на 1, 0 и 0 шагов соответственно; [[0,1],[1,1],[1,0]]( "Z")

    0 1⌽¨⊂ вращать весь массив вертикально, не раз и не один раз; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (), Добавьте следующий список:

     (2 2)4⍴¨1 преобразовать единицу в каждую из матрицы 2 × 2 и списка из 4 элементов; [[[1,1],[1,1]],[1,1,1,1]](«О», «Я»)

  1∊¨ для каждого один член?

  ∨/ горизонтальное уменьшение ИЛИ (то есть поперек поворотов; один логический для каждой фигуры)

  'OIZSLJT'/⍨ используйте это для фильтрации строки

* Find возвращает логический массив той же формы, что и его правый аргумент, с указанием левого верхнего угла всех подмассивов, идентичных левому аргументу.

Адам
источник
Будет ли это работать? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Захари
@ Zacharý Да, спасибо, готово.
Адам
7

JavaScript (ES6), 242 212 172 164 байта

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${'99,33825|15,51|2145,195|561,2115|57,1059|135,71|1073'.split`,`[y].replace(/\d+/g,C=x=>x?x%2+C(x>>1)+x%2:'|')})0*$`))

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

Принимает строку битов со строками, разделенными символом 0s ( '0001000110001000000'представляющими 0001 0011 0010 0000), и возвращает массив, содержащий символ, представляющий тетромино, или массив, не содержащий ничего.

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

0 0 0 0   -> 0000 0110 1100 0000
0 1 1 0   -> 0000001100110000000
1 1 0 0   -> 110011
0 0 0 0   -> 51

0 1 0 0   -> 0100 0110 0010 0000
0 1 1 0   -> 0100001100001000000
0 0 1 0   -> 100001100001
0 0 0 0   -> 2145

Таким образом, чтобы проверить, содержит ли вход S tetromino, мы просто проверяем, содержит ли он двоичное представление одного 51или 2145только 0с s с каждой стороны.

Некоторые из тетромино имеют 4 ориентации. Если вы посмотрите на двоичные их представления, у каждого есть 2 представления, которые являются просто зеркалом двух других. Чтобы сэкономить пространство, двоичное представление создается вперед и назад одновременно с рекурсивной Cфункцией, что позволяет нам вводить только две ориентации и подразумевать две другие.


Альтернативный подход с помощью кодов:

x=>[...'OISZLJT'].filter((z,y)=>x.match(`^0*(${[...'÷,êÿ,óî,ûÝ,ëúüÏ,çöïþ,ßýíÞ'.split`,`[y]].map(c=>(C=n=>n?'1e'+(n%4+2)%5-0+C(n>>2):'')(c.charCodeAt())).join`|`})0*$`))
ETHproductions
источник
3

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

s`(.*1){5}.*

{s`.*1111.*
I
s`.*111(.{2,4})1.*
$.1
T`234`\LTJ
s`.*11(.{2,4})11.*
$.1
T`2-90`S\OZ4-9
s`.*4.*

O#$`.
$.%`
O#$^`

Попробуйте онлайн! Ссылка включает в себя контрольные примеры плюс заголовок для преобразования из целых чисел в матрицу 4 × 4. Объяснение:

s`(.*1){5}.*

Удалить ввод, если он содержит 5 1с.

{s`.*1111.*
I

Проверьте все вращения входа (см. Ниже). Если вход содержит четыре последовательных 1с, это I.

s`.*111(.{2,4})1.*
$.1
T`234`\LTJ

Если он содержит три последовательных 1s плюс a 1на следующей строке под одним из трех, сопоставьте число промежуточных символов с соответствующей буквой результата.

s`.*11(.{2,4})11.*
$.1

Аналогично для двух смежных 1s, смежных с двумя смежными 1s на следующей строке.

T`2-90`S\OZ4-9

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

s`.*4.*

И сдавайтесь, если было выполнено слишком много вращений.

O#$`.
$.%`
O#$^`

Транспонировать и перевернуть массив, таким образом вращая его.

Нил
источник
3

MATL , 60 байт

Itt6tIl7tl7H15vHe"4:"G@X!HYa]4$v@BIthYaEqY+4=aa]v'OSZLJTI'w)

Ввод - это двоичный массив 4 × 4 (матрица), использующий в ;качестве разделителя строк. Ouput это буква или пусто для тетромино.

Попробуйте онлайн! Или проверьте все контрольные примеры (к выводу добавлена ​​точка, позволяющая идентифицировать пустой результат).

объяснение

Код строит 4 поворота входного массива 4 × 4 с шагом 90 градусов. Каждый повернутый массив дополняется 2 нулями вверх и вниз, что превращает его в массив 8 × 4. 4 массива вертикально объединены в массив 32 × 4. Четыре повернутых массива в этом объединенном массиве «изолированы» благодаря заполнению нулями.

Каждый из 7 возможных шаблонов проверяется, чтобы увидеть, присутствует ли он в массиве 32 × 4. Для этого используется цикл. Каждый шаблон определяется двумя числами, которые в двоичном виде дают соответствующую маску 0/1. Например, число 3, 6определяет форму «S».

7 наборов из 2 чисел расположены в матрице 2 × 7, из которой цикл будет последовательно выбирать каждый столбец. Матрица определяется путем помещения всех чисел в стек, связывания их в вектор и преобразования в двухрядную матрицу. Поскольку форма «I» определяется числом 15, за которым следует 0, размещение в конце позволяет неявно заполнять 0 функцией преобразования.

Затем маска дополняется 3 нулями в четырех направлениях. Это необходимо для обнаружения нежелательных значений на входе.

Чтобы увидеть, присутствует ли маска в массиве 32 × 4, последний преобразуется в биполярную форму (т.е. -1/1 вместо 0/1) и сворачивается с маской. Поскольку маска имеет 4 единицы, сопоставление происходит, если какая-либо запись в результате свертки равна 4.

В конце цикла было получено 7 ложных / истинных результатов, максимум один из которых является правдивым. Это используется для индексации в строку, содержащую возможные выходные буквы.

Луис Мендо
источник
3

Желе , 53 байта

ZL0ẋW⁸tZµ⁺ZU$3С“©©“œ“Ç¿“¦©¦“ƽ‘;Uḃ2$’¤iЀṀị“÷¶Ė¡µỵỤ»

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

Полная программа. Занимает 4х4. Печатает, mесли не тетромино, в противном случае печатает строчные.

Эрик Outgolfer
источник
Является ли ... допустимым массив массивов битов? Это спасло бы меня как 40 байтов
ETHproductions
@ETHproductions Вы можете использовать входные данные как целое число или непосредственно как двумерный массив 4x4 двоичных цифр или плоский массив из 16 двоичных цифр.
Эрик Outgolfer
Да, служит мне как раз для того, чтобы рассмотреть вопрос ...
ETHproductions
1

Perl 5 , 197 + 1 (-p) = 198 байт

s/(0000)*$//;1while s/(...)0(...)0(...)0(...)0/0${1}0${2}0${3}0${4}/;$_={51,O,15,I,4369,I,54,S,561,S,99,Z,306,Z,547,L,23,L,785,L,116,L,275,J,113,J,802,J,71,J,114,T,562,T,39,T,609,T}->{oct("0b".$_)}

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

Принимает 16-битную строку в качестве ввода. Ничего не выводится, если на входе нет одного тетромино.

Как?

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

Xcali
источник
1

APL (Dyalog) , 66 байт

{'TIOJSLZ-'[(¯51 144 64,,∘+⍨12J96 ¯48J64)⍳×/(+/-4×⊢)⍵/,0j1⊥¨⍳4 4]}

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

Аргумент является логическим вектором.

Вычисляет расстояния между точками со знаком и их центром тяжести в виде комплексных чисел (действительная и мнимая части - ∆x, ∆y) и умножает комплексные числа вместе. Это оказывается достаточно хорошим инвариантом, чтобы различать тетромино.

СПП
источник
Интересный метод.
Арно