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.

Improve this question
\$\endgroup\$
12
  • 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\$ Commented Apr 7, 2018 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\$ Commented Apr 7, 2018 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\$ Commented Apr 7, 2018 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\$ Commented Apr 7, 2018 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\$ Commented Apr 11, 2018 at 14:31

9 Answers 9

Reset to default
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!

Improve this answer
\$\endgroup\$
4
  • \$\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\$ Commented Apr 7, 2018 at 19:09
  • \$\begingroup\$ I would like to relax some rules to encourage more answers. Can I? \$\endgroup\$ Commented Apr 7, 2018 at 19:12
  • \$\begingroup\$ @danihp Go ahead.This doesn't invalidate my answer, right? \$\endgroup\$ Commented Apr 7, 2018 at 22:04
  • \$\begingroup\$ Nop, your answer is right! Nice. \$\endgroup\$ Commented Apr 8, 2018 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!

Improve this answer
\$\endgroup\$
10
  • \$\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\$ Commented Apr 7, 2018 at 19:53
  • \$\begingroup\$ (...yeah first two values in output are the wrong way around I think) \$\endgroup\$ Commented Apr 7, 2018 at 20:03
  • \$\begingroup\$ I just relaxed some restrictions (lexicographical-min requirement ). I hope don't be a problem for you. \$\endgroup\$ Commented Apr 7, 2018 at 20:12
  • \$\begingroup\$ ...this will now need to match lines and points. \$\endgroup\$ Commented Apr 7, 2018 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\$ Commented Apr 7, 2018 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)
Improve this answer
\$\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. } }
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ You can remove b<=d, as long as you keep a<=c. \$\endgroup\$ Commented Apr 7, 2018 at 17:37
  • \$\begingroup\$ @ovs actually that wont work either (see the example I added TIO) \$\endgroup\$ Commented Apr 7, 2018 at 18:39
  • \$\begingroup\$ @nimi: I could argue that's just a matter of transposing the input. \$\endgroup\$ Commented Apr 7, 2018 at 18:54
  • \$\begingroup\$ It's ok for me. You can transposing the input. \$\endgroup\$ Commented Apr 7, 2018 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.

Improve this answer
\$\endgroup\$
0
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!

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

APL (Dyalog Classic), 38 bytes

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

Try it online!

Improve this answer
\$\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`
Improve this answer
\$\endgroup\$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.