You are given a list of positive integers. You start at the beginning of the list and your goal is to reach the end of the list.
When you are at a value , you can jump steps to the right or to the left. However, you cannot make a jump that would take you outside the list. You want to reach the end of the list with the smallest possible total length of the jumps.
For example, in the list , the best solution is to first jump steps to the right, then steps to the left, and finally steps to the right. The total length of the jumps is .
In a file listjump.py
, implement a function find_steps
that returns the smallest total length of the jumps The function should return if there is no way to reach the end of the list.
The function should be efficient even if the list is long. The last function call in the code template tests this situation.
def find_steps(numbers): # TODO if __name__ == "__main__": print(find_steps([1, 1, 1, 1])) # 3 print(find_steps([3, 2, 1])) # -1 print(find_steps([3, 5, 2, 2, 2, 3, 5])) # 10 print(find_steps([7, 5, 3, 1, 4, 2, 4, 6, 1])) # 32 numbers = [] for i in range(10**5): numbers.append(1337 * i % 100 + 1) print(find_steps(numbers)) # 100055