Größtes Rechteck im 2D-Array

26

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:

Bildbeschreibung hier eingeben

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.

danihp
quelle
7
Hallo, willkommen bei PPCG! Dies scheint eine gute Herausforderung zu sein, aber es scheint, dass es kein Gewinnkriterium gibt. In der Regel sind die Beiträge hier mit [Code-Golf] gekennzeichnet, was bedeutet, dass der kürzeste Code (in Byte) gewinnt.
Conor O'Brien
1
Ich dachte, ich würde Sie wissen lassen, dass wir eine Sandbox haben , in der Sie Feedback zu Fragen erhalten können, bevor sie auf der Hauptseite veröffentlicht werden. Die Sandbox ist praktisch für alle hier, besonders aber für Anfänger, die möglicherweise nicht alle Regeln und Erwartungen kennen, die wir haben.
Weizen-Assistent
2
Einige Antworten geben die Koordinaten in der Sortierreihenfolge für das "erste" Rechteck (dh oben, links, unten, rechts) anstelle von (links, oben, rechts, unten) aus, wie in Ihren Beispielen gezeigt. Ist das ok?
Nimi
2
Weniger strenge Ausgabeformate ermutigen normalerweise zu mehr Antworten, daher sollte auch etwas ((left,top),(right,bottom))in Ordnung sein. Ich habe meine Antwort gelöscht und erneut beantwortet, wenn die Frage vollständig verfeinert wurde.
Angs
1
Klar, wenn Sie eine Antwort akzeptieren wollen, sollte sie insgesamt die kürzeste sein. So mögen die meisten Leute Dinge, die auf der Website gemacht werden. Dies hat jedoch keine Konsequenzen. Es wächst auch die Meinung, dass das Akzeptieren von Antworten der Website abträglich ist. Ich bin dieser Meinung und akzeptiere daher niemals Antworten auf meine Herausforderungen. Was Sie tun, liegt bei Ihnen.
Weizen-Assistent

Antworten:

6

Python 2 , 148 130 Bytes

lambda x,e=enumerate:min(((a-c)*(d-b),b,a,d,c)for a,y in e(x)for c,k in e(x)for b,g in e(y)for d,h in e(y)if g==h==k[b]==k[d])[1:]

Probieren Sie es online!

ovs
quelle
Hallo @ovs, ist es für dich und unpraktisch, wenn ich die Regel ändere, um den Bereich wie folgt darzustellen: (x2-x1 + 1) × (y2-y1 + 1), wie Angs es vorgeschlagen hat?
Danihp
Ich möchte einige Regeln lockern, um mehr Antworten zu ermutigen. Kann ich?
Danihp
@danihp Mach weiter. Das macht meine Antwort nicht ungültig, oder?
OVS
Nein, deine Antwort ist richtig! Nett.
Danihp
5

Retina , 163 162 Bytes

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*
4{N`
)m`^.*?,

0G`

Probieren Sie es online! Bearbeiten: 1 Byte gespeichert, da die nachfolgende )Übereinstimmung $.(mit implizit ist. Erläuterung:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?

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 wOption 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.

$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*

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

4{N`

Es werden dann vier numerische Sortierungen durchgeführt.

)m`^.*?,

Die Sortierspalte wird dann nach jeder Sortierung gelöscht.

0G`

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 144 143-Byte-Version bevorzugt ein breiteres Rechteck als ein höheres:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
-$.($5$#9*$5);$.2,$#1,$.7,$.($#1*_$#9*
N`
0G`
.*;

Probieren Sie es online!

Neil
quelle
Erfüllt die lexikografische Mindestanforderung nicht (probieren Sie den Testfall, den ich zum Beispiel zum OP hinzugefügt habe) (kann die Ausgabe auch in der falschen Reihenfolge erfolgen?) TIO
Jonathan Allan
(... ja, die ersten beiden Werte in der Ausgabe sind falsch herum, denke ich)
Jonathan Allan
Ich habe nur einige Einschränkungen gelockert (Lexikografische Mindestanforderung). Ich hoffe, es ist kein Problem für dich.
Danihp
... dies muss nun mit Linien und Punkten übereinstimmen.
Jonathan Allan
Das Korrigieren der lexikografischen Reihenfolge kostete 20 Bytes :-( und ich bemerkte, dass sich die Flächenberechnung änderte, was weitere 2 Bytes kostete, aber ich weiß nicht, was @ JonathanAllan über Punkte bedeutet.
Neil
4

Jelly , (27?)  29  28 Bytes

27 Wenn eine 1-basierte Indizierung zulässig ist, entfernen Sie das nachfolgende Element

Fṙ1s2;Uœị³EaZI‘P
ZLpLŒċÇÞṪF’

Ein volles Programm.

Probieren Sie es online! (oder siehe den anderen Testfall )

Wie?

Fṙ1s2;Uœị³EaZI‘P - Link 1, areaOrZero: list of pairs [[b,l],[t,r]]
F                - flatten the input                 [b,l,t,r]
 ṙ1              - rotate left one                   [l,t,r,b]
   s2            - split into twos                   [[l,t],[r,b]]
      U          - upend the input                   [[l,b],[r,t]]
     ;           - concatenate                       [[l,t],[r,b],[l,b],[r,t]]
         ³       - program's input
       œị        - multidimensional index into
          E      - all equal?                       X
            Z    - transpose the input              [[b,t],[l,r]]
           a     - logical AND (vectorises)         (if not X we now have [[0,0],[0,0]]
             I   - incremental differences          [t-b,r-l] (or [0,0] if not X)
              ‘  - increment (vectorises)           [t-b+1,r-l+1] (or [1,1] if not X)
               P - product                          area (or 1 if not X)

ZLpLŒċÇÞṪF’ - Main link: list of lists
Z           - transpose the input
 L          - length
   L        - length of the input
  p         - Cartesian product
    Œċ      - pairs with replacement
       Þ    - (stable) sort by:
      Ç     -   last link (1) as a monad
        Ṫ   - tail (note that the rightmost pre-sort represents the bottom-right 1x1
            -       so cannot be superseded by a non-matching rectangle)
         F  - flatten
          ’ - decrement (vectorises) (to get to 0-based indexing)
Jonathan Allan
quelle
4

Perl 6 , 83 73 Bytes

{([X] (^$^a[0]X ^$a)xx 2).max:{[eq] $a[.[*;1];.[*;0]]and[*] 1 X-[Z-] $_}}

Probieren Sie es online!

Gibt eine Liste von Listen zurück ((x0 y0) (x1 y1)).

Erläuterung

{
  ([X]                   # Cross product of corner pairs.
    (^$^a[0]             # Range of x coords.
     X                   # Cross product of coords.
     ^$a                 # Range of y coords.
    )xx 2                # Duplicate list.
  ).max:                 # Find maximum of all ((x0 y0) (x1 y1)) lists
  {                      # using the following filter.
    [eq]                 # All letters equal?
      $a[.[*;1];.[*;0]]  # Multidimensional subscript with y and x coord pairs.
    and                  # Stop if false.
    [*]                  # Multiply
      1 X-[Z-] $_        # for each axis 1 - (c0 - c1) == c1 - c0 + 1.
  }
}
nwellnhof
quelle
3

Haskell , 144 Bytes

import Data.Array
o=assocs
f r=snd$maximum[((c-a+1)*(d-b+1),[a,b,c,d])|((a,b),x)<-o r,((c,d),y)<-o r,x==y,r!(a,d)==r!(c,b),x==r!(a,d),a<=c,b<=d]

Probieren Sie es online!

Angs
quelle
Sie können entfernen b<=d, solange Sie behalten a<=c.
Weizen-Assistent
@ovs eigentlich, die entweder nicht funktionieren (siehe das Beispiel, das ich TIO hinzugefügt )
Jonathan Allan
@nimi: Ich könnte argumentieren, dass es nur darum geht, die Eingabe zu transponieren.
Angs
Für mich ist das in Ordnung. Sie können den Eingang transponieren.
Danihp
3

Gelee , 24 Bytes

XLṭLp`€p/⁺œị€EɗÐfI‘PɗÞ0Ṫ

Probieren Sie es online!

erweist sich als nützlich.

Ausgabeformat: [oben, unten], [links, rechts] . 1-Indizierung.

user202729
quelle
3

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] .

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

Probieren Sie es online!

Arnauld
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
14 m²,
Wenn es mehrere Rechtecke mit derselben maximalen Fläche gibt, geben Sie eines aus . vielleicht (A=...)<=b-> (A=...)<b?
tsh
@tsh Das ist jetzt in der Tat sicher. Vielen Dank!
Arnauld
1

Java 8, 208 205 Bytes

m->{int r=0,R[]={},i=m.length,j,y,z,u,t,T;for(;i-->0;)for(j=m[i].length;j-->0;)for(y=i*j;y-->0;)if((T=m[i][j])==m[u=y/j][z=y%j]&T==m[i][z]&T==m[u][j]&r<(t=(i-u)*(j-z))){r=t;R=new int[]{z,u,j,i};}return R;}

Kann definitiv Golf gespielt werden. Ich benutze jetzt den naheliegendsten Ansatz, vier drei 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.

m->{                         // Method with char-matrix parameter and int-array return-type
  int r=0,                   //  Largest area found, starting at 0
      R[]={},                //  Result coordinates, starting empty
      i=m.length,j,          //  x,y indices of the first corner
      y,z,                   //  x,y indices of the second corner
      u,t,T;                 //  Temp integers to reduce bytes
  for(;i-->0;)               //  Loop `i` over the rows
    for(j=m[i].length;j-->0;)//   Inner loop `j` over the columns
      for(y=i*j;y-->0;)      //    Inner loop over the rows and columns
        if((T=m[i][j])==m[u=y/j][z=y%j]
                             //      If the values at coordinates [i,j] and [y,z] are equal
           &T==m[i][z]       //      as well as the values at [i,j] and [i,z]
           &T==m[u][j]       //      as well as the values at [i,j] and [y,j]
           &r<(t=(i-u)*(j-z))){
                             //      And the current area is larger than the largest
          r=t;               //       Set `r` to this new largest area
          R=new int[]{z,u,j,i};}
                             //       And save the coordinates in `R`
  return R;}                 //  Return the largest rectangle coordinates `R`
Kevin Cruijssen
quelle