# An interesting problem

McGlinchy, Alistair Alistair.McGlinchy at marks-and-spencer.com
Wed Jan 3 20:44:06 GMT 2007

```> 03 January 2007 19:33 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:
> >
> That's sort of what I have been playing with, but it still
> doesn't seem
> impressively fast. There's a large number of off-by-one
> errors possible
> in here, but the answers seems to tally up when I check in Excel.
>
> I'd be interested in comments:

I'll comment on my own code. My original brute force algorithm is still
faster with a 30x100 array(albeit with deep recursion warnings).  What
did I do wrong ?

#!/usr/bin/perl
use strict;
use warnings;
my %store;

my \$table;

my \$max_x=0;
my \$max_y=0;

while (<DATA>) {
chomp;
s/^\s+//;# Remove initial  whitespace.
s/\s+\$//;# Remove trailing whitespace.
next if /^\s*\$/;
my @row = split /\s+/;
push @\$table, \@row;
\$max_y = @row;
\$max_x++;
}

print "\$max_x, \$max_y\n";

my \$best;
my @result;
for (my \$x1 = 0   ; \$x1< \$max_x ; \$x1++) {
for (my \$y1 = 0   ; \$y1< \$max_y ; \$y1++) {
print "New \$x1,\$y1 for top left considerd\n";
for (my \$x2 = \$x1 ; \$x2< \$max_x ; \$x2++) {
for (my \$y2 = \$y1 ; \$y2< \$max_y ; \$y2++) {
my \$val = sum_range(\$x1, \$y1, \$x2, \$y2);
#    print "Range (\$x1,\$y1) , (\$x2,\$y2) has val \$val\n";
if (!defined(\$best) or \$val > \$best) {
print "Range (\$x1,\$y1) , (\$x2,\$y2) is better with \$val\n";
\$best = \$val;
@result = (\$x1,\$y1,\$x2,\$y2);

}
}}}}

print "Range (\$result[0],\$result[1]) , (\$result[2],\$result[3]) has val
\$best\n";

sub sum_range {
die "coding error" unless @_ == 4;
my (\$x1,\$y1,\$x2,\$y2) =@_;
if (\$x1 < \$x2) {
return
sum_row(  \$x1,     \$y1, \$y2) +     # The \$x1 column's row
sum_range(\$x1 + 1, \$y1, \$x2, \$y2)  # The remaining columns'
row range
} elsif (\$x1 == \$x2) {
return sum_row(  \$x1,     \$y1, \$y2)    # The \$x1 column
}
}

sub sum_row {
die "coding error" unless @_ == 3;
my (\$x, \$y1,\$y2) =@_;
my \$sum;
\$sum += \$_ for @{\$table->[\$x]}[\$y1 .. \$y2];
return \$sum;
}

**********************************************************************
Registered Office:
Marks and Spencer plc
Waterside House
London
W2 1NW

Registered No. 214436 in England and Wales.

Telephone (020) 7935 4422
Facsimile (020) 7487 2670

<<www.marksandspencer.com>>

Please note that electronic mail may be monitored.

This e-mail is confidential. If you received it by mistake, please let us know and then delete it from your system; you should not copy, disclose, or distribute its contents to anyone nor act in reliance on this e-mail, as this is prohibited and may be unlawful.
2005

```