How To Find The Longest Smallest Path?

A frog wants to cross a river. There are 3 stones in the river she can jump to. She wants to choose among all possible paths the one that leads to the smallest longest jump. Ie. e

Solution 1:

You can simplify the three loops by using itertools.permutations on a range. That will return a three-tuple if you pass it a range of length 3.

As for keeping track of the path, I think it would be much easier if you used an actual if statement to compare the largest jump lengths from each path to the best you've seen so far, rather than using min. In an if, you can also save additional information (such as the path that has the smallest largest jump) at the same time you're saving that jump's length.

def longestJump(x, y):
    best_jump =10# infinity
    best_path = ()
    for i, j, k in itertools.permutations(range(3)):           
        jump0 = x[i]                                      # shore to i
        jump1 = sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2)     # i to j
        jump2 = sqrt((x[j]-x[k])**2 + (y[i]-y[j])**2)     # j to k
        jump3 = 10 - x[k]                                 # k to far shore
        longest = max(jump0, jump1, jump2, jump3)
        if longest < best_jump:
            best_jump = longest
            best_path = (i, j, k)
    return best_jump, best_path

This always expects the path to use all three stones. If that's not required, you may want to iterate over permutations of the each subset of the stones. I'm not sure if there's a particularly easy way to do that, but you could try combining itertools.combinations and the permutations code above.

Solution 2:

You don't need to take the square-root except for the final result. Just compute "distance squared" and compare with that.

Not sure what you are calling "round" either. That would potentially create a bug.

Also, don't you need to skip all cases of "i == j" from the inner loop?

deflongestJump(x, y):
        best = 10for i inrange(0,3):           
            for j inrange(0,3):  
                for k inrange(0,3):                
                   # first jump from shore to a stone
                   dist = x[i] 
                   # second jump between stones
                   dist = max(dist, (x[i]-x[j])**2 + (y[i]-y[j])**2)
                   # third jump between stones
                   dist = max(dist, (x[i]-x[k])**2 + (y[i]-y[k])**2) 
                   dist = max(dist, x[j]-x[k])**2 + (y[j]-y[k])**2)
                   # last jump from a stone to the opposite shore 
                   dist = max(dist, 10 - x[j])
                   best = min(dist, best)
        return math.sqrt(best)