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
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
More information about the london.pm
mailing list