Как найти самый длинный путь?

Question

Лягушка хочет пересечь реку.

В реке, в которую она может прыгать, есть 3 камня.

Она хочет выбрать среди всех возможных путей тот, который ведет к наименьшему длинному прыжку.

Т.е. каждый из возможных путей будет иметь один прыжок, который является самым длинным. Ей нужно найти путь, где этот самый длинный прыжок самый маленький.

2 берега расположены в 10 друг от друга и параллельны оси y.

Каждое положение камня задается списком x = [x1, x2, x3] положений x и y = [y1, y2, y3] положений y.

Возвратите как самый длинный прыжок на этом пути (округленный до ближайшего целого), так и сам путь через список индексов в списках x и y камней на пути.

Вот мой код на Python, чтобы найти самый длинный прыжок.

Как бы я отслеживал сам путь?

И мой код выглядит неуклюжим с 3 вложенными циклами, есть ли лучший/более элегантный способ написать этот код?

def longestJump(x, y): 
     best = 10 
     for i in range(0,3):   
      for j in range(0,3): 
       for k in range(0,3):     
        # first jump from shore to a stone 
        dist = x[i] 
        # second jump between stones 
        dist = max(dist, round(math.sqrt((x[i]-x[j])**2 + (y[i]-y[j])**2))) 
        # third jump between stones 
        dist = max(dist, round(math.sqrt((x[i]-x[k])**2 + (y[i]-y[k])**2))) 
        dist = max(dist, round(math.sqrt((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 best 

Answer 1

Вам не нужно брать квадратный корень, за исключением конечного результата. Просто вычислите «квадрат расстояния» и сравните с этим.

Не уверен, что вы называете «круглым». Это может создать ошибку.

Кроме того, вам не нужно пропускать все случаи «i == j» из внутреннего цикла?

def longestJump(x, y): 
     best = 10 
     for i in range(0,3):   
      for j in range(0,3): 
       for k in range(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) 

Answer 2

Вы можете упростить три петли с помощью itertools.permutations на range. Это вернет три кортежа, если вы передадите ему range длины 3.

Что касается отслеживания пути, я думаю, было бы намного проще, если бы вы использовали фактическое заявление if, чтобы сравнить наибольшую длину прыжка от каждый путь к лучшему, который вы видели до сих пор, вместо того, чтобы использовать min. В if вы также можете сохранить дополнительную информацию (например, путь с наименьшим наибольшим скачком), в то же время вы сохраняете длину этого перехода.

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 

Это всегда предполагает путь для использования всех трех камней. Если это не требуется, вы можете захотеть итерации над перестановками каждого подмножества камней. Я не уверен, есть ли особенно простой способ сделать это, но вы можете попробовать комбинировать itertools.combinations и код permutations выше.