Re: Lookahead algorithm for IP subroutine

[demerphq]

To the best of my understanding from the CB you can factor a lot of stuff out of your current approach. Here is what i came up with based on your scratchpad.

use strict;
use warnings;


sub find_seq {
    my ($num,$array)=@_;

    # assert that @$array is sorted numerically increasing

    return unless $num<=@$array; # illegal

    $num--;  # num is one based, we need a 0 based value
    my $min_pos=$num;
    my $min=$array->[$min_pos] - $array->[0];

    for my $i ($num..$#$array) {
        if ($array->[$i] - $array->[$i-$num] == $num) {
            return ($i-$num,$i);
        } elsif ($min > $array->[$i]-$array->[$i-$num]) {
            $min=$array->[$i] - $array->[$i-$num];
            $min_pos=$i;
        }
    }
    return ($min_pos-$num,$min_pos);
}

my @array=sort { $a <=>$b } qw( 1 3 4 5 6 8 15 31  
                                61 62 63 64 65 66 67 
                                70 71 72 73 );

for my $num (2..@array-5) {
    if (my ($s,$f)=find_seq($num,\@array)) {
        print "seq($num) == \@array[$s..$f]=(",
              join(",",@array[$s..$f]),")\n";
    } else {
        print "No sequence for $num\n";
    }
}
__END__
seq(2) == @array[1..2]=(3,4)
seq(3) == @array[1..3]=(3,4,5)
seq(4) == @array[1..4]=(3,4,5,6)
seq(5) == @array[8..12]=(61,62,63,64,65)
seq(6) == @array[8..13]=(61,62,63,64,65,66)
seq(7) == @array[8..14]=(61,62,63,64,65,66,67)
seq(8) == @array[8..15]=(61,62,63,64,65,66,67,70)
seq(9) == @array[8..16]=(61,62,63,64,65,66,67,70,71)
seq(10) == @array[8..17]=(61,62,63,64,65,66,67,70,71,72)
seq(11) == @array[8..18]=(61,62,63,64,65,66,67,70,71,72,73)
seq(12) == @array[7..18]=(31,61,62,63,64,65,66,67,70,71,72,73)
seq(13) == @array[6..18]=(15,31,61,62,63,64,65,66,67,70,71,72,73)
seq(14) == @array[1..14]=(3,4,5,6,8,15,31,61,62,63,64,65,66,67)

It expects a length and an array of increasing ordered numbers. It finds the start index and end index of the array such that, the sequence is the lowest contiguous sequence of the required size, or failing that a sequence where the difference between the highest and lowest value is the least.

The trick with this is that you can tell if a sequence is contiguous by subtracting the beginnig from the end, likewise we can get the sequence with the least difference between begin and end by the same approach. We can remember the "best" sequence we've seen by storing its endpoint, and we can simply exit when we have encountered the first contiguous sequence (which will be the lowest since we start low and iterate up). Anyway, the idea here is to take something like this and adapt it to your exact requirements, the way you formatted the code and stuff made it fairly hard to read and work out. Alway use whitespace in your queries to make them readable, SQL is an ugly language to begin with so making it readable is really important.

HTH

The text in this node was added sometime after it was posted in an attempt to clarify the code for hok.

Later Update: Heres a cleaner and annotated version of the code, same idea, but simplified further. Note the early termination when it finds a contiguous sequence which allows this to be worst case O(N) and best case lower.

sub find_seq {
    my ($num,$array)=@_;

    # assert that @$array is sorted numerically increasing

    return if $num > @$array; # ensure array is big enough
           

    $num--;  # num is one based, we need a 0 based value
    
    # the default return will be the first N values,
    # if we find better then we will overwrite these
    my $min_start = 0;
    my $min_end = $num;
    my $min = $array->[$num] - $array->[0];

    # start at num as below that nothing can match
    for my $end ( $num .. $#$array) {
        my $start = $end - $num;
        my $diff = $array->[$end] - $array->[$start];
        if ( $min > $diff ) {
            # we have found a better sequence, 
            # so remember where it is
            $min = $diff;
            $min_end = $end;
            $min_start = $start;
        }
        # if the sequence is contiguous we can finish
        last if $diff == $num; 
    }
    return ( $min_start, $min_end );
}