Given an arbitrary range of 1
to F
and a starting point S
with an ending point G
such that the only directions we could go is L
Left steps and R
Right Steps (also arbitrary), create a general solution that will return the number of steps it would take to go from S
to R
if it is possible otherwise return not possible
.
You are bound to the range [1, F]
which means that you cannot move L
or R
steps if the next move will be more than F
or less than 1
Example:
F = 100
S = 2
G = 1
L = 0
R = 1
Output: not possible
F = 10
S = 1
G = 10
L = 1
R = 2
Output: 6
Explanation: [1 -> 3(R) -> 5(R) -> 7(R) -> 9(R) -> 8(L) -> 10(R)]
I've been given this problem in our class and our current topic is binary search and divide and conquer. Here's my approach but this does not solve one hidden case.
F = int(input())
S = int(input())
G = int(input())
L = int(input())
R = int(input())
count = 0
while S != G:
dist = abs(S - G) # Takes the current distance from S to G
if S > G:
if S-L > 0:
S -= L
count += 1
else:
S += R
count += 1
else:
if S+R <= F:
S += R
count += 1
else:
S -= L
count += 1
if dist == abs(S - G): # If distance doesn't change after trying
print("not possible") # a move, conclude that it is not possible.
break
if S == G: print(count)
from Check if there is a Way to get from Point S to Point G in an Arbitrary Range F
No comments:
Post a Comment