[Tutor] overlapping tuples

[Peter Otten]

Narasimharao Nelluri wrote:

> Hi David ,
> Thanks for your feedback. Yes here i am solving Home work from one of my
> assignments.
> please check below i added your comments.
> 
> NNELLURI-M-L13P:google_class nnelluri$ cat overlap.py
> #!/usr/bin/env python3
> 
> 
> def tuple_overlap(old_list,overlap = None):
> 
>   old_list.sort()
>   if overlap is None:
>     overlap = []
>   for fir,sec in zip(old_list,old_list[1:]):
> 
>     if fir[1] >= sec[0] and fir[1] <=sec[1]:=======>Here i am validating
> 2nd element in first variablae is in-between seconds variable if it is
> there is a overlap
>       overlap.append(fir)
> 
>     if sec[0] >= fir[0] and sec[1] <= fir[1]:=====> Here i am checking if
> first element in second variable is in-between second variable , there is
> a oberlap
>       overlap.append(sec)
> 
>   overlap = sorted(overlap)
>   return overlap
> 
> 
> overlaps = tuple_overlap( [(1,10),(15,20),(101,110)] )
> print( "Overlap 1 =", overlaps )
> assert overlaps == []
> 
> overlaps = tuple_overlap( [(1,20),(15,20),(101,110)])
> print( "Overlap 2 =", overlaps )
> assert overlaps ==[(1, 20), (15, 20)]
> 
> overlaps = tuple_overlap( [(1,10),(15,20),(1,10),(1,10),(101,110)])
> print( "Overlap 3 =", overlaps )
> assert overlaps == [(1, 10), (1, 10),(1,10)]
> 
> 
> NNELLURI-M-L13P:google_class nnelluri$
> 
> 
> Please let know if you know correct solution.

I would have to work it out myself ;) but I think I can give you a few 
hints:

If you add some debugging information

>>> tuple_overlap( [(1,10, "a"),(15,20, "b"),(1,10, "c"),(1,10, "d"),
(101,110, "e")])
[(1, 10, 'a'), (1, 10, 'c'), (1, 10, 'c'), (1, 10, 'd')]

you can see that (1, 10, "c") occurs twice. Your code checks adjacent 
tuples, and if three tuples overlap the tuple in the middle may be added 
twice. In this situation you need to ensure that every tuple is added only 
once. 

But not only that:

>>> tuple_overlap([(0, 10), (1, 3)])
[(1, 3)]

Hm, one overlapping tuple? with what? with itself?

If tuple A overlaps with tuple B, tuple B overlaps with A, i. e. instead of 
two independent checks you can use a single one, and add both tuples if 
there is an overlap.

That single check may be easier to implement if you ask yourself the 
opposite question: when do the tuples not overlap?

Also consider [(0, 10), (1, 3), (5, 20)].

Clearly you need to decide what to do if t1 overlaps with t2 and t3, but t2 
not with t2. 

Finally, does your task say something about independent overlaps, e. g. what 
should be returned by

tuple_overlap([(0, 2), (1, 3), (5, 7), (6, 8)])

?