# Turning number ranges into prefixes

McGlinchy, Alistair Alistair.McGlinchy at marks-and-spencer.com
Thu Aug 24 15:52:42 BST 2006

Dave et al,

> 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);
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
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