Contribution

Le plateau: Un conteneur 2D (matrice, liste de listes, etc.) de lettres comme:

  ["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 vous choisissez une liste de listes, vous pouvez supposer que toutes les sous-listes sont de la même longueur.

Règles

• Pour faire un rectangle valide, vous avez besoin de tous les coins de rectangle avec la même «lettre».
• Exemple, regardez l' exemple de carte avec X ci-dessous. Vous pouvez voir 'X' sur (1,0) également sur (4,0) également sur (1,3) et sur (4,3) puis vous avez le rectange [1,0,4,3] qui signifie de (1,0) à (4,3):

Exemple de carte avec 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"]

• Le but est de trouver le rectangle ou l'un des rectangles avec la plus grande surface, calculé par (droite-gauche + 1) * (bas-haut + 1)
• S'il existe plusieurs rectangles avec la même zone maximale, sortez-en un. Facultativement celui avec (coordonnée supérieure, coordonnée gauche, coordonnée droite, coordonnée inférieure) lexicographiquement le plus petit.
• Les rectangles doivent avoir des bords parallèles au bord de la planche.
• Chaque lettre est un caractère ASCII imprimable de A à Z (tous deux inclus).

Sortie

La sortie doit être les positions gauche-haut et droite-bas des coins rectangulaires de la plus grande surface. Pour le premier échantillon "board", le grand carré est le jaune:

Et la réponse devrait être:

[1, 1, 8, 4]

Un deuxième exemple de cas de test

Une entrée 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"]

Devrait produire l'une de ces trois listes de coordonnées identifiant une zone de six rectangles:

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

Cette question est publiée sur Stack Overflow avec le titre: Comment trouver le plus grand rectangle dans un tableau 2D formé de quatre coins identiques? et avec cette solution JS grossière (je peux dire "grossier" car c'est mon code;):

Ok, c'est mon premier post, soyez tolérant avec moi s'il vous plait. Je vais changer tout ce que vous dites pour améliorer le quiz.

Python 2 , 148 130 octets

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

Essayez-le en ligne!

Rétine , 163 162 octets

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

0G`

Essayez-le en ligne! Edit: enregistré 1 octet car la fin )correspondant à la $.(est implicite. Explication:

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

Cette expression régulière correspond aux rectangles. Les groupes sont les suivants: 1) Ligne du haut (comme nombre de captures) 2) Colonne de gauche (comme longueur) 3) Équilibrage pour assurer l'alignement des coins gauches 4) Lettre pour les coins 5) Largeur + 1 (comme longueur) 6) Équilibrage pour assurer l'alignement des coins droits 7) Colonne droite (en longueur) 8) inutilisée 9) Hauteur (en nombre de captures). L' woption garantit que toutes les largeurs possibles de rectangles correspondent à chaque coin supérieur gauche donné. Les $options répertorient les résultats en utilisant le modèle de substitution suivant.

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

Les substitutions sont les suivantes: la colonne de droite, la ligne du haut, la colonne de gauche, la négation de la zone du rectangle (calculée littéralement comme la longueur de la répétition de la chaîne de largeur par un de plus que la hauteur nombre de fois), la colonne de gauche , la ligne du haut, la colonne de droite, suivie d'une expression qui évalue la ligne du bas (une capture aurait coûté 12 octets et je n'ai plus de variables à un chiffre). Les quatre premières captures représentent l'ordre de tri par ordre de priorité. Comme Retina trie de manière stable, un tri multicolonne peut être établi en triant par chaque colonne de tri à tour de rôle de la priorité la plus faible à la plus élevée. (La zone doit être triée par ordre décroissant, de sorte qu'un seul tri de chaîne ne peut pas être utilisé.)

4{N`

Quatre tris numériques sont ensuite effectués.

)m`^.*?,

La colonne de tri est ensuite supprimée après chaque tri.

0G`

La première entrée est donc maintenant le résultat souhaité.

Remarque: La restriction sur le choix du rectangle d'une zone donnée a depuis été assouplie et la version 144 144 octets suivante préfère un rectangle plus large que plus grand:

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

Essayez-le en ligne!

Gelée , (27?)  29  28 octets

^{27 si l'indexation basée sur 1 est autorisée - supprimer la fin ’}

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

Un programme complet.

Essayez-le en ligne! (ou voir l'autre cas de test )

Comment?

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 octets

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

Essayez-le en ligne!

Renvoie une liste de listes ((x0 y0) (x1 y1)).

Explication

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

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]

Essayez-le en ligne!

Gelée , 24 octets

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

Essayez-le en ligne!

⁺ s'avère utile.

Format de sortie: [haut, bas], [gauche, droite] . 1-indexation.

JavaScript (ES6), 121 octets

-1 octet grâce à @ l4m2
-1 octet grâce à @tsh
+2 octets pour se conformer à la nouvelle règle de notation rectangle

Prend l'entrée comme une matrice de chaînes. Renvoie les coordonnées indexées 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

Essayez-le en ligne!

APL (Dyalog Classic) , 38 octets

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

Essayez-le en ligne!

Java 8, 208 205 octets

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

Peut certainement être joué au golf. J'utilise maintenant l'approche la plus évidente de l'utilisation de quatre trois boucles for imbriquées.

-3 octets grâce à @ceilingcat combinant les boucles internes des lignes et des colonnes en une seule boucle.

Explication:

Essayez-le en ligne.

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`