26
\$\begingroup\$

Input

The board: A 2D container (matrix, list of lists, etc.) of letters like:

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

If you choose a list of lists you may assume that all of the sublists are of the same length.

Rules

  • To make a valid rectangle you need all rectangle corners with the same 'letter'.
  • Example, look the sample board with X bellow. You can see 'X' on (1,0) also on (4,0) also on ( 1,3) and on (4,3) then you have the rectange [1,0,4,3] that means from (1,0) to (4,3):

Sample board with 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"]
  • The goal is to find the rectangle or one of the rectangles with the largest area, calculated by (right-left+1)*(bottom-top+1)
  • If there are multiple rectangles with the same maximum area, output any one. Optionally the one with (top coordinate, left coordinate, right coordinate, bottom coordinate) lexicographically smallest.
  • Rectangles must have edges parallel to the board's edge.
  • Each letter is a printable ASCII char from A to Z (both included).

Output

The output should be the left-up and right-down positions of the largest area rectangle corners. For the first sample "board" the big square is the yellow one:

enter image description here

And the answer should be:

[1, 1, 8, 4]

A second example test case

An input of:

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

Should yield one of these three coordinate lists identifying an area six rectangles:

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

This question is posted on Stack Overflow with title: How to find the largest rectangle in a 2D array formed by four identical corners? and with this rude JS solution (I can say "rude" because is my code ;) :

Ok, is my first post, be tolerant with me please. I will change all you say to improve the quiz.

\$\endgroup\$
  • 7
    \$\begingroup\$ Hi, welcome to PPCG! This seems to be a good challenge, but seems to lack any winning criterion. Typically, posts here are tagged [code-golf], which means that the shortest code (in bytes) wins. \$\endgroup\$ – Conor O'Brien Apr 7 '18 at 16:11
  • 1
    \$\begingroup\$ I thought I would let you know that we have a sandbox that you can use to get feedback on questions before they are posted to the main site. The sandbox is useful to pretty much everyone here but especially to beginners, who might not know all the rules and expectations we have. \$\endgroup\$ – Sriotchilism O'Zaic Apr 7 '18 at 16:48
  • 2
    \$\begingroup\$ Some answers output the coordinates in sorting order for the "first" rectangle (i.e, top, left, bottom, right) instead of (left, top, right, bottom) as seen in your examples. Is this ok? \$\endgroup\$ – nimi Apr 7 '18 at 18:58
  • 2
    \$\begingroup\$ Less strict output formats usually encourage more answers, so something like ((left,top),(right,bottom)) should be fine too. I deleted my answer and answer again when the question is completely refined. \$\endgroup\$ – Angs Apr 7 '18 at 19:10
  • 1
    \$\begingroup\$ Sure, If you are going to accept an answer it should be the shortest overall, this is how most people like things done on the site. However there is no consequence for not doing so. There is also a growing opinion that accepting answers is detrimental to the site. I am of that opinion, and thus I never accept answers on my challenges. What you do is up to you. \$\endgroup\$ – Sriotchilism O'Zaic Apr 11 '18 at 14:31
6
\$\begingroup\$

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Hi @ovs, is for you and inconvenient if I change the rule to figure up the area to: (x2-x1+1)×(y2-y1+1) as Angs did suggested? \$\endgroup\$ – danihp Apr 7 '18 at 19:09
  • \$\begingroup\$ I would like to relax some rules to encourage more answers. Can I? \$\endgroup\$ – danihp Apr 7 '18 at 19:12
  • \$\begingroup\$ @danihp Go ahead.This doesn't invalidate my answer, right? \$\endgroup\$ – ovs Apr 7 '18 at 22:04
  • \$\begingroup\$ Nop, your answer is right! Nice. \$\endgroup\$ – danihp Apr 8 '18 at 18:36
5
\$\begingroup\$

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`

Try it online! Edit: Saved 1 byte because the trailing ) matching the $.( is implicit. Explanation:

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

This regular expression matches rectangles. The groups are as follows: 1) Top row (as capture count) 2) Left column (as length) 3) Balancing to ensure the left corners align 4) Letter for the corners 5) Width + 1 (as length) 6) Balancing to ensure the right corners align 7) Right column (as length) 8) unused 9) Height (as capture count). The w option ensures that all possible widths of rectangles are matched for each given top left corner. The $ options lists the results using the following substitution pattern.

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

The substitutions are as follows: The right column, the top row, the left column, the negation of the area of the rectangle (literally calculated as the length of repeating the width string by one more than height number of times), the left column, the top row, the right column, followed by an expression that evaluates to the bottom row (a capture would have cost 12 bytes plus I've run out of single-digit variables). The first four captures represent the sort order in order of priority. As Retina sorts stably, a multicolumn sort can be established by sorting by each sort column in turn from least to greatest priority. (The area must be sorted in descending order, so a single string sort cannot be used.)

4{N`

Four numeric sorts are then performed.

)m`^.*?,

The sort column is then deleted after each sort.

0G`

The first entry is therefore now the desired result.

Note: The restriction on the choice of rectangle of a given area has since been relaxed and the following 144 143-byte version prefers a wider rather than a taller rectangle:

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Fails the lexicographical-min requirement (try the test case I added to the OP for example) (maybe also output can be in the wrong order??) TIO \$\endgroup\$ – Jonathan Allan Apr 7 '18 at 19:53
  • \$\begingroup\$ (...yeah first two values in output are the wrong way around I think) \$\endgroup\$ – Jonathan Allan Apr 7 '18 at 20:03
  • \$\begingroup\$ I just relaxed some restrictions (lexicographical-min requirement ). I hope don't be a problem for you. \$\endgroup\$ – danihp Apr 7 '18 at 20:12
  • \$\begingroup\$ ...this will now need to match lines and points. \$\endgroup\$ – Jonathan Allan Apr 7 '18 at 20:14
  • \$\begingroup\$ Fixing the lexicographical order cost 20 bytes :-( and I noticed that the area calculation changed, which cost another 2 bytes, but I don't know what @JonathanAllan means about points. \$\endgroup\$ – Neil Apr 7 '18 at 20:23
4
\$\begingroup\$

Jelly, (27?)  29  28 bytes

27 if 1-based indexing is allowed - remove trailing

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

A full program.

Try it online! (or see the other test case)

How?

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)
\$\endgroup\$
4
\$\begingroup\$

Perl 6, 83 73 bytes

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

Try it online!

Returns a list of lists ((x0 y0) (x1 y1)).

Explanation

{
  ([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.
  }
}
\$\endgroup\$
3
\$\begingroup\$

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]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You can remove b<=d, as long as you keep a<=c. \$\endgroup\$ – Sriotchilism O'Zaic Apr 7 '18 at 17:37
  • \$\begingroup\$ @ovs actually that wont work either (see the example I added TIO) \$\endgroup\$ – Jonathan Allan Apr 7 '18 at 18:39
  • \$\begingroup\$ @nimi: I could argue that's just a matter of transposing the input. \$\endgroup\$ – Angs Apr 7 '18 at 18:54
  • \$\begingroup\$ It's ok for me. You can transposing the input. \$\endgroup\$ – danihp Apr 7 '18 at 19:06
3
\$\begingroup\$

Jelly, 24 bytes

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

Try it online!

proves to be useful.

Output format: [top,bottom],[left,right]. 1-indexing.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 121 bytes

-1 byte thanks to @l4m2
-1 byte thanks to @tsh
+2 bytes to comply with the new rectangle scoring rule

Takes input as a matrix of strings. Returns 0-indexed coordinates: [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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – l4m2 Apr 7 '18 at 17:31
  • \$\begingroup\$ If there are multiple rectangles with the same maximum area, output any one; maybe (A=...)<=b -> (A=...)<b? \$\endgroup\$ – tsh Apr 8 '18 at 8:16
  • \$\begingroup\$ @tsh That's now safe indeed. Thanks! \$\endgroup\$ – Arnauld Apr 8 '18 at 8:30
2
\$\begingroup\$

APL (Dyalog Classic), 38 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

Can definitely be golfed.. I now use the most obvious approach of using four three nested for-loops.

-3 bytes thanks to @ceilingcat combining the inner loops of rows and columns into a single loop.

Explanation:

Try it 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`
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.