Link to home
Start Free TrialLog in
Avatar of shilpi84
shilpi84

asked on

count squares of different dimensions in a matrix

I have a question. It isn't homework I just want to know the logic that must be applied in this program.


Suppose u r given a 4*3 rectangle like (take these values from user)

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

Now calculate the no. of squares in this rectangle like:
No. of squares of dimension 1 is 12
No. of squares of dimension 2 is 6
No. of squares of dimension 3 is 2
No. of squares of dimension 4 is 0
Total no. of squares are 20.

So, can anyone please help me with the logic?
Thanks.
SOLUTION
Avatar of Infinity08
Infinity08
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Well, the number of squres of the dimension 1*1 in a m*n-sized rectangle will always be m*n*...
A few typo corrections :

        0 = (4 - 3) * (3 - 0)

should have been :

        0 = (4 - 3) * (3 - 3)

And I should have shown :

        12 = 3 * 4

as :

        12 = (4 - 0) * (3 - 0)
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Hi NovaDenizen,

I don't believe that it's that complicated.  :)

Counting all possible squares of size S in a rectangle size MxN is the expression that I posted.

  ( Length(Rectangle) - Side(Square) + 1 ) * ( Width(Rectangle) - Side(Square) + 1 )

that is,

  (M - S + 1) * ( N - S + 1)


Kent
Avatar of NovaDenizen
NovaDenizen

If your expression is correct (and mine is too. :) ), then my expression is equivalent to the sum of (M-S+1)(N-S+1) for all S between 1 and min(N,M).  My expressions solves for the whole sum, where yours is only for a particular square size.
A non-formulaic approach...

You first multiply width times height of the entire rectatngle (or height times width, it doesn't matter) (e.g. 4 x 3 = 12)
Then, reduce each number by 1 and multiply again (e.g. 3 x 2 = 6)
Reduce each number by 1 again, and multiply again (e.g. 2 x 1 =2).

Keep reducing and multiplying, until one of the numbers hits 0.  Then, add all the products: in the example above, 12 + 6 + 2 = 20.
Take a look at the first post, Galisteo8 ...
Oops. Thanks, infinity. I'm late to the party. :)
Infinity has pretty well pegged it for you...
As the size of your "squares" increase, the size of the matrix you are "dealing with" effectively decreases...
If you were writing it as a program, a for loop to reduce the variables, and since the variables are not necessarily equal, an if to exit the for loop when either of the resulting reductions reachs zero...
In the meantime, multiply the variables and total the results.
> No. of squares of dimension 2 is 6

Question is more like rectangles than squares, still that is incorrect. Taking

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

I think you are missing these:

__________________________
|                |                  |                |
|                |                  |                |
|________|_________|________|
|                |                  |                |
|        2      |                  |        2      |
|________|_________|________|
|                |                  |                |
|        2      |                  |        2      |
|________|_________|________|
|                |                  |                |
|                |                  |                |
|________|_________|________|

etc

Hi Sunbow,

6 is correct.

___________________________
|                |                  |                |
|      A        |        B        |       C       |
|________|_________|________|
|                |                  |                |
|      D        |        E        |       F       |
|________|_________|________|
|                |                  |                |
|     G         |        H        |      I        |
|________|_________|________|
|                |                  |                |
|      J         |        K        |      L        |
|________|_________|________|

2x2 squares can only be inserted (defined) such that their upper left small square is coincidental with A, B, D, E, G, and H.


Kent
Mybe it is design or image, and seeing what is rectangle or not while open to "these values from user"

I pretty much stopped review where AD is square, and imagine that you presume that. So I bow out Thanks This is then a math question, not puzzle.