Program calculates the shortest route from point, to line, then to second point. Also I need to say how long is from the start of the line, to where point crosses. My code so far:
from math import sqrt
numbers_total = []
numbers_canal = []
first_triangle_longest_side_length = 300 #defining the variabledef first_triangle(first_triangle_longest_side_length):calculation_one = sqrt(first_triangle_longest_side_length)first_triangle_bottom_side_length = calculation_one - sqrt(300)def second_triangle(canal_length_left):canal_length_left = canal_length_left ** 2calculation_two = canal_length_left + 500 ** 2second_triangle_longest_side_length = sqrt(calculation_two)while True:first_triangle_longest_side_length = first_triangle_longest_side_length + 0.01first_triangle(first_triangle_longest_side_length)canal_length_left = 1000 - first_triangle_bottom_side_lengthsecond_triangle(canal_length_left)if first_triangle_longest_side_length == 1044.03:breaktotal_distance = first_triangle_longest_side_length + second_triangle_longest_side_lengthnumbers_total.append(total_distance)numbers_canal.append(first_trangle_bottom_side_length)minimal_total_distance = min(numbers_total)
number_on_the_list = numbers_total.index(minimal_total_distance)
print "The distance of the shortest route is: " + "%.1f" % minimal_total_distance
print "The distance of the canal from point A is: " + "%.1f" % numbers_canal[number_on_the_list]
However, it gives the error:
line 19, in <module>canal_length_left = 1000 - first_triangle_bottom_side_length
NameError: name 'first_triangle_bottom_side_length' is not defined
Any ideas?
For those interested, here is the problem: Cambridge February Computing Competition
You are taking a very brute-force approach; it works, but could be much more efficient Edit: I take it back; your math is incorrect too. I will correct it in a new post.
Here is a more analytic way to do it:
TOWER_DIST = 300
CANAL_LEN = 1000
FIRE_DIST = 500#
# express the problem as a function
#
def path_length(dist_a):"""Given distance in meters from A along the canal,return total path length"""leg_a = (TOWER_DIST**2 + dist_a**2) ** 0.5leg_b = ((CANAL_LEN - dist_a)**2 + FIRE_DIST**2) ** 0.5return leg_a + leg_b#
# find x such that path_length(x) is minimized
## (the easy way:
# import scipy.optimize
# result = scipy.optimize.minimize(path_length, CANAL_LEN * 0.5)
# best_dist = result.x[0] # => 375.00092001
# best_length = path_length(best_dist) # => 1280.6248
#
# but because this is a competition we will avoid add-on modules)def deriv(f, delta=0.01):"""Return a function which is a numerical first derivative of f"""def df(x):a, b = f(x - delta), f(x + delta)return (b - a) / (2. * delta)return dfdef newton_root(f, initial_x, tolerance=0.01, max_tries=1000):"""Use Newton-Raphson method to find x such that abs(f(x)) <= tolerance"""df = deriv(f)x = initial_xfor try_ in range(max_tries):err = f(x)if abs(err) <= tolerance:# found a solutionreturn xelse:# find next value for xx -= err / df(x)else:raise ValueError("newton_root fails to converge for initial_guess = {}".format(initial_x))# By inspection, path_length is a smooth upward curve (ie a U-shape)
# on 0 .. CANAL_LEN; minimum occurs where first derivative is 0
best_dist = newton_root(deriv(path_length), CANAL_LEN * 0.5, 0.00001) # => 374.9999
best_length = path_length(best_dist) # => 1280.62484# return results to nearest 0.1 meter
print("{:0.1f} {:0.1f}".format(best_dist, best_length))
If you play with this and think about it a while, you should realize that the shortest path is always such that the angles between leg_a and the canal and between the canal and leg_b are identical; if you think of the canal as a mirror, the shortest path is to run straight to the fire's reflection in the mirror.
This allows us to reduce the problem to a simple pair of similar triangles,
# TOWER_DIST / best_dist == (TOWER_DIST + FIRE_DIST) / CANAL_LEN
best_dist = TOWER_DIST * CANAL_LEN / (TOWER_DIST + FIRE_DIST)best_length = ((TOWER_DIST + FIRE_DIST)**2 + CANAL_LEN**2) ** 0.5