# An interesting problem

Andy Armstrong andy at hexten.net
Wed Jan 3 19:32:41 GMT 2007

On 3 Jan 2007, at 14:03, Paul Orrock wrote:
> Does anyone have any clever ways of doing this other than brute
> forcing it by checking every possible range (in a 100 by 30 table).
> And if brute forcing it is the only option (which I suspect it is)
> does anyone have any clever ways of doing it. Using numbers for
> columns and rows instead of letters is fine.

If you do end up brute forcing it you may be able to speed it up by
first computing a quad tree. To do that you'd calculate the sum of
each 2x2 meta-square and then do that recursively until you end up
with a single square that's the sum of all the squares like this:

Original (level 0):

1  2 -1  3
3 -2  4 -2
2 -2  1 -4
-3  1  2  1

Level 1:

4  4
-2  0

Level 2:

6

Then the code that computes the value of any region can consult
higher level squares for the bulk of its work only drilling down to
the original array around the edges of a region.

So to compute the sum of the top left 3x3 array you could either take
the 4 from the top left of the level 1 square and add in the 2, -2,
1, 4, -1 that hang over the edge of it.

In practice that'd probably be slower for small arrays - but it would
be a huge win for large datasets.

--
Andy Armstrong, hexten.net