Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Union of overlapping numeric intervals

by onlyIDleft (Scribe)
on Dec 30, 2013 at 21:11 UTC ( #1068776=perlquestion: print w/replies, xml ) Need Help??

onlyIDleft has asked for the wisdom of the Perl Monks concerning the following question:

I have three lists (each of the entry is a string of letter:number-number) like so:

List1

a:10-34 b:9-12 c:12-24 e: 1-9

List 2

a:1-8 a: 19-24 b:2-6

List3

a:7-11 d:9-23 e: 12-23

The final answer should look like so:

a:1-34 b:2-6 b:9-12 c:12-24 d:9-23 e: 1-9 e: 12-23

Thank you Exalted Monks! Wishing you all a HNY 2014

Replies are listed 'Best First'.
Re: Union of overlapping numeric intervals
by thezip (Vicar) on Dec 30, 2013 at 21:28 UTC

    With a little bit of front end work with your data, this should be something Set::IntSpan can handle, (see especially the 'Set operations' section.)


    *My* tenacity goes to eleven...
Re: Union of overlapping numeric intervals
by atcroft (Abbot) on Dec 30, 2013 at 22:50 UTC

    Here is a one-liner that provides an example of parsing of lists similar to those you provide into individual letter:number ranges:

    perl -Mstrict -Mwarnings -le 'my @l = ( q{a:10-34 b:9-12 c:12-24 e: 1- +9}, q{a:1-8 a: 19-24 b:2-6}, q{a:7-11 d:9-23 e:12-23} ); foreach my $ +m ( @l ) { foreach my $n ( $m =~ m/([a-z]:\s*\d+(?:\s*-\s*\d+))/ig ) +{ $n =~ s/\s+//g; print $n; } }'

    Here is a one-liner that provides an example of parsing a key and value or range to get the key, starting and ending values (or repeats the starting value as the ending value, if there is only one value present:

    perl -Mstrict -Mwarnings -le 'my $str = q{a:1}; my %f; $str =~ m/([a-z +]):(\d+)(?:-(\d))?/; my ( $k, $starting, $ending ) = ( $1, $2, define +d $3 ? $3 : $2 ); print $k; print $starting; print $ending;'

    Here is a one-liner that provides an example of filling in a hash with values in a range (the Data::Dumper code present only to verify that the values were set:

    perl -Mstrict -Mwarnings -MData::Dumper -le '$Data::Dumper::Sortkeys = + 1; my %range = ( start => 1, end => 9, ); my %f; foreach my $i ( $ra +nge{start} .. $range{end} ) { $f{$i}++; } print Data::Dumper->Dump( [ + \%f, ], [ qw( *f ) ] );'

    Here is a one-liner that takes a hash with values and loops through, to determine the consecutive ranges present:

    perl -Mstrict -Mwarnings -le 'my %g = ( 1 => 1, 2 => 2, 3 => 2, 4 => 2 +, 6 => 1, 7 => 1, 8 => 1, 12 => 1, ); my @h = sort { $a <=> $b } keys + %g; my $sv; my $ev; while ( scalar @h ) { my $v = shift @h; if ( ! d +efined $sv ) { $sv = $v; } if ( ! defined $ev ) { $ev = $v; } my $i = + 1; while ( scalar @h and $h[0] == $sv + $i ) { $i++; $ev = shift @h; + } if ( $sv == $ev ) { print $sv; } else { print $sv, q{ - }, $ev; } +$sv = undef; $ev = undef; }'

    With all of the examples above, there should be enough, with the addition of a small amount of code, to do what you desire. If not, then you might want to refocus your study of perl on the areas you still find yourself weakest in.

    Please comment in the thread if you have any questions.

    Hope that helps.

Re: Union of overlapping numeric intervals
by davido (Cardinal) on Dec 30, 2013 at 21:39 UTC

    I'm sure that in the 2.5 years you've been posting here you have learned that we need to know what you've tried, and how it's failing. Showing your code is an important component of obtaining help in getting past the parts you're having trouble with.


    Dave

Re: Union of overlapping numeric intervals
by Lennotoecom (Pilgrim) on Dec 31, 2013 at 03:35 UTC
    $l .= $_ foreach <DATA>; while($l =~s/(\w):\s?(\d+)-(\d+)//){ $h{$1}{$_} = 1 for ($2 .. $3); } for $k (sort keys %h){ print "\n$k: "; for (sort {$a <=> $b} keys %{$h{$k}}){ print "$_ " if $h{$k}{$_-1} == 0; print "- $_ " if $h{$k}{$_+1} == 0; } } __DATA__ a:10-34 b:9-12 c:12-24 e: 1-9 a:1-8 a: 19-24 b:2-6 a:7-11 d:9-23 e: 12-23

      I refactored your script into one that illustrates what's going on a bit more clearly. It also runs under use strict and use warnings. It separates the operations into three functions named make_sets, make_ranges and print_ranges. Feedback is welcome.

      use strict; use warnings; print_ranges(make_ranges(make_sets(<DATA>))); exit 0; sub make_sets { my @lists = @_; my %set_by; # Hash of sets of integers by labels for my $list (@lists) { while ($list =~ m/(\w+)\s*:\s*(\d+)(?:\s*-\s*(\d+))?/ag) { my $label = $1; my $start = $2; my $end = $+; for my $integer ($start .. $end) { $set_by{$label}{$integer} = 1; } } } return \%set_by; } sub make_ranges { my $set_by = shift; my %ranges_by; # Hash of arrays of integer ranges by labels for my $label (keys %$set_by) { my $index = 0; for my $integer (sort { $a <=> $b } keys %{ $set_by->{$label} +}) { if (not exists $set_by->{$label}{$integer - 1}) { $ranges_by{$label}[$index]{START} = $integer; } if (not exists $set_by->{$label}{$integer + 1}) { $ranges_by{$label}[$index++]{END} = $integer; } } } return \%ranges_by; } sub print_ranges { my $ranges_by = shift; my @ranges; for my $label (sort keys %{ $ranges_by }) { for my $range (@{ $ranges_by->{$label} }) { my $start = $range->{START}; my $end = $range->{END}; push @ranges, $start == $end ? "$label:$start" : "$label:$start-$end +"; } } print join(' ', @ranges) . "\n"; } __DATA__ a:10-34 b:9-12 c:12-24 e: 1-9 a:1-8 a: 19-24 b:2-6 a:7-11 d:9-23 e: 12-23 a:35 e : 20 - 28 foo:42

      This prints…

          a:1-35 b:2-6 b:9-12 c:12-24 d:9-23 e:1-9 e:12-28 foo:42
      

      Jim

Re: Union of overlapping numeric intervals
by 2teez (Vicar) on Dec 30, 2013 at 21:29 UTC

    hi,
    ..The final answer should look like so:..
    And how will you get that done? What have you done so far?
    Please check How do I post a question effectively?

    If you tell me, I'll forget.
    If you show me, I'll remember.
    if you involve me, I'll understand.
    --- Author unknown to me
      I am willing to make an exception if the OP really does want the type of answer that thezip provided.
      Bill

        ..I am willing to make an exception if the OP really does want the type of answer that thezip provided...
        And how can you tell?
        The crystal ball is broken... tell the OP to check back in the new year!

        If you tell me, I'll forget.
        If you show me, I'll remember.
        if you involve me, I'll understand.
        --- Author unknown to me
Re: Union of overlapping numeric intervals
by Anonymous Monk on Dec 31, 2013 at 17:23 UTC

    What is a:1-5 union a:6-10? Is it a:1-10 as the other monks have assumed? Or is "a:1-5 a:6-10" a better answer? (In other words, are these real or integral intervals?)

    Also, what is a:1-5 union a:5-10? a:1-10 or "a:1-5 a:5-10"? (Are these open or closed intervals?)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1068776]
Approved by ww
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (8)
As of 2020-10-28 09:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (260 votes). Check out past polls.

    Notices?