How can I find the least number of segments to get from start point to end point using Python?

Question

So, I have start number, end number and a list of segments.

start = 10
end = 100
li = [(50, 60), (10, 20), (10, 40), (40, 60), (60, 80), (75, 95), (95, 100), (35, 45)]

And I need to find the least number of segments to get from point A to point B. If there are not enough segments, the program should indicate this.

I think that thanks to the illustration it will become clearer what I need.

In addition, I am not allowed to use any libraries or even import's. Of course, the less memory and time is used, the better.

As for me, I've wrote terrible code:

for el in li:
    for el1 in li:
        if el != el1 and el[0] >= el1[0] and el[1] <= el1[1]:
            li.remove(el)

        elif el != el1 and (el[1] == el1[0] or el[0] == el1[1]):
            tmp = (min(el[0], el1[0]), max(el[1], el[1]))

            for el2 in li:
                if el != el2 and el1 != el2 and el2[0] >= tmp[0] and el2[1] <= tmp[1]:
                    li.remove(el2)

However, in my program there are three levels of nested loops, and in the middle of the third there is also remove, so my code do not work quickly and efficiently.

Presumably the end of one segment in the path doesn't need to be exactly the same as the start of the next? For example, you can follow (60,80) then (75,95), because 75<80? If so, then a greedy algorithm should work. If your current position is X, then find the segments (P, Q) with P<=X, and choose whichever one maximises Q. Repeat until you reach your goal. — slothrop
– slothrop, Commented Mar 29, 2023 at 14:23
@slothrop Yes, you are right, the end of one path segment does not have to coincide with the beginning of the next one. But I would like to understand how you can implement this in Python. — Ionnafan
– Ionnafan, Commented Mar 29, 2023 at 14:30

GregoirePelegrin · Accepted Answer · 2023-03-30 06:11:45Z

0

This code, while not being the fastest, should work well:

def n_length_combo(lst, n):
    if n == 0:
        return [[]]

    l = []
    for i in range(0, len(lst)):

        m = lst[i]
        rem_lst = lst[i + 1:]

        remainlst_combo = n_length_combo(rem_lst, n - 1)
        for p in remainlst_combo:
            l.append([m, *p])

    return l


def mergeable(segs):
    if segs[0][0] < segs[1][0] <= segs[0][1] <= segs[1][1]:
        return True
    if segs[1][0] <= segs[0][0] <= segs[1][1] < segs[0][1]:
        return True
    return False


def merger(segs):
    has_grown = True
    while has_grown:
        has_grown = False
        for comb in n_length_combo(segs, 2):
            if mergeable(comb):
                curr_segs = set(segs)
                curr_len = len(curr_segs)
                curr_segs.add((min(comb[0][0], comb[1][0]), max(comb[0][1], comb[1][1])))
                if curr_len < len(curr_segs):
                    has_grown = True
                    segs.append((min(comb[0][0], comb[1][0]), max(comb[0][1], comb[1][1])))


def valid_combo(combo, start, end):
    # Merge segments
    segments = combo[:]
    merger(segments)
    # Verify if start and end are in the segment
    for seg in segments:
        if seg[0] <= start <= seg[1] and seg[0] <= end <= seg[1]:
            return True
    return False


if __name__ == "__main__":
    start = 10
    end = 100
    li = [(50, 60), (10, 20), (10, 40), (40, 60), (60, 80), (75, 95), (95, 100), (35, 45)]
    best_comb = []
    for length in range(5, len(li)):
        for comb in n_length_combo(lst=li, n=length):
            if valid_combo(comb, start, end):
                print(comb)

Here we go through each combinations of segments by increasing length of combination and we check whether or not they are valid. In this example, we print them when they are, but we also could simply add a break statement.

I used help from Geeks for Geeks' Combinations in python without using itertools to generate the combinations without using libraries.

For each combination, we try to merge every segment with each other to create the longest segments possible, and then we try to find a segment which contains the start and the end.

edited Mar 30, 2023 at 6:11

answered Mar 29, 2023 at 15:06

GregoirePelegrin

1,1832 gold badges12 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Ionnafan Over a year ago

There are a lot of loops and also nested loops, assignings and even recursion in your code. It won't work fast, I think.

GregoirePelegrin Over a year ago

I admit that it may not be the fastest nor the prettiest, but it works fine. Although it may not be the fastest, it runs in 0.018s on average to find all the working combinations for your case, and only 0.0087s on average if we stop at the first solution.

Ionnafan Over a year ago

Ok, thanks for your solution, but speed and uncluttered code is still important to me.

GregoirePelegrin Over a year ago

For the sake of curiosity, can you quickly run my and your solution on your end, to get comparable numbers?

Ionnafan Over a year ago

Actually, there are some counterexamples for my code, so I think it doesn't make sense to do that😞.

|

Collectives™ on Stack Overflow

How can I find the least number of segments to get from start point to end point using Python?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related