LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 November 7 2010

arithma
Member

Exercise - Overlapping Rectangle Sum

You are given a grid of integral values.
Ex:

0 1 2 3 4 5
6 7 8 9 0 1
1 3 5 7 9 1
5 6 5 6 5 6

In addition to its width and height.

You are asked to find the sum of the elements that fall inside the domain. The domain is defined as a list of rectangles that can overlap. Each rectangle is defined by four values: col (starting column), row(starting row), cols (width in columns), rows (height in rows).

An example domain to sum over for the above grid is:
Rectangle 1: 0 0 2 2
Rectangle 2: 1 1 2 2

The above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum [strike]twice[/strike] once. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.

Last edited by arithma (November 7 2010)

Offline

#2 November 7 2010

saeidw
Member

Re: Exercise - Overlapping Rectangle Sum

arithma wrote:

The above two rectangles overlap on the single cell at coordinates (1, 1). The element in there should be added to the sum twice. The sum would then be: 0 + 1 + 6 + 7 + 8 + 3 + 5 = 30.

Wouldn't that be 0 + 1 + 6 + 7 + 7 +8 + 3 + 5 = 37?

This looks like a fun exercise, I'll see if I can put up some simple code to do it later on.

Offline

#3 November 7 2010

jsaade
Member

Re: Exercise - Overlapping Rectangle Sum

I think he meant it should be added once as it is an intersection.

Offline

#4 November 7 2010

arithma
Member

Re: Exercise - Overlapping Rectangle Sum

@jsaade: You got it right.

The naive solution for the problem would be to go through each cell, check its inclusion-status in any of the rectangles, and then accordingly sum to a sentinel. I encourage you to see past that and try to solve for a performant algorithm (in possibly an infinite grid with arbitrarily large rectangles)

Offline

#5 November 7 2010

GN90
Member

Re: Exercise - Overlapping Rectangle Sum

um shouldn't rectangle 1 be : 1 1 2 2 ?

cause in your case (0 0 2 2) rect1 would be :

0 1 2
6 7 8
1 3 5

and rect 2 would be :

7 8
3 5

so the overlap thing will be 7 8 3 5
and the sum will be 0 + 1 + 2 + 6 + 7 + 8 + 1 + 3 + 5 = ??

or I did understand the thing wrong ?

Offline

#6 November 7 2010

Joe
Member

Re: Exercise - Overlapping Rectangle Sum

rect1 (0 0 2 2) is

0 1 
6 7

rect2 (1 1 2 2) is

7 8
3 5

Look carefully at the definition of rectangles.

Offline

Board footer