Wkład

Tablica: Kontener 2D (matryca, lista list itp.) Z literami takimi jak:

  ["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"]

Jeśli wybierzesz listę list, możesz założyć, że wszystkie listy podrzędne są tej samej długości.

Zasady

• Aby utworzyć prawidłowy prostokąt, potrzebujesz wszystkich rogów prostokąta z tą samą „literą”.
• Przykład, spójrz na przykładową tablicę z X poniżej. Możesz zobaczyć „X” na (1,0) również na (4,0) również na (1,3) i na (4,3), wtedy masz prostokąt [1,0,4,3], co oznacza, że ​​z (1,0) do (4,3):

Przykładowa tablica z 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"]

• Celem jest znalezienie prostokąta lub jednego z prostokątów o największej powierzchni obliczonej przez (prawo-lewo + 1) * (dół-góra + 1)
• Jeśli istnieje wiele prostokątów o tym samym maksymalnym obszarze, wyślij dowolny. Opcjonalnie ten z leksykograficznie najmniejszą (współrzędną górną, lewą współrzędną, prawą współrzędną, współrzędną dolną).
• Prostokąty muszą mieć krawędzie równoległe do krawędzi planszy.
• Każda litera jest drukowalnym znakiem ASCII od A do Z (oba w zestawie).

Wydajność

Dane wyjściowe powinny być pozycjami w lewo iw prawo w rogach największego obszaru prostokątnego. Dla pierwszej przykładowej „planszy” duży kwadrat jest żółty:

Odpowiedź powinna brzmieć:

[1, 1, 8, 4]

Drugi przykładowy przypadek testowy

Dane wejściowe:

["C", "D", "D", "D", "A", "A"],
["B", "D", "C", "D", "A", "A"],
["B", "D", "D", "C", "A", "C"],
["B", "D", "B", "C", "A", "C"]

Powinien dać jedną z tych trzech list współrzędnych identyfikujących obszar sześciu prostokątów:

[1, 0, 2, 2]
[1, 0, 3, 1]
[3, 2, 5, 3]

To pytanie jest zamieszczone na stronie Przepełnienie stosu z tytułem: Jak znaleźć największy prostokąt w tablicy 2D utworzonej z czterech identycznych narożników? i z tym niegrzecznym rozwiązaniem JS (mogę powiedzieć „niegrzeczny”, ponieważ to mój kod;):

Ok, to mój pierwszy post, bądź dla mnie tolerancyjny. Zmienię wszystko, co powiesz, aby poprawić quiz.

Python 2 , 148 130 bajtów

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

Wypróbuj online!

Siatkówka , 163 162 bajty

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

0G`

Wypróbuj online! Edycja: Zapisano 1 bajt, ponieważ końcowe )dopasowanie do $.(niejawnego. Wyjaśnienie:

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

To wyrażenie regularne pasuje do prostokątów. Grupy są następujące: 1) Górny rząd (jako liczba przechwytywania) 2) Lewa kolumna (jako długość) 3) Równoważenie w celu zapewnienia wyrównania lewych narożników 4) Litera dla narożników 5) Szerokość + 1 (jako długość) 6) Równoważenie aby zapewnić wyrównanie prawych narożników 7) Prawa kolumna (jako długość) 8) nieużywana 9) Wysokość (jako liczba przechwytywania). Ta wopcja zapewnia dopasowanie wszystkich możliwych szerokości prostokątów do każdego lewego górnego rogu. Do $listy Opcje te wyniki, stosując następujący wzór zastąpienia.

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

Podstawienia są następujące: prawa kolumna, górny rząd, lewa kolumna, negacja obszaru prostokąta (dosłownie obliczona jako długość powtórzenia ciągu szerokości jeden raz więcej niż wysokość razy), lewa kolumna , górny wiersz, prawa kolumna, a następnie wyrażenie, które zwraca wartość do dolnego wiersza (przechwytywanie kosztowałoby 12 bajtów plus zabrakło jednocyfrowych zmiennych). Pierwsze cztery przechwytywania reprezentują porządek sortowania w kolejności pierwszeństwa. Gdy Retina sortuje stabilnie, można ustalić sortowanie wielokolumnowe, sortując kolejno każdą kolumnę sortowania od najmniejszego do największego priorytetu. (Obszar musi być posortowany w kolejności malejącej, więc nie można użyć sortowania według pojedynczego łańcucha).

4{N`

Następnie wykonuje się cztery sortowania numeryczne.

)m`^.*?,

Kolumna sortowania jest następnie usuwana po każdym sortowaniu.

0G`

Pierwszy wpis jest zatem pożądanym rezultatem.

Uwaga: Ograniczenie wyboru prostokąta dla danego obszaru zostało odtąd złagodzone, a następująca 144 143-bajtowa wersja preferuje szerszy niż wyższy prostokąt:

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

Wypróbuj online!

Galaretka , (27?)  29  28 bajtów

^{27 jeśli indeksowanie na podstawie 1 jest dozwolone - usuń końcowe ’}

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

Pełny program.

Wypróbuj online! (lub zobacz inny przypadek testowy )

W jaki sposób?

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)

Perl 6 , 83 73 bajty

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

Wypróbuj online!

Zwraca listę list ((x0 y0) (x1 y1)).

Wyjaśnienie

{
  ([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.
  }
}

Haskell , 144 bajty

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]

Wypróbuj online!

Galaretka , 24 bajty

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

Wypróbuj online!

⁺ okazuje się przydatny.

Format wyjściowy: [góra, dół], [lewo, prawo] . 1-indeksowanie.

JavaScript (ES6), 121 bajtów

-1 bajt dzięki @ l4m2
-1 bajt dzięki @tsh
+2 bajty, aby zachować zgodność z nową regułą punktacji prostokąta

Pobiera dane wejściowe jako macierz ciągów znaków. Zwraca współrzędne 0-indeksowane: [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

Wypróbuj online!

APL (Dyalog Classic) , 38 bajtów

a⊃⍨⊃⍒×/1+-/↑2 2∘⍴¨a←⍸≢¨↑∘.(∩¨)⍨∘.∩¨⍨↓⎕

Wypróbuj online!

Java 8, 208 205 bajtów

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;}

Zdecydowanie można grać w golfa .. Teraz używam najbardziej oczywistego podejścia, używając czterech trzech zagnieżdżonych pętli for.

-3 bajty dzięki @ceilingcat łącząc wewnętrzne pętle wierszy i kolumn w jedną pętlę.

Wyjaśnienie:

Wypróbuj online.

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`