An interesting problem

[McGlinchy, Alistair]

Woops. The code got stripped from my previous email
> I'd be interested in comments:

use strict;
use warnings;
use Memoize;

memoize('sum_power2square');
memoize('compute_power_two_ranges');

my $table;
my $max_x=0;
my $max_y=0;

my $c="A";
my @excel_col = map {$c++} (1..256);

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++;
}


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 considered\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
..".&excel_coord($x1, $y1, $x2, $y2)."\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 {
    my ($x1,$y1,$x2,$y2) =@_;
#    print "Summing range ($x1,$y1) => ($x2,$y2)  = ";
    my $x_ranges= compute_power_two_ranges($x1,$x2);
    my $y_ranges= compute_power_two_ranges($y1,$y2);

    # divide the range into rectangles with power of two length and
widths
    my $sum;
	# WARNING You can't use while... Each here as memoize may
provide the same hash for 
      # both X and Y ranges
    for my $x_start (keys %$x_ranges) {
        my $x_width= $x_ranges->{$x_start};
        for my $y_start (keys %$y_ranges) {
            my $y_width= $y_ranges->{$y_start};
            # We now have a rectange from $x_start,$y_start made up of
$x_width/y_width squares
            if ($x_width < $y_width) {
                # We need to devide this rectangle into multiple squares
$x_width wide
                for ( my $y_bot =$y_start; $y_bot < $y_start + $y_width
; $y_bot +=  $x_width) {
                    $sum += sum_power2square($x_start,$y_bot,$x_width)
                }
            } elsif ($x_width ==  $y_width) {
                # We have a square
                $sum+= sum_power2square($x_start,$y_start,$x_width)
            } else {
                # We need to devide this rectangle into multiple squares
$y_width wide
                for ( my $x_bot = $x_start; $x_bot < $x_start + $x_width
; $x_bot +=  $y_width) {
                    $sum += sum_power2square($x_bot,$y_start,$y_width)
                }
            }
        }
    }
#    print "$sum\n";
    return $sum;
}

# Compute the smallest number of ranges of integers to cover $bot to
$top
# with each range being a power of 2 wide.
# Eg ( 35, 47) => { 34=>2, 36=>39, 40=>47 }

sub compute_power_two_ranges {
    my ($bot,$top)=@_;
#    print "Power Two ranges for $bot,$top\n";
    my $range_bot = $bot;
    my $range_top;
    my $power =1;
    my %ranges;
    
    # Work out way from smallest to largest powers of two.
    while ($range_bot  + $power < $top+1) {
        if ($range_bot % ($power*2)) {
            # Then must add a range of size $power 
            $range_top = $range_bot + $power-1;
#            print "New range ($range_bot .. $range_top) of length
$power\n";
            $ranges{$range_bot}=$power;
            $range_bot+=$power;
        }
        $power *=2;
    }
#   print "Power capped at $power\n"; 
    # Now work the way back down
    while ( $range_bot <= $top) {
        if ($range_bot + $power <= $top+1) {
            # Then must add a range of size $power 
            my $range_top = $range_bot + $power-1 ;
#            print "New range ($range_bot .. $range_top) of length
$power\n";
            $ranges{$range_bot}=$power;
            $range_bot+=$power;
        }
        $power/=2;
    }
    return \%ranges
}
 
# Sum the square range with top left ($x,$y) and width $width a power of
two
sub sum_power2square {
    die "coding error" unless @_ == 3;
    my ($x, $y, $width) =@_;
#   print "SumSQ $x,$y,$width\n";
    my $sum;
    # Single Cell 
    return $table->[$x]->[$y]  if $width == 1;

    # or 4 squares with half the width
    my $new_w= $width/2;  # WIll always be an integer
    return (
        sum_power2square($x       , $y         , $new_w)+ 
        sum_power2square($x       , $y+$new_w  , $new_w)+ 
        sum_power2square($x+$new_w, $y         , $new_w)+ 
        sum_power2square($x+$new_w, $y+$new_w  , $new_w)
    )
}

sub excel_coord {
    my ($x1,$y1,$x2,$y2) =@_;
    return sprintf( "%s%s:%s%s",
        $excel_col[$y1], $x1+1,
        $excel_col[$y2], $x2+1
    )
}

__DATA__
31  36  -47 4   
22  -36 -2  26  
-32 -19 -9  -28 
-21 -7  -20 40  

**********************************************************************
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