Finding minimum number of steps to reach (x,y) from (1,1) : we can increment number by using condition (x,y+x)or(x+y,x)

Javeed 0
Viewed 62
a = 1
b = 1

x=int(input())
y=int(input())

def minsteps(x,y):
    if x==a and y==b:
        print(1)
        return 1
    if x<a and y<b:
        print(2)
        return 20
    
    count = 1 + min(minsteps(x,x+y),minsteps(x+y,y))
    return count

print(minsteps(x,y))

Test case:

(3,2) (input)
2 (output)

Explanation:

1:(1,1+1) #at first step
2:(1+2,2) #at second step
dynamic recursion dynamic-programming python
2 Answers

Problem statement is quite unclear and you do not really ask a clear question... Of course we understand you get an infinite loop, for the simple reason you don't have a real "breaking" statement, in most cases.

Generally speaking, I don't understand the algo goal: you start at (1,1) and you want to reach (x,y) by only adding y on x and/or x on y ? If that's it, I really don't see how it can behave properly...

Let's say you have x=10 and y=63 Then you can go to (1+63, 1) = (64,1) or to (1,63+10) = (1,73). Regardless of the case you already overpass your initial target which is (10,63). That's basically why you never enter your two if statements.

Can you please clarify ?

EDIT

Considering your precision, the first thing for me is to be able to state if there are still possible improvements at a reached position (x,y) to achieve a target (xt,yt). This function (very explicited) is a proposal for that:

def improvement_possible(xt, yt, x, y):
    x_possible = True
    y_possible = True
    if x >= xt and y >= 0:
        x_possible = False
    if x <= xt and y <= 0:
        x_possible = False
    if y >= yt and x >= 0:
        y_possible = False
    if y <= yt and x <= 0:
        y_possible = False
    return x_possible, y_possible

Then we can recursively try all paths, while storing (1) the path sequences and (2) the reached positions:

def find_path(xt, yt, x, y, path_sequences: list, reached: list, level=0):
    print((level)*"-" + f"We are at ({x},{y})")
    new_x = x + y
    new_y = y + x

    # Check if improvement is possible
    dirs_to_test = ["x", "y"]
    x_possible, y_possible = improvement_possible(xt, yt, x, y)
    if not (x_possible or y_possible):
        print(level*"-" + "======== No improvement possible at this point, we must stop ========")
        return
    if not x_possible:
        print(level*"-" + "=> No improvement possible on X at this point")
        dirs_to_test = ["y"]
    if not y_possible:
        dirs_to_test = ["x"]
        print(level*"-" + "=> No improvement possible on Y at this point")

    for new_dir in dirs_to_test:
        print(level*"-" + f"Increasing on direction {new_dir}...")
        path_sequences.append(path_sequences[-1] + [new_dir])
        new_pos = (new_x, y) if new_dir =="x" else (x, new_y)
        reached.append(new_pos)
        find_path(xt, yt, new_pos[0], new_pos[1], path_sequences, reached, level+1)

For a very simple problem whose target is (10,12) with starting point (4,4) it gives the following for reached list:

[(8, 4), (12, 4), (12, 16), (8, 12), (20, 12), (4, 8), (12, 8), (12, 20), (4, 12), (16, 12)]

Hence 10 possible paths that you can check are correct by hand. By the way, you can remark the symetry of it, which makes sense considering the starting point.

When it comes to which one is better, well, it's up to your criteria. Is (8, 12) better than (12, 8) for instance

Limtorak0

this problem seems very familiar to one that I worked on while completing the google foobar challenge.
this program is the most efficient was to find the solution of x, y...

    def solution(x, y): #finds the solution for inputs x, y
        count = 0
        while x > 1 or y >1:
            if y > x:
                y -= x
            elif x > y:
                x -= y
            else: #solution is impossible
                return 0
            count += 1
       return count;
CR1300
Related