Welcher Tetromino ist das?

54

Bei einer vorzeichenlosen 16-Bit-Ganzzahl N müssen Sie feststellen, ob ihre in einer 4x4-Matrix abgebildete Binärdarstellung mit einer Tetrominoform übereinstimmt , und wenn ja, welche Form es ist.

Matrix

Jedes Bit von N wird in einer 4x4-Matrix von links nach rechts und von oben nach unten abgebildet, beginnend mit dem höchstwertigen.

Beispiel :

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

Tetromino-Formen

Grundformen

Es gibt 7 Tetrominoformen, die mit den Buchstaben O , I , S , Z , L , J und T gekennzeichnet sind :

Tetrominos

Rotationen und Übersetzungen

Wenn eine Form innerhalb der 4x4-Matrix verschoben und / oder gedreht wird, wird sie weiterhin als gültige Variation desselben Tetrominos betrachtet. Zum Beispiel sollten 17600, 1136, 2272 und 1604 alle als J- Tetrominos identifiziert werden :

gültige J-Beispiele

Wickeln Sie nicht!

Die Formen können jedoch nicht über die Grenzen der Matrix hinaus gewickelt oder verschoben werden. Zum Beispiel sollten weder 568 noch 688 als J- Tetrominoe identifiziert werden (geschweige denn irgendeine andere Form):

ungültige J-Beispiele

Erläuterungen und Regeln

  • Sie können Eingaben als Ganzzahl oder direkt als 16 Binärziffern in einem beliebigen vernünftigen Format, z. B. einem 2D-Array, einem flachen Array oder einer durch Trennzeichen getrennten Zeichenfolge, annehmen.
  • Bei der Eingabe handelt es sich garantiert um eine 16-Bit-Ganzzahl ohne Vorzeichen (oder die entsprechende Darstellung als Array oder Zeichenfolge).
  • Wenn eine gültige Form identifiziert wurde, müssen Sie den Buchstaben , der die Form identifiziert, entweder in Groß- oder Kleinbuchstaben drucken oder zurückgeben .
  • Wenn keine Form identifiziert wird, müssen Sie einen Wert drucken oder zurückgeben, der keinem Tetromino-Buchstaben entspricht. Sie können sich auch dafür entscheiden, überhaupt nichts zurückzugeben.
  • Um als gültig zu gelten, muss die Matrix die genaue Tetrominoform ohne zusätzliche Zellen enthalten (siehe 1911 und 34953 in den Testfällen).
  • Das ist , also gewinnt die kürzeste Antwort in Bytes!

Testfälle

Sie können diesem Link folgen , um die Testfälle als 2D-Arrays abzurufen.

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
quelle
Interessanterweise habe ich func1 . func2 . func3
neulich
Kann ich Eingaben als die vier mit verbundenen Zeilen nehmen 0, also 1111011110111101111für 65535?
ETHproductions
@ETHproductions Das scheint in Ordnung zu sein. Ich habe die Herausforderung mit einem etwas entspannten Eingabeformat bearbeitet.
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
Ingenieur Toast
^ Wird mit Lynns Python 3-Antwort generiert, da es über praktische Eingabe- / Ausgabeformate verfügt.
Ingenieur Toast

Antworten:

6

Jelly ,  54 43 42  41 Bytes

-1 Byte dank Erik the Outgolfer (Transponieren innerhalb der wiederholten Kette)

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

Ein monadischer Link, der ein 2D-Array von Ganzzahlen ( 1s und 0s) oiszljtaufnimmt und einen Kleinbuchstaben für das jeweilige Tetromino zurückgibt oder wungültig ist.

Probieren Sie es online! oder sehen Sie sich die Testsuite an .

Sehen Sie sich auch dieses Programm an, das alle 1820 möglichen 2D-Binär-Arrays mit genau vier gesetzten Bits zusammen mit ihren Ausgängen auflistet, sortiert nach diesen Ausgängen.

Wie?

Dies dauert zunächst alle vier Umdrehungen der Eingabe. Dann verschiebt es die gesetzten Bits von jedem so weit wie möglich nach rechts und dann so weit wie möglich nach unten und wandelt die Ergebnisse in Binärzahlen um. Anschließend wird das minimale Ergebnis in einer Liste der minimalen derartigen Darstellungen jedes gültigen Tetrominos nachgeschlagen und das dekrementierte Ergebnis verwendet, um in die beiden verketteten Wörter des Wörterbuchs zoist+ zu indexieren jowl, was ergibt, wwenn keine Übereinstimmung gefunden wurde.

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

Vorherige Methode (54 Byte)

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

Ein monadischer Link, der ein 2D-Array von Ganzzahlen ( 1s und 0s) oiszljtaufnimmt und einen Kleinbuchstaben für das jeweilige Tetromino zurückgibt oder wungültig ist.

Probieren Sie es online!

Dadurch wird überprüft, ob mindestens drei leere Zeilen (Zeilen + Spalten) vorhanden sind und bestimmte Bitmuster in keiner Zeile vorhanden sind (insbesondere die Zahlen 5, 9, 10, 11 und 13). Diese stellen zusammen sicher, dass der nächste Schritt nicht ergibt Fehlalarm. Anschließend wird die Binärzahl (durch Entfernen von nachgestellten Nullen vor der Konvertierung) für jede der vier Umdrehungen abgeflacht und auf der Grundlage des dekrementierten Ergebnisses durch Indexierung in die beiden verketteten Wörterbuchwörter verschoben zoist+ jowl, was ergibt, wwenn keine Übereinstimmung gefunden wurde.

Jonathan Allan
quelle
Und ich wusste, dass es einen besseren Weg gibt als Hardcoding ...
Erik the Outgolfer
Übrigens denke ich, dass dieser Code von einem Zufall abhängt (weil er zoistjowlsonst normalerweise nicht für eine Zeichenfolge passt: p)
Erik the Outgolfer
Was meinst du mit "hängt von einem Zufall ab"? (Die Wörterbuchsuche speichert ...Ṁị“LZOISTJWsowieso nur ein Byte )
Jonathan Allan
Hmm ... ja, ich wusste, das würde nicht lange dauern ... Übrigens, ich glaube, du hast mein gestohlen ZU$3С: p
Erik the Outgolfer 10.08.17
Ich habe gestern versucht, dieselbe Methode anzuwenden, nachdem ich die vorherige eingereicht hatte, aber ich glaube, ich war ein bisschen müde.
Jonathan Allan
28

Python 3 , 124 Bytes

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]

Probieren Sie es online!

Erwartet eine Ganzzahl n, die eine 4 × 4- Binärmatrix darstellt. Wirft, wenn kein Tetromino gefunden wird.

Zeile 2 verschiebt die Form nach rechts, bis sich eine 1 in der äußersten rechten Spalte befindet. (4369 ist 0001 0001 0001 0001binär.) Zeile 3 senkt die Form, bis sich eine 1 in der unteren Reihe befindet. Zusammen ergibt dies zB:

    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

Dann suchen wir den Index von nin dieser Liste:

 [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

Jede Spalte von Indizes, die dem Modulo 7 äquivalent sind, entspricht einer Tetrominoform. 64 ( @) wird als Auffüllwert verwendet, da nan dieser Stelle im Code nicht 64 angegeben werden kann.

NB. Anstelle von wird eine Ausnahme für die Eingabe 0durch Computing ausgelöst .n/n1

Lynn
quelle
Warum funktioniert Ihre Binärzeichenfolge? Ich hatte Probleme damit in Python 3, siehe Kommentare codegolf.stackexchange.com/a/85201/53667
Karl Napf
Python verwendet UTF-8 als Standardkodierung für den Quellcode und für die Textausgabe. PPM-Dateien werden in UTF-8 jedoch nicht gelesen . Wenn Sie laufen print("ÿ"), dass die Bytes geschrieben werden sind c3 bf 0a, nicht ff 0a, und die PPM Bild verwandelt sich in Müll.
Lynn
8

APL (Dyalog) , 95 94 93 89 87 Bytes

-2 Dank an Zacharý

Benötigt, ⎕IO←0was auf vielen Systemen Standard ist. Nimmt eine Boolesche Matrix (beliebiger Form!) Als Argument. Gibt nichts zurück, wenn die angegebene Anzahl von Bits nicht vier ist, und eine leere Zeile, wenn die vier angegebenen Bits kein Tetromino bilden.

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

Probieren Sie es online!

Erstellt alle vier Umdrehungen der Eingabe und sucht dann in jeder Umdrehung nach jedem Tetromino.

{} Anonyme Funktion, bei der das Argument dargestellt wird durch :

,⍵ das Argument durchkreuzen

+/ summiere es

4= ist vier gleich das?

: Wenn ja, dann (sonst nichts zurück):

  ⍳4 ersten vier ɩ ndices; [0,1,2,3]

  ⍵∘{ Wenden auf jede die folgende Funktion an und verwenden die Eingabe als Argument mit fester linker Maustaste

    das linke Argument, dh die Eingabe

   ⊢⍺ ergibt das (trennt sich von )

   ⌽∘⍉⍣⍵ Spiegel und transponieren (dh um 90 °) mal

  ()∘.⍷ Äußeres "Produkt", jedoch mit Suchen * der folgenden Liste und der Rotationen:

   3↑1 Nimm drei Elemente von einem und fülle sie mit Nullen auf. [1,0,0]

   K← Speichern Sie das als K

    Tabelle (in Spaltenvektor umwandeln); [[1],[0],[0]]

   1, ein eins voranstellen; [[1,1],[1,0],[1,0]]("J")

   J← speichern als J

   ()⊖¨⊂ Das gesamte J vertikal drehen, jeweils mit der folgenden Anzahl von Schritten:

    ⍳3 ersten drei ɩ ntegers;[0,1,2]

   wir haben [[[1,1],[1,0],[1,0]],[[1,0],[1,0],[1,1]],[[1,0],[1,1],[1,0]]]("J", "L," T ")

   (), Der folgenden Liste voranstellen:

    2⊖J Drehe Jzwei Schritte vertikal. [[1,0],[1,1],[1,0]]("T")

    K⌽ Drehen Sie die Zeilen um jeweils 1, 0 und 0 Schritte. [[0,1],[1,1],[1,0]]("Z")

    0 1⌽¨⊂ drehen Sie das gesamte Array vertikal, nicht einmal und nicht einmal; [[[0,1],[1,1],[1,0]],[[1,0],[1,1],[0,1]]] ("Z", "S")

    (), Der folgenden Liste voranstellen:

     (2 2)4⍴¨1 eine Eins in eine 2 × 2-Matrix und eine 4-Elemente-Liste umformen; [[[1,1],[1,1]],[1,1,1,1]]("O", "I")

  1∊¨ Ist einer für jeden ein Mitglied?

  ∨/ horizontale ODER-Reduktion (dh über Rotationen; ein Boolescher Wert für jede Form)

  'OIZSLJT'/⍨ Verwenden Sie dies, um die Zeichenfolge zu filtern

* Find gibt ein boolesches Array mit derselben Form wie das rechte Argument zurück, wobei diejenigen die linke obere Ecke aller Subarrays angeben, die mit dem linken Argument identisch sind.

Adam
quelle
Würde das funktionieren? {4=+/,⍵:'OIZSJLT'/⍨∨/1∊¨(((2 2)4⍴¨1),(0 1⌽¨⊂K⌽2⊖J),(⍳3)⊖¨⊂J←1,⍪K←3↑1)∘.⍷⍵∘{⌽∘⍉⍣⍵⊢⍺}¨⍳4}
Zacharý
@ Zacharý Ja, danke, fertig.
Adám,
7

JavaScript (ES6), 242 212 172 164 Bytes

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

Sollte nur sein, um den Ball ins Rollen zu bringen, aber ich bin ein bisschen spät dran ¯ \ _ (ツ) _ / ¯

Nimmt eine Folge von Bits, wobei die Zeilen durch 0s ( '0001000110001000000'stellvertretend für 0001 0011 0010 0000) getrennt sind, und gibt ein Array zurück, das das Zeichen enthält, das das Tetromino darstellt, oder ein Array, das nichts enthält.

Dies funktioniert, indem bei jeder Drehung von Tetromino überprüft wird, ob die Eingabe an einem beliebigen Punkt das Tetromino enthält, das auf beiden Seiten vollständig von Nullen umgeben ist. Jedes Tetromino wird durch eine oder mehrere Binärzahlen dargestellt:

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

Um zu überprüfen, ob die Eingabe ein S-Tetromino enthält, prüfen wir einfach, ob es die binäre Darstellung von entweder 51oder enthält 2145, wobei sich nur 0s auf beiden Seiten befindet.

Einige der Tetrominos haben 4 Ausrichtungen. Wenn Sie sich die binären Darstellungen von diesen ansehen, hat jede 2 Darstellungen, die einfach der Spiegel der anderen beiden sind. Um Platz zu sparen, wird die Binärdarstellung gleichzeitig mit der rekursiven CFunktion vorwärts und rückwärts aufgebaut , sodass wir nur zwei der Ausrichtungen einfügen und die anderen beiden implizieren können.


Alternativer Ansatz mit Zeichencodes:

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
quelle
3

Netzhaut , 125 Bytes

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

Probieren Sie es online! Der Link enthält Testfälle und einen Header zum Konvertieren von Ganzzahlen in eine 4 × 4-Matrix. Erläuterung:

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

Löschen Sie die Eingabe, wenn sie 5 1s enthält .

{s`.*1111.*
I

Überprüfen Sie alle Umdrehungen des Eingangs (siehe unten). Wenn die Eingabe vier aufeinanderfolgende 1s enthält , ist dies eine I.

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

Wenn es drei aufeinanderfolgende 1s plus a 1in der nächsten Zeile unter einem der drei Zeichen enthält, ordnen Sie die Anzahl der Zwischenzeichen dem entsprechenden Ergebnisbuchstaben zu.

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

Ähnliches gilt für zwei benachbarte 1s neben zwei benachbarten 1s in der nächsten Zeile.

T`2-90`S\OZ4-9

Aber auch die Anzahl der Umdrehungen mit den ansonsten nicht verwendeten 0s zählen.

s`.*4.*

Und aufgeben, wenn zu viele Umdrehungen durchgeführt wurden.

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

Transponieren und kehren Sie das Array um und drehen Sie es so.

Neil
quelle
3

MATL , 60 Bytes

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

Die Eingabe ist ein binäres 4 × 4-Array (Matrix), das ;als Zeilentrennzeichen verwendet wird. Ouput ist ein Buchstabe oder leer für kein Tetromino.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle (an die Ausgabe ist ein Punkt angehängt, um ein leeres Ergebnis zu identifizieren).

Erläuterung

Der Code erstellt 4 Umdrehungen des 4 × 4-Eingabearrays in Schritten von 90 Grad. Jedes gedrehte Array wird mit 2 Nullen nach oben und unten aufgefüllt, wodurch es in ein 8 × 4-Array umgewandelt wird. Die 4 Arrays sind vertikal zu einem 32 × 4-Array verkettet. Die vier gedrehten Arrays innerhalb dieses verketteten Arrays sind dank der Null-Auffüllung "isoliert".

Jedes der 7 möglichen Muster wird getestet, um festzustellen, ob es im 32 × 4-Array vorhanden ist. Hierfür wird eine Schleife verwendet. Jedes Muster wird durch zwei Zahlen definiert, die in Binärform die entsprechende 0/1-Maske ergeben. Zum Beispiel, Zahlen 3, 6definieren Sie die "S" -Form.

Die 7 Sätze von 2 Zahlen sind in einer 2 × 7-Matrix angeordnet, aus der die Schleife nacheinander jede Spalte auswählt. Die Matrix wird definiert, indem alle Zahlen auf den Stapel verschoben, zu einem Vektor verknüpft und in eine 2-Zeilen-Matrix umgewandelt werden. Da die "I" -Form durch die Zahl 15 gefolgt von der Zahl 0 definiert ist, kann die 0 durch die Umformungsfunktion implizit gefüllt werden, wenn sie am Ende steht.

Die Maske wird dann mit 3 Nullen in den vier Richtungen aufgefüllt. Dies ist notwendig, um unerwünschte Werte in der Eingabe zu erkennen.

Um zu sehen, ob die Maske im 32 × 4-Array vorhanden ist, wird das letztere in eine bipolare Form (dh -1/1 anstelle von 0/1) transformiert und mit der Maske gefaltet. Da die Maske 4 Einsen hat, erfolgt eine Übereinstimmung, wenn ein Eintrag im Faltungsergebnis 4 entspricht.

Am Ende der Schleife wurden 7 falsche / wahre Ergebnisse erhalten, von denen höchstens eines wahr ist. Dies wird verwendet, um einen String zu indizieren, der die möglichen Ausgabebuchstaben enthält.

Luis Mendo
quelle
3

Jelly , 53 Bytes

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

Probieren Sie es online!

Volles Programm. Nimmt einen 4x4. Druckt, mwenn kein Tetromino, ansonsten Kleinbuchstaben.

Erik der Outgolfer
quelle
Ist ... eine Reihe von Bit-Arrays zulässig? Das würde mir 40 Bytes
ersparen
@ETHproductions Sie können Eingaben als Ganzzahl oder direkt als 2D-Array mit 4x4-Binärziffern oder als flaches Array mit 16 Binärziffern vornehmen.
Erik der Outgolfer
Huh, es
tut
1

Perl 5 , 197 + 1 (-p) = 198 Bytes

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

Probieren Sie es online!

Nimmt eine 16-Bit-Zeichenfolge als Eingabe. Gibt nichts aus, wenn der Eingang kein einzelner Tetromino ist.

Wie?

Die beiden Ersetzungen "verschieben" die Eingabeform in die untere rechte Ecke. Die resultierende Bitfolge wird in eine Ganzzahl konvertiert und dann in einem Hash von gültigen Ganzzahlen überprüft.

Xcali
quelle
1

APL (Dyalog) , 66 Bytes

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

Probieren Sie es online!

Das Argument ist ein Boolescher Vektor.

Berechnet die vorzeichenbehafteten Abstände der Punkte zu ihrem Schwerpunkt als komplexe Zahlen (Real- und Imaginärteil sind ∆x, ∆y) und multipliziert die komplexen Zahlen miteinander. Dies stellt sich als ausreichend invariant heraus, um zwischen den Tetrominos zu unterscheiden.

ngn
quelle
Interessante Methode.
Arnauld