Wednesday 9 December 2020

Check if there is a Way to get from Point S to Point G in an Arbitrary Range F

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