An interesting problem

[Andy Armstrong]

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