An interesting problem

[McGlinchy, Alistair]

> 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
35 North Wharf Road
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