An interesting problem

[Dan Rowles]

Set the max to the value of the cell at 0,0 before starting the inner 
loop. Then, you can remove the "defined" check.

Dan




McGlinchy, Alistair wrote:
> Simon Matthews wrote:
>> One thing that might speed it up even further would be to 
>> pre-cache the 
>> total of (0..x, 0..y) for each x and y.
>>
>> Then for a particular tile (l..r, t..b):
>>
>> 0   l   r
>> +---|---|----+
>> |...|///|    |
>> ----+---+----- t
>> |\\\|XXX|    |
>> |\\\|XXX|    |
>> ----+---+----- b
>> |   |   |    |
>> +---|---|----+
>>
>> Total of ... will be T(l,t)
>> Total of /// will be T(r,t) - T(l,r)
>> Total of \\\ will be T(l,b) - T(l,r)
>>
>> So the total of XXX will be:
>>    T(r,b) - ( total of /// + total of \\\ + total of ... )
>>  = T(r,b) - ( T(r,t) - T(l,r) + T(l,b) - T(l,r) + T(l,r) )
>>  = T(r,b) - T(r,t) + T(l,t) - T(l,b)
>>
>> Simon
> 
> I've had a go at this method. Its slower than my previous post (up to
> 40secs from about 16secs).  There's some hash ref caching that may help
> speed it up a bit. What I cannot work out is how you think this method
> can be intergrare within the previous method.  Please advise.
> 
> By the way does anyone have a better method doing the max calculation. I
> loathe  "if (!defined($max) or $max  < $val)" line.
> 
> Cheers
> 
> Alistair
> 
> 
> __CODE__
> 
> # Same top bit as before.
> 
> sub prepare_origin_range {
>     # Prepare a cache of range sums from he origin to $x,$y
> 
>     # Initialise the top left row 
>     $sum_from_origin[0][0] = $table[0][0];
> 
>     # Complete the calulations for the rest of $y where $x==0.
>     for my $y        (1 .. $max_y) {
>         $sum_from_origin[0][$y] = 
>             $sum_from_origin[0][$y-1] + 
>             $table[0][$y];
>     }
>     # Populate the whole table of the $x >0 
>     for my $x        (1 .. $max_x) {
>         #@row_sum is the sume of the slice (0..$y) of the $x'th row
>         my @row_sum = ($table[$x][0]); 
>         $sum_from_origin[$x][0] = $row_sum[0];
>         for my $y        (1 .. $max_y) {
>             $row_sum[$y]= $row_sum[$y-1] + $table[$x][$y];
>             $sum_from_origin[$x][$y] = $sum_from_origin[$x-1][$y] +
> $row_sum[$y];
>         }
>     }
> }
> 
> sub max_sum_range { 
>     my $max;
>     for my $x1(0   .. $max_x) {
>     for my $y1(0   .. $max_y) {
>     for my $x2($x1 .. $max_x) {
>     for my $y2($y1 .. $max_y) {
>         #+---|---|
>         #| A | B |
>         #----+---+
>         #| C | D |
>         #----+---+
>         my $A    = $sum_from_origin[$x1][$y1];
>         my $AB   = $sum_from_origin[$x1][$y2];
>         my $AC   = $sum_from_origin[$x2][$y1];
>         my $ABCD = $sum_from_origin[$x2][$y2];
>         my $val = $ABCD - $AB - $AC + $A;
>         if (!defined($max) or $max  < $val) {
>             $max = $val;
>             print "Range ($x1,$y1) , ($x2,$y2) is better with $val\n";
>             @result = ($x1,$y1,$x2,$y2);
>         }
>     }}}}
>     return ($max, @result);
> }
>  
> 
> **********************************************************************
> 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
> 
> 
> 

-- 
Dan Rowles
CTO
Outcome Technologies

_________________________________

t: +44 (0)207 656 2460
f: +44 (0)709 230 6588
m: +44 (0)798 076 8143
e: d.rowles at outcometechnologies.com
w: http://www.outcometechnologies.com
BUPA House
15-19 Bloomsbury Way
London WC1A 2BA
_________________________________

***This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they are
addressed. If you receive this message in error, please return it to the
sender.***