Turning number ranges into prefixes

[McGlinchy, Alistair]

Dave et al,

A few comments about your solution. I have a different solution below.
> my @minprefixes = map { substr($min, 0, $_) } reverse 1..length($min);
> my @maxprefixes = map { substr($max, 0, $_) } reverse 1..length($max);
> my $longest_prefix;
> foreach(0 .. length($max) - 1) {
>     if($minprefixes[$_] == $maxprefixes[$_]) {
>         $longest_prefix = $minprefixes[$_];
>         last;
>     }
> }

As commented earlier. This can be obfu^Wsimplified by these two lines
("$min" ^ "$max") =~  /(^\0*)/;
my $longest_prefix = substr($min,0,length $1);

>     my $extradigits = length($min) - length($prefix);
>     return () unless($extradigits);	
This is bugged. $extradigits can legally be 0. Consider $min =1 and $max
=2.
   
>     if(
>         $prefix.('0' x $extradigits) >= $min &&
>         $prefix.('9' x $extradigits) <= $max
I'm sure there are some optimisations possible here too. Eg
	($prefix  ge $min)  is the same as the first clause isn't it?

Now my solution. I approached this problem from a more text based
solution allowing for variable length phone number prefixes. Eg phone
numbers from 141xxxx to 1541yyyyy.  More comments inline.

Cheers

Alistair


__CODE__

my $min = 141;  # same as 1410000000...
my $max = 1541; # same as 1541999999...

print "Min: $min, Max: $max\n";
("$min" ^ "$max") =~  /(^\0*)/;
my $longest_prefix = substr($min,0,length $1);
print "Longest prefix: $longest_prefix\n";

my @results;
my $last_char;

# Pop each char off $min and add all suffixes up to 9 into result
push @results,$min;
while (length($min) > length($longest_prefix)+1) {
    push @results,  map {$min.$_} (chop $min)+1 .. 9;
}
# Repeat with $max,
push @results, $max;
while (length($max) > length($longest_prefix)+1) {
    push @results,  map {$max.$_} 0 .. (chop $max) -1 ;
}
# Fill in the middle bit between what's left of $min and $max 
push @results, map {$longest_prefix.$_} ( (chop $min) + 1 .. (chop
$max)-1);

# The sort here is just being lazy, it is possible to add all the above
entries 
# into @results in the right order first time round if the code were
reordered
# and a few more temp vars included.
@results= sort @results;  

# optimise results to remove suffixes with all 10 possible entries
# xxxxxx0, xxxxxx1, ... xxxxxx9 
# I tried to do this automatically within the above code but couldn't 
# get it to work without recursion.

for (my $i =0; $i< @results -9; $i++) {
    if (
            (substr($results[$i],-1,1) eq 0) and  # The last char is 0
            ($results[$i+ 9]  == $results[$i]+9)  # 10th pos is 9 ahead
        ) {
            my $opt_val = substr($results[$i],0,-1);
            splice(@results,$i, 10, $opt_val);
            $i = 0; # We have to start from scratch if we optimise here
            # ...maybe not I think we only need to go back $i -9 for the

            # optimsation to work
            redo;
    }
}

print "  [".join(",",  @results)."]\n";

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