CODEWITHSUNDEEP
pythonalgorithm
Saunderfist
Saunderfist

Reputation: 33

Why doesn't this code related to finding common multiples work?

Assignment:

You are choreographing a circus show with various animals. For one act, you are given two kangaroos on a number line ready to jump in the positive direction (i.e, toward positive infinity).

The first kangaroo starts at location x1 and moves at a rate of v1 meters per jump. The second kangaroo starts at location x2 and moves at a rate of v2 meters per jump.

You have to figure out a way to get both kangaroos at the same location at the same time as part of the show. If it is possible, return YES, otherwise return NO.

How I can replace the while m < 1000 line in the given code to extend the search limits.

I executed the given code on Pycharm. I found that no execution. 

x1 = 0
v1 = 3
mul1 = 0              # Multiple of Kangaroo 1
a = []             # Multiples of Kangaroo 1 List
x2 = 4
v2 = 2
mul2 = 0              # Multiple of Kangaroo 2
b = []             # Multiples of Kangaroo 2 List
m = 0
while m < 10000:                    # Limited search
    i = 0
    mul1 += x1 + (i*v1)
    a.append(mul1)
    mul2 += x2 + (i*v2)
    b.append(mul2)
    i += 1
    conj = list(set(a).intersection(b))             # List of common elements
    if len(conj) > 0:                        # Checking if conj has some values
        for x in range(len(conj)):
            print(conj[x])                # Prints common value
        break
    m += 1

I need to get

YES

if I input

0
3
4
2

And I need to get

NO

if I input

0
2
5
3

Upvotes: 3

Views: 234

Answers (2)

molamk
molamk

Reputation: 4116

Solving the 2 equations is actually much faster (and simpler than iterating) as the solution may be arbitrarily far in the future. This runs in O(1) time and space.

def solve(x1, v1, x2, v2):
    if v1 == v2:
        # If same start       -> always together (True)
        # If different start  -> will never meet (False)
        return x1 == x2
    else:
        t = (x2 - x1) / (v1 - v2)
        # Will only meet if the intersection happens in the future
        return t >= 0

def main():
    x1 = 0
    v1 = 3
    x2 = 4
    v2 = 2

    print('YES' if solve(x1, v1, x2, v2) else 'NO')


if __name__ == '__main__':
    main()

Upvotes: 1

Ralf
Ralf

Reputation: 16495

You can solve this problem a simpler way.

Assuming that the roos jump at the same speed (both have the same number of jumps per minute, just each can have different distance per jump), you have the following (in math terms):

x_final = x1 + v1 * num_jumps
x_final = x2 + v2 * num_jumps

Doing some restructuring (in math terms), we get this:

x1 + v1 * num_jumps = x2 + v2 * num_jumps
x1 - x2 = v2 * num_jumps - v1 * num_jumps
x1 - x2 = (v2 - v1) * num_jumps
(x1 - x2) / (v2 - v1) = num_jumps

Now with values

x1 = 0
v1 = 3
x2 = 4
v2 = 2
(x1 - x2) / (v2 - v1) = num_jumps
(0 - 4) / (2 - 3) = num_jumps
(-4) / (-1) = num_jumps
4 = num_jumps

Here num_jumps is positive, so they will meet.

x1 = 0
v1 = 2
x2 = 5
v2 = 3
(x1 - x2) / (v2 - v1) = num_jumps
(0 - 5) / (3 - 2) = num_jumps
(-5) / 1 = num_jumps
-5 = num_jumps

Here num_jumps is negative, so they will never meet.

A Python function to solve this:

def will_they_meet(x1, v1, x2, v2):
    num_jumps = (x1 - x2) / (v2 - v1)
    return 'YES' if num_jumps >= 0 else 'NO'

Note: this code may raise errors if v1 and v2 are equal (ZeroDivisionError) of if the arguments passed to the function are not numbers. You may need to add your try...except blocks to make it more robust.

As you can see, there is no need to generate all the possible positions and no need for a any kind of loop.

Upvotes: 3

Related Questions