Entrada

El tablero: un contenedor 2D (matriz, lista de listas, etc.) de letras como:

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

Si elige una lista de listas, puede suponer que todas las sublistas tienen la misma longitud.

Reglas

• Para hacer un rectángulo válido, necesita todas las esquinas del rectángulo con la misma 'letra'.
• Ejemplo, mire el tablero de muestra con X debajo. Puede ver 'X' en (1,0) también en (4,0) también en (1,3) y en (4,3), entonces tiene el rectángulo [1,0,4,3] que significa (1,0) a (4,3):

Tablero de muestra con 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"]

• El objetivo es encontrar el rectángulo o uno de los rectángulos con el área más grande, calculado por (derecha-izquierda + 1) * (abajo-arriba + 1)
• Si hay varios rectángulos con la misma área máxima, imprima cualquiera. Opcionalmente el que tiene (coordenada superior, coordenada izquierda, coordenada derecha, coordenada inferior) lexicográficamente más pequeño.
• Los rectángulos deben tener bordes paralelos al borde del tablero.
• Cada letra es un carácter ASCII imprimible de la A a la Z (ambos incluidos).

Salida

La salida debe ser las posiciones izquierda y derecha de las esquinas rectangulares de mayor área. Para el primer "tablero" de muestra, el cuadrado grande es el amarillo:

Y la respuesta debería ser:

[1, 1, 8, 4]

Un segundo caso de prueba de ejemplo

Una entrada de:

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

Debería producir una de estas tres listas de coordenadas que identifiquen un área de seis rectángulos:

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

Esta pregunta se publica en Stack Overflow con título: ¿Cómo encontrar el rectángulo más grande en una matriz 2D formada por cuatro esquinas idénticas? y con esta solución grosera de JS (puedo decir "grosero" porque es mi código;):

Ok, es mi primer post, sé tolerante conmigo por favor. Cambiaré todo lo que digas para mejorar el cuestionario.

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

Pruébalo en línea!

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`

Pruébalo en línea! Editar: se guardó 1 byte porque la )coincidencia final $.(es implícita. Explicación:

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

Esta expresión regular coincide con rectángulos. Los grupos son los siguientes: 1) Fila superior (como recuento de captura) 2) Columna izquierda (como longitud) 3) Equilibrio para garantizar que las esquinas izquierdas se alineen 4) Letra para las esquinas 5) Ancho + 1 (como longitud) 6) Equilibrio para garantizar que las esquinas correctas se alineen 7) Columna derecha (como longitud) 8) sin usar 9) Altura (como recuento de captura). La wopción garantiza que todos los anchos posibles de los rectángulos coincidan para cada esquina superior izquierda dada. Las $opciones enumeran los resultados utilizando el siguiente patrón de sustitución.

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

Las sustituciones son las siguientes: la columna derecha, la fila superior, la columna izquierda, la negación del área del rectángulo (literalmente calculada como la longitud de repetir la cadena de ancho por una más que el número de altura), la columna izquierda , la fila superior, la columna derecha, seguida de una expresión que se evalúa como la fila inferior (una captura habría costado 12 bytes y me he quedado sin variables de un solo dígito). Las primeras cuatro capturas representan el orden de clasificación en orden de prioridad. Como Retina clasifica de manera estable, se puede establecer una clasificación de varias columnas clasificando por cada columna de clasificación de menor a mayor prioridad. (El área se debe ordenar en orden descendente, por lo que no se puede usar una sola cadena).

4{N`

Luego se realizan cuatro clasificaciones numéricas.

)m`^.*?,

La columna de clasificación se elimina luego de cada clasificación.

0G`

Por lo tanto, la primera entrada es ahora el resultado deseado.

Nota: La restricción en la elección del rectángulo de un área dada se ha relajado y la siguiente versión de 144 143 bytes prefiere un rectángulo más ancho que uno más alto:

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

Pruébalo en línea!

Jalea , (27?)  29  28 bytes

^{27 si se permite la indexación basada en 1 - eliminar el final ’}

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

Un programa completo

Pruébalo en línea! (o vea el otro caso de prueba )

¿Cómo?

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 bytes

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

Pruébalo en línea!

Devuelve una lista de listas ((x0 y0) (x1 y1)).

Explicación

{
  ([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 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]

Pruébalo en línea!

Jalea , 24 bytes

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

Pruébalo en línea!

⁺ Demuestra ser útil.

Formato de salida: [arriba, abajo], [izquierda, derecha] . 1-indexación.

JavaScript (ES6), 121 bytes

-1 byte gracias a @ l4m2
-1 byte gracias a @tsh
+2 bytes para cumplir con la nueva regla de puntuación rectangular

Toma la entrada como una matriz de cadenas. Devuelve coordenadas indexadas 0: [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

Pruébalo en línea!

APL (Dyalog Classic) , 38 bytes

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

Pruébalo en línea!

Java 8, 208205 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;}

Definitivamente se puede jugar al golf. Ahora uso el enfoque más obvio de usar cuatro tres bucles for anidados.

-3 bytes gracias a @ceilingcat combina los bucles internos de filas y columnas en un solo bucle.

Explicación:

Pruébalo en línea.

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`