12
\$\begingroup\$
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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think a better way to word it is to say that: rectangles must be surrounded by 0's, or an edge \$\endgroup\$ – Cruncher Jan 16 '14 at 16:43
  • \$\begingroup\$ Done. Thanks for wording it in a better English. \$\endgroup\$ – microbian Jan 16 '14 at 16:47
  • \$\begingroup\$ What about 1100\n1100\n0011\n0011 ? \$\endgroup\$ – Cruncher Jan 16 '14 at 16:54
  • 1
    \$\begingroup\$ I 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 \$\endgroup\$ – microbian Jan 16 '14 at 16:56
  • 1
    \$\begingroup\$ Even 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 \$\endgroup\$ – Cruncher Jan 16 '14 at 16:57
2
\$\begingroup\$

GolfScript, 107 characters

.n?):L;'1'/{,}%{1$+)}*;][]\{:A{{+}+[1L.~)-1]%&}+1$\,.@^\[[[A]]+{|}*]+}/{.{L%}{%$..&1$,1$,/*$=}:C~\{L/}C&},,

The input must be given on STDIN.

Examples:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
\$\endgroup\$
  • \$\begingroup\$ See comments above - it seems that "valid" rectangles need to have width/height both > 1. \$\endgroup\$ – Paul R Jan 17 '14 at 11:56
  • \$\begingroup\$ @PaulR That rule is not written in the question, by all reasonable definitions those are perfectly fine rectangles - maybe I'll add that later. \$\endgroup\$ – Howard Jan 17 '14 at 12:30
  • \$\begingroup\$ 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. \$\endgroup\$ – Paul R Jan 17 '14 at 13:23
  • \$\begingroup\$ I clarified that rectangle of size 1 is valid. \$\endgroup\$ – microbian Jan 17 '14 at 15:33
  • \$\begingroup\$ 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." \$\endgroup\$ – Paul R Jan 17 '14 at 17:54

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.