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.

Improve this question
\$\endgroup\$
10
  • 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
    Commented Jan 16, 2014 at 16:43
  • \$\begingroup\$ Done. Thanks for wording it in a better English. \$\endgroup\$
    – microbian
    Commented Jan 16, 2014 at 16:47
  • \$\begingroup\$ What about 1100\n1100\n0011\n0011 ? \$\endgroup\$
    – Cruncher
    Commented Jan 16, 2014 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
    Commented Jan 16, 2014 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
    Commented Jan 16, 2014 at 16:57

1 Answer 1

Reset to default
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
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ See comments above - it seems that "valid" rectangles need to have width/height both > 1. \$\endgroup\$
    – Paul R
    Commented Jan 17, 2014 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
    Commented Jan 17, 2014 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
    Commented Jan 17, 2014 at 13:23
  • \$\begingroup\$ I clarified that rectangle of size 1 is valid. \$\endgroup\$
    – microbian
    Commented Jan 17, 2014 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
    Commented Jan 17, 2014 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.