find the minimum range that includes all angles in a list

Question

I have a list of sorted values that represents angles (in degrees), all in the range [0,360)

My goal is to find the best range (minimum range) that fit all the angles in the list.

Some examples:

• Given the list angles = [0,1,2,10,20,35] the answer would be (0,35).

• Given the list angles = [10,20,340,355], due to the circular nature of the values, the answer would be (340,20).

My current script works as follow:

MAX_ANGLE = 360

def get_best_range(angles):

    number_of_angles = len(angles)

    # Append the list of angles with the same angles plus 360 (max value)
    angles = angles + [angle + MAX_ANGLE for angle in angles]

    # Create a list of all possible ranges
    possible_ranges = [(angles[i], angles[i+number_of_angles - 1]) for i in range(number_of_angles)]

    # Find the best range (minimum range)
    best_range = min(possible_ranges, key = lambda ang_range: ang_range[1] - ang_range[0])

    return best_range[0], best_range[1]%MAX_ANGLE

Well, that is my best approach so far and it works in O(n), which is good, but just seems to me that there might be a better way to do it in python. Maybe some tool to work with circular values? I always have a bit of a hassle when working with angles or other circular values.

Answer 1

That one liner should do the trick:

max(zip(angles, angles[1:] + [360+angles[0]]), key = lambda x: x[1]-x[0])

(you can change the answer afterwards to values smaller than 360 if needed)