21
1
Background
I want to buy an plot of land and build my house on it. My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots. I want you to write a program that analyzes the plots for me.
Input and output
Your input is a rectangular 2D array of bits, of size at least 1×1, in any reasonable format.
The array represents a plot of land; 1
s are "good" areas where I could build my house, and 0
s are "rocky" areas where the house cannot be built.
Your output shall be the maximal area of a solid rectangle of 1
s in the input array.
It represents the area of the largest house I could build on the plot.
Note that if there are no 1
s in the input, then the output is 0
.
Example
Consider the input
101
011
111
The largest rectangle of 1
s is the 2×2 rectangle in the lower right corner.
This means that the correct output is 4
.
Rules and scoring
You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.
Test cases
0
-> 0
1
-> 1
00
00
-> 0
01
10
-> 1
01
11
-> 2
111
010
111
-> 3
101
011
111
-> 4
0111
1110
1100
-> 4
1111111
1110111
1011101
-> 7
111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20
000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
8Bulldozer, 4 bytes:
plow
. – Conor O'Brien – 2016-05-06T01:39:29.6201Is it OK if my solution only works for rectangles of up to 30×30? – Neil – 2016-05-06T09:26:00.263
1@Neil No, it should (at least theoretically) work for about as large inputs as your language can handle. – Zgarb – 2016-05-06T12:24:30.237
1I was hoping to do some sneaky bit-twiddling but in that case I won't bother. – Neil – 2016-05-06T13:26:41.860
Could we have the option to receive the dimensions of the land also? – miles – 2016-05-06T15:00:54.437
@miles Only if your language can't extract them from the array in another way. – Zgarb – 2016-05-06T15:06:47.377
@neil do it in Ruby or Python then. Both support arbitrary precision integers. That said, "as large as your language can handle" is a bit open to interpretation. 8x8 in brainfuck would be mighty impressive, but I'm sure it's (theoretically) possible to go bigger :-S – Level River St – 2016-05-06T18:36:35.900
@LevelRiverSt Fortunately I found a way of doing it without limiting myself to 30. – Neil – 2016-05-06T19:19:33.610
1Does the solution need to account for rotation? – None – 2016-05-06T20:10:09.507
@YiminRong No, the sub-rectangle of 1s will not be rotated. Although I'm not entirely sure that's what you meant. – Zgarb – 2016-05-06T20:53:48.903