9
1
This question is similar to Biggest Square in a grid.
Challenge
Given a matrix of 1
and 0
in a string format "xxxx,xxxxx,xxxx,xx.."
or array format ["xxxx","xxxx","xxxx",...]
, You will create a function that determines the area of the largest square submatrix that contains all 1
.
A square submatrix is one of equal width and height, and your function should return the area of the largest submatrix that contains only 1
.
For Example:
Given "10100,10111,11111,10010"
, this looks like the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
You can see the bolded 1
create the largest square submatrix of size 2x2, so your program should return the area which is 4.
Rules
- Submatrix must be one of equal width and height
- Submatrix must contains only values
1
- Your function must return the area of the largest submatrix
- In case no submatrix is found, return
1
- You can calculate the area of the submatrix by counting the number of
1
in the submatrix
Test cases
Input: "10100,10111,11111,10010"
Output: 4
Input: "0111,1111,1111,1111"
Output: 9
Input "0111,1101,0111"
Output: 1
This is code-golf, so the shortest answer in bytes win.
3Why string format? – Stewie Griffin – 2018-04-25T18:23:55.427
Done, Thanks for your suggestions @StewieGriffin – Luis felipe De jesus Munoz – 2018-04-25T18:28:15.203
Isn't this an exact duplicate of the question you linked to? The only thing different is the IO format and the delimiters. – Nit – 2018-04-25T18:28:36.397
3Can we take the input as a binary (numeric) matrix? – Stewie Griffin – 2018-04-25T18:28:50.793
This looks very similar to the (now deleted) challenge Squares, so many squares.
– Jonathan Frech – 2018-04-25T18:29:46.573@Nit Not exactly. First the other one is a closed, out of topic question. also is not
code-golf
, it isfastest-code
. That's why i came with this one. Hope it is no problem with it – Luis felipe De jesus Munoz – 2018-04-25T18:31:01.293@StewieGriffin No sorry. Just array or string input – Luis felipe De jesus Munoz – 2018-04-25T18:32:34.733
@JonathanFrech Sorry, never saw that question. Hope there is no problem – Luis felipe De jesus Munoz – 2018-04-25T18:33:50.160
1Is
["xxxx";"xxxx";"xxxx";...]
ok a input? – Stewie Griffin – 2018-04-25T18:34:21.647@StewieGriffin Yes – Luis felipe De jesus Munoz – 2018-04-25T18:35:12.827
5For [0] still required to output 1? – l4m2 – 2018-04-25T20:37:55.460
@l4m2 Yes. Remember,
In case no submatrix is found, return 1
– Luis felipe De jesus Munoz – 2018-04-25T20:38:39.5106Hang about, why return 1 when no all-1 sub-matrix is found, wouldn't 0 make much more sense? (Otherwise it is simply a special case to handle) – Jonathan Allan – 2018-04-25T21:01:02.007
2As it stands I think both answerers would not mind if you changed the specs and I strongly recommend doing so because there's no point for returning 1 and it doesn't make the submissions more interesting. – ბიმო – 2018-04-25T23:15:56.470
1
This question appears to be taken from here.
– Laikoni – 2018-04-27T22:18:38.003