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: