CODEWITHSUNDEEP
perlsortingintegerrange
SSilk
SSilk

Reputation: 2502

Perl: Find ranges of numbers in an array

In Perl, if I have a sorted array of integers, is there a compact way to convert it to a list or array of ranges of integers?

E.g. suppose I have: 

my @numbers=(3,4,5,6,9,10,12,14,15,16,17);

I would like a way to determine that the ranges of numbers present are:

3-6,9-10,12,14-17

I know I can go through it with a For loop checking to see if we've hit a gap between two array elements, etc. But before I do that, I thought I'd see if there was some compact notation or core functionality that would accomplish this.

I'd prefer not to have to load any non-core libraries. I'm using Cygwin Perl 5.22.

Thanks.

Upvotes: 1

Views: 1001

Answers (3)

SSilk
SSilk

Reputation: 2502

OK, after messing around with this for a few minutes, the following seems to be working fairly well on a few quick test sets I tried. If anyone has any thoughts on this method, I'd appreciate it. 

use strict;
use warnings;
my @numbers=(-7,-3,-2,-1,3,4,5,6,9,10,12,14,15,16,17);

my @ranges=();
my $start;
$start=$numbers[0];
for(my $i=0; $i<@numbers; $i++){
    if($numbers[$i]>$numbers[$i-1]+1){

        push @ranges, ($start == $numbers[$i-1] ? $start : $start.":".$numbers[$i-1]);
        $start=$numbers[$i];
        print "New start: ".$numbers[$i]."\n";
    }
}
push @ranges, ($start == $numbers[@numbers-1] ? $start : $start.":".$numbers[@numbers-1]);

print join(",",@ranges)."\n";

Upvotes: 0

ikegami
ikegami

Reputation: 385764

my @ranges;
for (@numbers) {
   if (@ranges && $_ == $ranges[-1][1]+1) {
      ++$ranges[-1][1];
   } else {
      push @ranges, [ $_, $_ ];
   }
}

say join ',', map { $_->[0] == $_->[1] ? $_->[0] : "$_->[0]-$_->[1]" } @ranges;

Upvotes: 7

Sinan &#220;n&#252;r
Sinan &#220;n&#252;r

Reputation: 118128

#!/usr/bin/env perl

use strict;
use warnings;

use autouse 'YAML::XS' => 'Dump';

use Const::Fast;
use Graph::Undirected;
use List::Util qw( min max shuffle );
use Test::More;

const my %I => (in => 0, out => 1);

my @cases = (
    [[shuffle 3 .. 6, 9 .. 12, 14 .. 17] => [[3, 6], [9, 12], [14, 17]]],
    [[shuffle 3 .. 6, 9 .. 12, 14 .. 17, 21] => [[3, 6], [9, 12], [14, 17], [21]]],
);

for my $case ( @cases ) {
    is_deeply(
        spans($case->[$I{in}]),
        $case->[$I{out}],
        Dump($case->[$I{in}]) . ' = ' . Dump($case->[$I{out}])
    );
}

done_testing;

sub spans {
    my $sequence = shift;
    my $g = Graph::Undirected->new;

    $g->add_vertex($_) for @$sequence;
    $g->has_vertex($_ + 1) and $g->add_edge($_, $_ + 1) for @$sequence;

    return [
        sort { $a->[0] <=> $b->[0] }
        map $_->[0] == $_->[1] ? [ $_->[0] ] : $_,
        map [min(@$_), max(@$_)],
        $g->connected_components
    ];
}

Output:

$ prove -v spans.pl 
ok 1 - ---
# - 9
# - 4
# - 10
# - 14
# - 6
# - 5
# - 3
# - 15
# - 12
# - 17
# - 11
# - 16
#  = ---
# - - 3
#   - 6
# - - 9
#   - 12
# - - 14
#   - 17
# 
ok 2 - ---
# - 17
# - 16
# - 12
# - 11
# - 6
# - 9
# - 10
# - 5
# - 3
# - 4
# - 21
# - 14
# - 15
#  = ---
# - - 3
#   - 6
# - - 9
#   - 12
# - - 14
#   - 17
# - - 21
# 
1..2
ok
All tests successful.
Files=1, Tests=2,  1 wallclock secs ( 0.04 usr  0.01 sys +  0.25 cusr  0.02 csys =  0.32 CPU)
Result: PASS

Upvotes: 1

Related Questions