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

Question

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)

I’m voting to close this question because it shows no effort — Pynchia, Nov 28 '20 at 05:35
How so? Would it show effort if I present my own code that doesn't work for all cases? Is this problem actually easy? — lambduh, Nov 28 '20 at 05:51
Updated my post with my draft code. It works for most cases, I don't know what I'm missing in my approach, but I hope this shows some effort. — lambduh, Nov 28 '20 at 06:12

score 0 · Answer 1 · answered Dec 08 '20 at 15:58

If the distance didn't change that doesn't mean it's impossible, you could have just jumped over the point and made it to the other side with the same distance, imagine L=2, R=1, S=3, G=2, you start distance 1 from goal, jump left (still distance 1) then jump right and win. What you need to check is whether you have gone in a loop and ended up at a location you have already tried before. You can either keep track of these locations (say in a set) or do some math ahead of time and figure out how many Ls and Rs it takes before you have definitely looped (probably not intended to figure this out).

score 0 · Answer 2 · answered Dec 09 '20 at 12:02

F=int(input())
S=int(input())
G=int(input())
L=int(input())
R=int(input())


L*=-1
Fl=1-L
Fr=F-R
h0=set()
n=0
while True:
    if   S<G:
        S+= R if S<=Fr else L
    elif G<S:
        S+= L if Fl<=S else R
    else:
        print(n)
        break
    if S in h0:
        print('not possible')
        break

    h0.add(S)
    n+=1

IoaTzimas · Accepted Answer · 2020-12-13T08:50:49.800

Mathematically this problem means that we are looking for integer solutions (for x and y) of the following equation:

x * R - y * L = G - S

we can start by creating a function to check if there is a solution quickly:

def path(S, G, F, L, R):
    x=0
    while True:
        y = (x * R - G + S) / L
        if y>=0 and int(y)==y:
            return(x,y)
        else:
            x+=1

This will work if there are solutions, but not if they are not. It can be proved mathematically that there is no solution when L devides R but not G-S. Here is the proof:

If R mod L =0 (L devides R) (G - S)/L != 0 (L doesn't devide G-S)

then by deviding the whole equation (x * R - y * L = G - S) by L we take:

x * R/L - y = (G - S)/L <=>

y= (x * R/L) - (G - S)/L

Now, we want y mod 1 = 0 (means that y is integer) for x mod 1 =0 (x integers). Using common modulo operations we take:

y mod 1 = [(x * R/L) - (G - S)/L] mod 1 =

[(x * R/L) mod 1 - ((G - S)/L) mod 1] mod 1 =

[(x mod 1 * (R/L) mod 1) mod 1 - ((G - S)/L) mod 1] mod 1 =

[(x mod 1 * 0) mod 1 - ((G - S)/L) mod 1] mod 1 =

[((G - S)/L) mod 1] mod 1

This cannot be 0 if L doesn't devide G-S which eventally means that there are no pair of integers x,y that can satisfy the original condition.

Programatically this means for our code, the following additions:

def path(S, G, F, L, R):
        if R%L==0 and (G-S)%L != 0 :
            return 'No solutions'
        x=0
        while True:
            y = (x * R - G + S) / L
            if y>=0 and int(y)==y:
                return(x,y)
            else:
                x+=1

I don;t know if mathematically we can prove that the above if is the only exception, it can probably be proved with some more modulo operations. Programatically we can add some clock in our code so that if there are no solutions, which means that it will go to infitive loop, we can return False after some time. Here is how we can do this:

How would I stop a while loop after n amount of time?

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

3 Answers3