How to find an element with the minimum number of steps

user_2336081 0
Viewed 429

How can I count the minimum steps to get to a specific index counting forward and backward?

The list is:

content = [1, 2, 3, 4, 5]

If I start from index 0 and want to know how many steps to get to the number 4 iterating forwards I'll get 3, because:

#0 #1 #2 #3
[1, 2, 3, 4, 5]

But I also want to know it backward, like:

#0       #2 #1
[1, 2, 3, 4, 5]

In the example above the minimum amount of steps is 2

Another example

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

 #1   #2   #3   #4   #0
["A", "B", "C", "D", "E"]
# Moving forward I'll start from "A" again until reache "D"

                #1   #0
["A", "B", "C", "D", "E"] # Moving backwards...

In the example above the minimum amount of steps is 1

Note: the target element is unique.

algorithm python
7 Answers

You could do:

len(content) - content.index(4)

Because content.index(4) finds the "forward" index, and then the "backward" index equals the number of elements from the element 4 to the end of the list, which is the same as all of them minus the first content.index(4).

As noted in the comments, this finds the index of the first occurrence in the list. In order to find that of the last (i.e. first from the end), you might do:

content[::-1].index(4) + 1

Example:

>>> content = ['a', 'b', 'c', 'b']
>>> len(content) - content.index('b')
3
>>> content[::-1].index('b') + 1
1
user_61174260

It seems to me that this is a modulus problem:

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

length = len(content)

difference = content.index(to_find) - start_index

print(min(difference % length, -difference % length))

Note that we only search content once, unlike some solutions, including the currently accepted one, which search content twice!

user_57712690 
def minimal_steps(lst: list, num: int, start: int = 0):
    pos = lst.index(num)
    return min(abs(pos - start), len(lst) - abs(pos - start))

EDIT: update answer since the question updated.

user_5728020

No for loops solution:

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

c2 = content*2
forward = c2[start_index:].index(to_find)
backward = c2[::-1][len(content)-start_index-1:].index(to_find)

print('minimum steps:', min(forward, backward))
user_85058170

Assuming the target element is always present in the array:

content = ["A", "B", "C", "D", "E"]
start_index = 4 # "E"
to_find = "D"

end_index = content.index(to_find)
d = end_index - start_index
forward  = d if d>=0 else len(content) + d
backward = -d if d<=0 else len(content) - d
print(min(forward, backward))
user_127639540

Here is a simple method that offsets the list first and uses the start list.index() method:

content = [1, 2, 3, 4, 5]
start_index = 0
to_find = 4

temp = content[start_index:] + content[:start_index]

print(temp.index(to_find))           # Forward
print(temp[::-1].index(to_find) + 1) # Backward

Output:

3
2

For example #2:

content = ["A", "B", "C", "D", "E"]
start_index = 4
to_find = "D"

temp = content[start_index:] + content[:start_index]

print(temp.index(to_find))           # Forward
print(temp[::-1].index(to_find) + 1) # Backward

Output:

4
1
user_135524700

Simply decrement your index instead of incrementing it. Python lists support negative indexing

content = [1, 2, 3, 4, 5]
end_element = 4

i = 0
count = 0
while content[i] != end_element:
    i -= 1 
    count += 1

print(count) # 2

Of course, this leaves the possibility of an IndexError: list index out of range when the end_element is not in your list, but you can handle that error pretty easily.

user_8439530
Related