Eingang
Die Tafel: Ein 2D-Container (Matrix, Liste der Listen usw.) mit Buchstaben wie:
["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]
Wenn Sie eine Liste von Listen auswählen, können Sie davon ausgehen, dass alle Unterlisten gleich lang sind.
Regeln
- Um ein gültiges Rechteck zu erstellen, benötigen Sie alle Rechteckecken mit demselben Buchstaben.
- Schauen Sie sich beispielsweise die Musterplatte mit X- Balg an. Sie können 'X' an (1,0) auch an (4,0) auch an (1,3) und an (4,3) sehen, dann haben Sie den Bereich [1,0,4,3], der von bedeutet (1,0) bis (4,3):
Musterplatine mit X :
["B", "X", "C", "C", "X", "B", "B", "C", "A", "A"],
["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
["B", "X", "B", "A", "X", "B", "A", "C", "B", "A"],
["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]
- Ziel ist es, das Rechteck oder eines der Rechtecke mit der größten Fläche zu finden, berechnet durch (rechts-links + 1) * (unten-oben + 1)
- Wenn es mehrere Rechtecke mit derselben maximalen Fläche gibt, geben Sie eines aus. Optional die mit (obere Koordinate, linke Koordinate, rechte Koordinate, untere Koordinate) lexikographisch kleinste.
- Rechtecke müssen Kanten parallel zur Brettkante haben.
- Jeder Buchstabe ist ein druckbares ASCII-Zeichen von A bis Z (beide enthalten).
Ausgabe
Die Ausgabe sollte die linke Aufwärts- und die rechte Abwärtsposition der Ecken des Rechtecks mit dem größten Bereich sein. Für das erste Muster "Board" ist das große Quadrat das gelbe:
Und die Antwort sollte lauten:
[1, 1, 8, 4]
Ein zweites Beispiel für einen Testfall
Eine Eingabe von:
["C", "D", "D", "D", "A", "A"],
["B", "D", "C", "D", "A", "A"],
["B", "D", "D", "C", "A", "C"],
["B", "D", "B", "C", "A", "C"]
Sollte eine dieser drei Koordinatenlisten ergeben, die einen Bereich mit sechs Rechtecken identifiziert:
[1, 0, 2, 2]
[1, 0, 3, 1]
[3, 2, 5, 3]
Diese Frage wurde auf Stack Overflow mit dem Titel gestellt: Wie finde ich das größte Rechteck in einem 2D-Array, das aus vier identischen Ecken besteht? und mit dieser unhöflichen JS-Lösung (ich kann "unhöflich" sagen, weil mein Code ist;):
Ok, ist mein erster Beitrag, sei bitte tolerant mit mir. Ich werde alles ändern, was Sie sagen, um das Quiz zu verbessern.
((left,top),(right,bottom))
in Ordnung sein. Ich habe meine Antwort gelöscht und erneut beantwortet, wenn die Frage vollständig verfeinert wurde.Antworten:
Python 2 ,
148130 BytesProbieren Sie es online!
quelle
Retina ,
163162 BytesProbieren Sie es online! Bearbeiten: 1 Byte gespeichert, da die nachfolgende
)
Übereinstimmung$.(
mit implizit ist. Erläuterung:Dieser reguläre Ausdruck entspricht Rechtecken. Die Gruppen lauten wie folgt: 1) Obere Reihe (als Erfassungsanzahl) 2) Linke Spalte (als Länge) 3) Balancieren, um sicherzustellen, dass die linken Ecken ausgerichtet sind 4) Buchstabe für die Ecken 5) Breite + 1 (als Länge) 6) Balancieren um sicherzustellen, dass die rechten Ecken ausgerichtet sind 7) Rechte Spalte (als Länge) 8) nicht verwendet 9) Höhe (als Erfassungsanzahl). Die
w
Option stellt sicher, dass alle möglichen Rechteckbreiten für jede gegebene linke obere Ecke übereinstimmen. In den$
Optionen werden die Ergebnisse unter Verwendung des folgenden Substitutionsmusters aufgelistet.Die Ersetzungen lauten wie folgt: Die rechte Spalte, die obere Zeile, die linke Spalte, die Negation des Bereichs des Rechtecks (buchstäblich berechnet als die Länge der Wiederholung der Zeichenfolge um eins mehr als die Höhe der Anzahl von Malen), die linke Spalte , die obere Zeile, die rechte Spalte, gefolgt von einem Ausdruck, der in die untere Zeile ausgewertet wird (eine Erfassung hätte 12 Byte gekostet, plus mir sind einstellige Variablen ausgegangen). Die ersten vier Erfassungen repräsentieren die Sortierreihenfolge in der Reihenfolge der Priorität. Wenn Retina stabil sortiert, kann eine mehrspaltige Sortierung eingerichtet werden, indem nach jeder Sortierspalte von der niedrigsten zur höchsten Priorität sortiert wird. (Der Bereich muss in absteigender Reihenfolge sortiert sein, damit keine einzelne Zeichenfolgensortierung verwendet werden kann.)
Es werden dann vier numerische Sortierungen durchgeführt.
Die Sortierspalte wird dann nach jeder Sortierung gelöscht.
Der erste Eintrag ist also jetzt das gewünschte Ergebnis.
Hinweis: Die Beschränkung der Rechteckauswahl für einen bestimmten Bereich wurde inzwischen gelockert, und die folgende
144143-Byte-Version bevorzugt ein breiteres Rechteck als ein höheres:Probieren Sie es online!
quelle
Jelly , (27?)
2928 Bytes27 Wenn eine 1-basierte Indizierung zulässig ist, entfernen Sie das nachfolgende Element
’
Ein volles Programm.
Probieren Sie es online! (oder siehe den anderen Testfall )
Wie?
quelle
Perl 6 ,
8373 BytesProbieren Sie es online!
Gibt eine Liste von Listen zurück
((x0 y0) (x1 y1))
.Erläuterung
quelle
Haskell , 144 Bytes
Probieren Sie es online!
quelle
b<=d
, solange Sie behaltena<=c
.Gelee , 24 Bytes
Probieren Sie es online!
⁺
erweist sich als nützlich.Ausgabeformat: [oben, unten], [links, rechts] . 1-Indizierung.
quelle
JavaScript (ES6), 121 Byte
-1 Byte dank @ l4m2
-1 Byte dank @tsh
+2 Byte, um die neue Bewertungsregel für Rechtecke einzuhalten
Nimmt die Eingabe als eine Matrix von Zeichenfolgen. Gibt 0-indizierte Koordinaten zurück: [x0, y0, x1, y1] .
Probieren Sie es online!
quelle
a=>a.map(b=(r,y)=>r.map((v,x)=>a.map((R,Y)=>R.map((V,X)=>V+R[x]+r[X]!=v+v+v|(A=(X-x)*(Y-y))<=b||(o=[x,y,X,Y],b=A)))))&&o
(A=...)<=b
->(A=...)<b
?APL (Dyalog Classic) , 38 Byte
Probieren Sie es online!
quelle
Java 8,
208205 BytesKann definitiv Golf gespielt werden. Ich benutze jetzt den naheliegendsten Ansatz,
vierdrei verschachtelte For-Loops zu verwenden.-3 Bytes dank @ceilingcat, das die inneren Schleifen von Zeilen und Spalten in einer einzigen Schleife kombiniert.
Erläuterung:
Probieren Sie es online aus.
quelle