Collapse

collapse.py

from typing import List, Tuple

def calc_overload(out: List[int], ins: List[int]) -> List[int]:
    out1, out2 = out[0], out[1]
    in1, in2 = ins[0], ins[1]
    if out1 <= in1 < out2 < in2:   # Case right overlap: [1, 50] with [32, 60]
        return [out1, in2]
    if out1 <= in1 < out2 >= in2:   # Case inside: [1, 50] x [20, 40]
        return [out1, out2]
    if in1 < out1 < in2:  # left overlap and full overlap: 1) [20, 30] x [10,25] and [20, 30] x [10, 40]
        return [in1, out2] if in2 < out2 else ins
    return ins  # # All others is disjunt


def is_overload(out: List[int], ins: List[int]) -> bool:
    out1, out2 = out[0], out[1]
    in1, in2 = ins[0], ins[1]

    # # Can be done in one line, this is separated to explain
    # if out1 <= in1 < out2 < in2 or out1 < in1 < out2 > in2 or in1 < out1 < in2:
    #     return True

    if out1 <= in1 < out2 < in2:   # Case right overlap: [1, 50] with [32, 60]
        return True
    if out1 <= in1 < out2 >= in2:   # Case inside: [1, 50] x [20, 40]
        return True
    if in1 < out1 < in2:  # left overlap and full overlap: 1) [20, 30] x [10,25] and [20, 30] x [10, 40]
        return True
    return False  # All others is disjunt

def check_overload_all(out: List[List[int]], inside: List[int]) -> Tuple[int, List[int]]:
    if out == []:
        return 0, inside
    for i, out_i in enumerate(out):
        if is_overload(out_i, inside):
            return i, calc_overload(out_i, inside)
    return len(inside), inside

def collaps_single(*lists: List[int]) -> List[List[int]]:
    new_lists = []  # type: List[List[int]]
    for i in lists:
        index, to_add = check_overload_all(new_lists, i)
        if index >= len(new_lists):
            new_lists.append(to_add)
        else:
            new_lists[index] = to_add
    return new_lists

def collaps(*lists: List[int]) -> List[List[int]]:
    res1 = collaps_single(*lists)
    res2 = collaps_single(*res1)
    while len(res1) != len(res2):
        res1, res2 = res2, collaps_single(*res2)
    return res1

def tests() -> None:
    a = [1,50]
    b = [75,150]
    c = [25,42]
    d = [120,149]
    e = [35,55]
    f = [60, 100]
    assert collaps(a, b, c, d, e, f) == [[1, 55], [60, 150]]


    x = [135098,19854736]
    y = [135098,41639553]
    z = [11818998,12587339]
    assert collaps(x, y, z) == [[135098, 41639553]]

    assert(collaps(a, b, c, d, e, f, x, y, z)) == [[1, 55], [60, 150], [135098, 41639553]]

def test_n(n, minim, maxim):
    # This is dynamically typed because mypy don't infer x as list and don't let to index
    from random import randint
    all_l = [[randint(minim, maxim), randint(minim, maxim)] for _ in range(n)]
    all_l = list(map(lambda x: x if x[0] < x[1] else [x[1],x[0]], all_l))
    return collaps(*all_l)

if __name__ == "__main__":
    tests()
    # test_n(5, 0, 2000000)
    # test_n(1000000, 0, 100000)