Three lines clear solution for Create Intervals by rossras - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Three lines solution in Clear category for Create Intervals by rossras

def create_intervals(data):
    """
        Create a list of intervals out of set of ints.
    """
    starts = sorted(i for i in data if i-1 not in data)
    ends = sorted(i for i in data if i+1 not in data)
    return list(zip(starts, ends))


if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert create_intervals({1, 2, 3, 4, 5, 7, 8, 12}) == [(1, 5), (7, 8), (12, 12)], "First"
    assert create_intervals({1, 2, 3, 6, 7, 8, 4, 5}) == [(1, 8)], "Second"
    print('Almost done! The only thing left to do is to Check it!')

Dec. 14, 2018

Comments:

aboutdogs7 on Jan. 14, 2019, 9:36 a.m.
Very beautiful solution! Very short.

maxnrg on Dec. 22, 2019, 9:56 a.m.
nice! could be optimized: ``` def create_intervals(data: Set[int]) -> List[Tuple[int, int]]: """ Create a list of intervals out of set of ints. """ starts = (element for element in data if element - 1 not in data) ends = (i for i in data if i + 1 not in data) return sorted(zip(starts, ends))

maxnrg on Dec. 22, 2019, 9:56 a.m.
... or two-liner :) ``` def create_intervals(data: Set[int]) -> List[Tuple[int, int]]: """ Create a list of intervals out of set of ints. """ return sorted(zip((element for element in data if not element - 1 in data), (element for element in data if not element + 1 in data)))

rossras on Dec. 27, 2019, 6:12 p.m.
Nice to have only one sort. But since sets are unordered collections, if you zip the interval endpoints together before sorting, what guarantee do you have that the correct pairs of endpoints get zipped together? In other words, if you want this: <pre class='brush: python'>>>> create_intervals({1, 2, 3, 4, 5, 7, 8, 12}) [(1, 5), (7, 8), (12, 12)] </pre> Then how do you know you won't get this? <pre class='brush: python'>>>> create_intervals({1, 2, 3, 4, 5, 7, 8, 12}) [(1, 12), (7, 8), (12, 5)] </pre>

maxnrg on Dec. 27, 2019, 6:53 p.m.
it doesn't matter since we iterate twice on the same set - the order of "unordered" set is consistent: <a href="https://stackoverflow.com/questions/12165200/order-of-unordered-python-sets">https://stackoverflow.com/questions/12165200/order-of-unordered-python-sets</a>

rossras on Dec. 28, 2019, 9:49 p.m.
Consistent internal order isn't enough, though. For example, I tried your two-liner on a different set of ints. I should get: <pre class='brush: python'>>>> create_intervals({-1, 0, 1, 12}) [(-1, 1), (12, 12)] </pre> What I actually, get, though, is: <pre class='brush: python'>>>> create_intervals({-1, 0, 1, 12}) [(-1, 12), (12, 1)] </pre> The problem is the internal order of the set. On my machine, <pre class='brush: python'>>>> {-1, 0, 1, 12} {0, 1, 12, -1} </pre> So, when it iterates through {0, 1, 12, -1} to find interval startpoints, it finds 12 then -1. When it iterates through the same ordering of {0, 1, 12, -1} to find interval endpoints, it finds 1 then 12. If you don't sort the startpoints and the endpoints separately before zipping, then zip() puts the wrong pairs of start and end points together, and sorting after the fact doesn't solve the incorrect pairing. What would work, though, is if python sets had not just a consistent internal order, but a sorted internal order. That might be what you end up with for all the small positive ints in checkio's tests. You could simulate sorted internal order by turning the input data into a sorted list first with data = sorted(data). In that case, you could also pick out the interval start and end points much more easily in a single pass through the sorted input data, without membership testing. However, if you have some very long intervals in the input data, it seems like a waste of time to sort all the numbers on the inside of an interval, when all you really need to do is pick out the start and end points and sort them.

maxnrg on Dec. 28, 2019, 10 p.m.
It seems that you found a corner case for this problem. This should be included in the testcases!

maxnrg on Dec. 28, 2019, 10:02 p.m.
``` <h1>v3 - `starts` and `ends` iterators</h1> def create_intervals(data: Set[int]) -> List[Tuple[int, int]]: """ Create a list of intervals out of set of ints. """ data = sorted(data) starts = (element for element in data if element - 1 not in data) ends = (element for element in data if element + 1 not in data) return list(zip(starts, ends)) ``` ``` <h1>v4 - `starts` and `ends` iterators two-liner</h1> def create_intervals(data: Set[int]) -> List[Tuple[int, int]]: """ Create a list of intervals out of set of ints. """ return list(zip(sorted(element for element in data if element - 1 not in data), sorted(element for element in data if element + 1 not in data))) ```

rossras on Dec. 29, 2019, 7:45 p.m.
Bad news about v3 is that since sorted() gives you a list, the average case complexity of "not in" is now O(n) instead of O(1), making (element for element in data if element - 1 not in data) O(n**2) instead of O(n). (See <a href="https://wiki.python.org/moin/TimeComplexity)">https://wiki.python.org/moin/TimeComplexity)</a> However, since you've already done an O(n*log(n)) sort, you can use that to your advantage -- you don't need to check the whole list to see if element+1 and element-1 are in it; you can just check element's neighbors.

Different kind of sets

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!