Który to tetromino?

54

Biorąc pod uwagę 16-bitową liczbę całkowitą bez znaku N , Twoim zadaniem jest ustalenie, czy jego reprezentacja binarna odwzorowana w macierzy 4x4 pasuje do kształtu tetromino , a jeśli tak, to jaki to jest kształt.

Matryca

Każdy bit N jest odwzorowany w macierzy 4x4, od lewej do prawej i od góry do dołu, zaczynając od najbardziej znaczącej.

Przykład :

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

Kształty Tetromino

Podstawowe kształty

Istnieje 7 kształtów tetromino, oznaczonych literami O , I , S , Z , L , J i T :

tetrominoes

Rotacje i tłumaczenia

Jeśli kształt jest translowany i / lub obracany w matrycy 4x4, nadal jest uważany za prawidłową odmianę tego samego tetromino. Na przykład 17600, 1136, 2272 i 1604 powinny zostać zidentyfikowane jako J tetrominoes:

prawidłowe przykłady J.

Nie zawijaj!

Jednak kształty nie mogą się zawijać ani być przesuwane poza jakąkolwiek granicę matrycy. Na przykład ani 568, ani 688 nie powinny być identyfikowane jako tetromino J (nie mówiąc już o żadnym innym kształcie):

niepoprawne przykłady J.

Wyjaśnienia i zasady

  • Możesz przyjmować dane wejściowe jako liczbę całkowitą lub bezpośrednio jako 16 cyfr binarnych w dowolnym rozsądnym formacie, takim jak tablica 2D, płaska tablica lub łańcuch rozdzielany.
  • Dane wejściowe mają gwarantowaną 16-bitową liczbę całkowitą bez znaku (lub ich równoważną reprezentację jako tablica lub ciąg znaków).
  • Po zidentyfikowaniu prawidłowego kształtu należy wydrukować lub zwrócić literę identyfikującą kształt, małymi lub dużymi literami.
  • Jeśli żaden kształt nie zostanie zidentyfikowany, musisz wydrukować lub zwrócić wartość, która nie pasuje do żadnej litery tetromino. Możesz także w ogóle nic nie zwracać.
  • Aby uznać za prawidłową, matryca musi zawierać dokładny kształt tetromino bez żadnych dodatkowych komórek (patrz 1911 i 34953 w przypadkach testowych).
  • To jest , więc wygrywa najkrótsza odpowiedź w bajtach!

Przypadki testowe

Możesz użyć tego linku, aby uzyskać przypadki testowe jako tablice 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
źródło
Co ciekawe, pracowałem nad bardzo podobnym problemem, pewnego dnia, zanim byłem rozproszony, tworząc technikę korzystania z łańcuchów funkcji func1 . func2 . func3w JS: P
ETHproductions
Czy mogę pobierać dane wejściowe, gdy cztery rzędy są połączone 0, tj. 1111011110111101111Dla 65535?
ETHprodukcje
@ETHproductions To wydaje się w porządku. Zredagowałem wyzwanie z nieco zrelaksowanym formatem wejściowym.
Arnauld,
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
Toast inżynierski
^ Wygenerowano przy użyciu odpowiedzi Lynna na Python 3, ponieważ miał on wygodne formaty wejścia / wyjścia.
Engineer Toast

Odpowiedzi:

6

Galaretka ,  54 43 42  41 bajtów

-1 bajt dzięki Erikowi Outgolferowi (przeniesienie transpozycji do powtarzającego się łańcucha)

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

Monadycznego Link biorąc 2D tablicę liczb całkowitych ( 1S i 0S) i powrocie małą literę oiszljtdla danego Tetromino lub wjeśli nieprawidłowy.

Wypróbuj online! lub zobacz pakiet testowy .

Zobacz także ten program, który wyświetla wszystkie 1820 możliwych tablic binarnych 2D z dokładnie czterema bitami ustawionymi wraz z ich wyjściami, posortowanymi według tych wyjść.

W jaki sposób?

Najpierw bierze wszystkie cztery obroty wejścia. Następnie przesuwa ustawione bity każdego z nich jak najdalej w prawo, a następnie jak najdalej na dół i konwertuje wyniki na liczby binarne. Następnie wyszukuje minimalny wynik na liście minimalnych takich reprezentacji każdego ważnego tetromino i używa zmniejszonego wyniku do indeksowania do dwóch połączonych słów słownika zoist+ jowl, uzyskując, wgdy nie znaleziono żadnego dopasowania.

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', ...)

Poprzednia metoda (54 bajty)

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

Monadycznego Link biorąc 2D tablicę liczb całkowitych ( 1S i 0S) i powrocie małą literę oiszljtdla danego Tetromino lub wjeśli nieprawidłowy.

Wypróbuj online!

To sprawdza, czy są co najmniej trzy puste linie (wiersze + kolumny) i czy pewne wzory bitów nie są obecne w żadnej linii (konkretnie liczby 5,9,10,11 i 13), to razem zapewnia, że ​​następny krok nie da rezultatu fałszywie dodatnie. Następnie spłaszcza, a następnie przesuwa piętro liczbę binarną (przez usunięcie końcowych zer przed konwersją) każdego z czterech obrotów i wyszukuje minimalny wynik na liście liczb, używając zmniejszonego wyniku do indeksowania do dwóch połączonych słów słownika zoist+ jowl, dając, wgdy nie znaleziono dopasowania.

Jonathan Allan
źródło
I wiedziałem, że jest lepszy sposób niż
na stałe
btw Myślę, że ten kod zależy od zbiegów okoliczności (ponieważ, no cóż, zoistjowlnormalnie nie pasowałby do łańcucha w przeciwnym razie: p)
Erik Outgolfer
Co masz na myśli mówiąc „zależy od przypadku”? (wyszukiwanie słownika i tak oszczędza tylko jeden bajt ...Ṁị“LZOISTJW)
Jonathan Allan
Hmm ... tak, wiedziałem, że to nie potrwa długo ... btw Myślę, że ukradłeś moje ZU$3С: p
Erik the Outgolfer
Próbowałem zrobić tę samą metodę wczoraj po przesłaniu poprzedniego, ale myślę, że byłem trochę zmęczony.
Jonathan Allan,
28

Python 3 , 124 bajty

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]

Wypróbuj online!

Oczekuje liczby całkowitej n reprezentującej macierz binarną 4 × 4. Rzuca, jeśli nie zostanie znalezione tetromino.

Linia 2 przesuwa kształt w prawo, aż 1 znajdzie się w skrajnej prawej kolumnie. (4369 jest 0001 0001 0001 0001dwójkowy.) Linia 3 obniża kształt, aż 1 znajdzie się w dolnym rzędzie. Razem to się zmienia np .:

    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

Następnie szukamy indeksu nna tej liście:

 [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

Każda kolumna indeksu równoważnego modulo 7 odpowiada kształtowi tetromino. 64 ( @) jest używane jako wartość dopełniania, ponieważ nw tym momencie kodu nie może być 64.

NB Zgłoszono wyjątek dla danych wejściowych za 0pomocą obliczeń n/nzamiast 1.

Lynn
źródło
Dlaczego działa twój ciąg binarny? Miałem z tym problemy w Pythonie 3, patrz komentarze codegolf.stackexchange.com/a/85201/53667
Karl Napf
Python używa UTF-8 jako domyślnego kodowania kodu źródłowego i tekstu wyjściowego. Ale pliki PPM nie są odczytywane w UTF-8. Po uruchomieniu print("ÿ")bajty, które są zapisywane c3 bf 0a, nie są ff 0a, a obraz PPM zamienia się w śmieci.
Lynn,
8

APL (Dyalog) , 95 94 93 89 87 bajtów

-2 dzięki Zacharý

Wymaga ⎕IO←0ustawienia domyślnego w wielu systemach. Jako argument przyjmuje macierz boolowską (dowolnego kształtu!). Nic nie zwraca, jeśli podana liczba bitów nie wynosi czterech, a pusta linia, jeśli cztery podane bity nie tworzą tetromino.

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

Wypróbuj online!

Działa, tworząc wszystkie cztery obroty wejścia, a następnie szukając każdego tetromino w każdym obrocie.

{} Anonimowa funkcja, w której argument reprezentowany jest przez :

,⍵ ravel (spłaszcz) argument

+/ zsumuj to

4= czy cztery są równe?

: jeśli tak, to (w przeciwnym razie nic nie zwracaj):

  ⍳4 Pierwsze cztery ɩ ndices; [0,1,2,3]

  ⍵∘{ Zastosuj następującą funkcję do każdej z nich, używając danych wejściowych jako ustalonego lewego argumentu

    lewy argument, tj. dane wejściowe

   ⊢⍺ dochód, (wydzielane z )

   ⌽∘⍉⍣⍵ lustro i transpozycja (tj. obrót o 90 °) razy

  ()∘.⍷ Zewnętrzny „produkt”, ale przy użyciu funkcji Znajdź * następującej listy i rotacji:

   3↑1 weź trzy elementy z jednego, wypełnienie zerami; [1,0,0]

   K← przechowuj to jako K

    tabela (przekształć w wektor kolumny); [[1],[0],[0]]

   1, przygotuj jeden; [[1,1],[1,0],[1,0]]("JOT")

   J← przechowywać jako J

   ()⊖¨⊂ Obróć cały J pionowo, każdy z następujących kroków:

    ⍳3 pierwsze trzy t ntegery;[0,1,2]

   mamy [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]](„J”, „L,„ T ”)

   (), Wstaw następującą listę:

    2⊖J obróć Jdwa kroki w pionie; [[1,0],[1,1],[1,0]](„T”)

    K⌽ obróć rzędy o odpowiednio 1, 0 i 0 kroków; [[0,1],[1,1],[1,0]](„Z”)

    0 1⌽¨⊂ obróć całą tablicę pionowo, nie raz i raz; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] („Z”, „S”)

    (), Wstaw następującą listę:

     (2 2)4⍴¨1 przekształć jeden w każdą z macierzy 2 × 2 i listy 4-elementowej; [[[1,1],[1,1]],[1,1,1,1]](„O”, „I”)

  1∊¨ czy każdy z nich jest członkiem?

  ∨/ pozioma redukcja OR (tj. w poprzek obrotu; jeden logiczny dla każdego kształtu)

  'OIZSLJT'/⍨ użyj tego do filtrowania ciągu

* Find zwraca tablicę boolowską o tym samym kształcie, co jej prawy argument, z tymi, które wskazują lewy górny róg wszystkich podpozycji identycznych z lewym argumentem.

Adám
źródło
Czy to zadziała? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zacharý
@ Zacharý Tak, dziękuję, gotowe.
Adám
7

JavaScript (ES6), 242 212 172 164 bajtów

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*$`))

Miało być tylko po to, żeby piłka się toczyła, ale trochę się spóźniłem ¯ \ _ (ツ) _ / ¯

Pobiera ciąg bitów, z wierszami oddzielonymi 0s ( '0001000110001000000'reprezentującymi 0001 0011 0010 0000) i zwraca tablicę zawierającą znak reprezentujący tetromino lub tablicę nie zawierającą niczego.

Działa to poprzez sprawdzanie każdego obrotu tetromino, aby sprawdzić, czy dane wejściowe w dowolnym punkcie zawierają tetromino, otoczone całkowicie zerami po obu stronach. Każde tetromino jest reprezentowane przez jedną lub więcej liczb binarnych:

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

Aby więc sprawdzić, czy dane wejściowe zawierają S tetromino, po prostu sprawdzamy, czy zawiera on binarną reprezentację jednego, 51czy 2145tylko 0s po obu stronach.

Kilka tetromino ma 4 orientacje. Jeśli spojrzysz na ich reprezentacje binarne, każda z nich ma 2 reprezentacje, które są po prostu odbiciem pozostałych dwóch. Aby zaoszczędzić miejsce, reprezentacja binarna jest budowana jednocześnie do przodu i do tyłu wraz z Cfunkcją rekurencyjną , co pozwala nam na wprowadzenie tylko dwóch orientacji i sugerowanie dwóch pozostałych.


Alternatywne podejście z kodami znaków:

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*$`))
ETHprodukcje
źródło
3

Siatkówka , 125 bajtów

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#$^`

Wypróbuj online! Link zawiera przypadki testowe oraz nagłówek do konwersji z liczb całkowitych na macierz 4 × 4. Wyjaśnienie:

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

Usuń wejście, jeśli zawiera 5 1s.

{s`.*1111.*
I

Sprawdź wszystkie obroty wejścia (patrz poniżej). Jeśli dane wejściowe zawierają cztery kolejne 1s, to jest to I.

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

Jeśli zawiera trzy kolejne 1s plus a 1w następnym wierszu pod jednym z trzech, to zamapuj liczbę znaków pośrednich na odpowiednią literę wyniku.

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

Podobnie dla dwóch sąsiadujących 1s sąsiadujących z dwoma sąsiadującymi 1s w następnej linii.

T`2-90`S\OZ4-9

Ale również policz liczbę obrotów, używając w przeciwnym razie nieużywanego 0s.

s`.*4.*

I poddaj się, jeśli wykonano zbyt wiele obrotów.

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

Transponuj i odwróć tablicę, obracając ją.

Neil
źródło
3

MATL , 60 bajtów

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

Dane wejściowe to binarna tablica 4 × 4 (macierz), używana ;jako separator wierszy. Ouput jest literą lub jest pusty dla braku tetromino.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe (na wyjściu znajduje się kropka, aby umożliwić identyfikację pustego wyniku).

Wyjaśnienie

Kod buduje 4 obroty wejściowej tablicy 4 × 4 w krokach co 90 stopni. Każda obrócona tablica jest wypełniona 2 zerami w górę i w dół, co przekształca ją w tablicę 8 × 4. 4 tablice są konkatenowane pionowo w macierz 32 × 4. Cztery obrócone tablice w tym skonkatowanym układzie są „izolowane” dzięki wypełnieniu zerami.

Każdy z 7 możliwych wzorów jest testowany pod kątem obecności w tablicy 32 × 4. Do tego celu używana jest pętla. Każdy wzór jest zdefiniowany przez dwie liczby, które wyrażone binarnie dają odpowiednią maskę 0/1. Na przykład liczba 3, 6określenie „S” kształt.

7 zestawów 2 liczb ułożonych jest w macierz 2 × 7, z której pętla będzie kolejno wybierać każdą kolumnę. Macierz jest definiowana przez wypychanie wszystkich liczb na stos, łączenie ich w wektor i przekształcanie w macierz 2-rzędową. Ponieważ kształt „I” jest zdefiniowany przez liczbę 15, a następnie 0, umieszczenie go na końcu pozwala domyślnie wypełnić 0 przez funkcję przekształcania.

Maska jest następnie wypełniana 3 zerami w czterech kierunkach. Jest to konieczne, aby wykryć niepożądane wartości na wejściu.

Aby sprawdzić, czy maska ​​jest obecna w tablicy 32 × 4, ta ostatnia jest przekształcana do postaci bipolarnej (tj. -1/1 zamiast 0/1) i splot z maską. Ponieważ maska ​​ma 4, dopasowanie występuje, jeśli jakiś wpis w wyniku splotu wynosi 4.

Na końcu pętli uzyskano 7 wyników fałsz / prawda, z których co najwyżej jeden jest prawdziwy. Służy do indeksowania do ciągu zawierającego możliwe litery wyjściowe.

Luis Mendo
źródło
3

Galaretka , 53 bajty

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

Wypróbuj online!

Pełny program Bierze 4x4. Drukuje, mjeśli nie jest tetromino, w przeciwnym razie drukuje małe litery.

Erik the Outgolfer
źródło
Czy ... czy przyjmowanie tablic bitów jest legalne?
Pozwoliłoby
@ETHproductions Dane wejściowe można przyjmować jako liczbę całkowitą lub bezpośrednio jako tablicę 2D z 4 cyframi binarnymi 4x4 lub płaską tablicę z 16 cyframi binarnymi.
Erik the Outgolfer,
Huh, słusznie mi
pomijając
1

Perl 5 , 197 + 1 (-p) = 198 bajtów

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".$_)}

Wypróbuj online!

Pobiera 16-bitowy ciąg jako dane wejściowe. Nie wyprowadza nic, jeśli wejście nie jest pojedynczym tetromino.

W jaki sposób?

Dwie substytucje „przenoszą” kształt wejściowy do prawego dolnego rogu. Wynikowy ciąg bitów jest konwertowany na liczbę całkowitą, a następnie sprawdzany w haszu poprawnych liczb całkowitych.

Xcali
źródło
1

APL (Dyalog) , 66 bajtów

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

Wypróbuj online!

Arg jest wektorem logicznym.

Oblicza podpisane odległości kropek do ich środka ciężkości jako liczby zespolone (rzeczywistą i urojoną częścią są ∆x, ∆y) i mnoży liczby zespolone razem. Okazuje się, że jest to wystarczająco dobry niezmiennik, aby odróżnić tetrominoy.

ngn
źródło
Ciekawa metoda.
Arnauld,