Overlap in python

[kj]

In <78d86d92-d373-4163-a418-600a3eb36ab3 at o15g2000yqm.googlegroups.com> Mark Dickinson <dickinsm at gmail.com> writes:

>On Aug 4, 7:15=A0pm, Jay Bird <jay.bird0... at gmail.com> wrote:
>> Hi everyone,
>>
>> I've been trying to figure out a simple algorithm on how to combine a
>> list of parts that have 1D locations that overlap into a non-
>> overlapping list. =A0For example, here would be my input:
>>
>> part name =A0 location
>> a =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A05-9
>> b =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A07-10
>> c =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A03-6
>> d =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A015-20
>> e =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A018-23
>>
>> And here is what I need for an output:
>> part name =A0 location
>> c.a.b =A0 =A0 =A0 =A0 =A0 =A03-10
>> d.e =A0 =A0 =A0 =A0 =A0 =A0 =A0 15-23
>>
>> I've tried various methods, which all fail. =A0Does anyone have an idea
>> how to do this?

>Here's an approach that might work.  Turning it into a sensible
>function and parsing input/massaging output properly are left
>as an exercise.  Blocks that just touch (e.g. (3, 6) then (6, 9))
>are amalgamated;  if this isn't what you want, and they should
>be treated as separate instead, then replace 'Stop' with 'Finish'
>(or any other string that sorts before 'Start').


>input =3D [
>    ('a', (5, 9)),
>    ('b', (7, 10)),
>    ('c', (3, 6)),
>    ('d', (15, 20)),
>    ('e', (18, 23)),
>    ]

># create sorted list of points where an interval is entered or left
>transitions =3D []
>for name, (start, stop) in input:
>    transitions.extend([(start, 'Start', name), (stop, 'Stop', name)])
>transitions.sort()

># scan list, accumulating blocks along the way.
>count =3D 0
>for i, (pt, startend, name) in enumerate(transitions):
>    if startend =3D=3D 'Start':
>        if not count:
>            start =3D pt
>            names =3D []
>        count +=3D 1
>        names.append(name)
>    else:
>        count -=3D 1
>        if not count:
>            print '.'.join(names), "%s--%s" % (start, pt)

Very cool.

kynn