Find number of rectangles in a 2D byte array

0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000111111000000000000000000011111111111111100000000000000000
0000000000000100001000000111111000000011111111111111100000000010000000
0000000000000100001000000111111000000000000000000000011000000000000000
0000000000000111111000000111111000000000000000000000011000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

Your are given a 2 dimensional array of bytes of size m x n. It is guaranteed that all the bytes are 1's or 0's. Find the number of rectangles represented by 1's when viewed in 2d, as shown above.

Only fully filled rectangles are considered for counting.
Rectangles must be surrounded by 0's unless they are on edge(1's diagonally touching rectangles are Okay though (see example.)).

For example, in above array there are 5 valid rectangles.

You can use any language.

popularity-contest

microbian

Posted 2014-01-16T16:21:38.020

Reputation: 2 297

1I think a better way to word it is to say that: rectangles must be surrounded by 0's, or an edge – Cruncher – 2014-01-16T16:43:27.987

Done. Thanks for wording it in a better English. – microbian – 2014-01-16T16:47:43.917

What about 1100\n1100\n0011\n0011 ? – Cruncher – 2014-01-16T16:54:12.627

1I think that's why I wrote 'adjacent / overlapping'. These are 2 valid rectangles from my initial intention. But the 'surrounding' condition is restricting them now. Do you have a better way to explain it – microbian – 2014-01-16T16:56:35.553

1Even at adjacent it's ambiguous whether or not diagonal means adjacent or not. The same ambiguity whether or not surrounded means, surrounded at the corners, or just sides – Cruncher – 2014-01-16T16:57:01.090

I'm not sure there is a more succinct way to word it. Probably keep it as is and explicitly state that the corners can be 1's. Or including that case in your example helps as well. – Cruncher – 2014-01-16T16:58:58.630

I put my ideas in an edit suggestion – Cruncher – 2014-01-16T17:02:57.630

Just for clarification, degenerate rectangles shouldn't be counted, correct? For example, are a single 1 or a single subrow/subcolumn of adjacent 1's invalid? – O-I – 2014-01-16T18:42:07.937

Yes, they are invalid, and should not be counted. – microbian – 2014-01-16T18:53:43.843

So far this question has got only 1 answer. The solution from Howard is pretty slick. It seems that it was on the harder side. – microbian – 2014-01-22T00:03:59.873

See comments above - it seems that "valid" rectangles need to have width/height both > 1. – Paul R – 2014-01-17T11:56:19.330

@PaulR That rule is not written in the question, by all reasonable definitions those are perfectly fine rectangles - maybe I'll add that later. – Howard – 2014-01-17T12:30:21.040

I agree with your definition - I was just noting the discrepancy in the comments - it looks like OP needs to update the question to make it more definitive. – Paul R – 2014-01-17T13:23:00.233

I clarified that rectangle of size 1 is valid. – microbian – 2014-01-17T15:33:56.323

But you also said in the comments, in response to: "Just for clarification, degenerate rectangles shouldn't be counted, correct? For example, are a single 1 or a single subrow/subcolumn of adjacent 1's invalid?" by saying: "Yes, they are invalid, and should not be counted." – Paul R – 2014-01-17T17:54:42.577

I think when I said "rectangle of size 1 is valid", it added an ambiguity that it might always be valid regardless of other rules. So it is true that rectangle of size 1 is a valid rectangle but it should also conform to all the other rules of the problem. To get away from the ambiguity I removed the line 'rectangles of size 1 are valid', however, I kept the size 1 rectangle showing that it is valid because it fulfills all the rules, not because it is of size 1. Let me know if it is still confusing, but you get the idea i guess. – microbian – 2014-01-17T23:33:11.090

Find number of rectangles in a 2D byte array

Answers

GolfScript, 107 characters