CODEWITHSUNDEEP
algorithmrecursionmemoization
programmerdev
programmerdev

Reputation: 55

Minimum Jumps required from given number to 1

I am trying to solve the problem given below: (I solved it using recursion but I am having a hard time trying to use a cache to prevent a lot of the same steps being recalculated. """ Given a positive integer N, find the smallest number of steps it will take to reach 1.

There are two kinds of permitted steps:

You may decrement N to N - 1. If a * b = N, you may decrement N to the larger of a and b.

For example, given 100, you can reach 1 in five steps with the following route: 100 -> 10 -> 9 -> 3 -> 2 -> 1. """

def multiples(num):
    ret = []
    start = 2
    while start < num:
        if num % start == 0:
            ret.append(num // start)
        start +=1
        if ret and start >= ret[-1]:
            break
    return ret if ret else None

def min_jumps_no_cache(num, jumps=0):
    if num == 1:
        return jumps
    
    mults = multiples(num)
    res = []
    res.append(min_jumps(num - 1, jumps +1))
    if mults:
        for mult in mults:
            res.append(min_jumps(mult , jumps +1))
    return min(res)

Now, I am trying to add a cache in here because of the obvious high runtime of this solution. But I have run into a similar issue before where I am overwriting the cache and I was curious if there is a solution to this.

def min_jumps_cache(num, jumps=0, cache={}):

    if num == 1:
        return jumps
    if num in cache:
        return cache[num]
    
    mults = multiples(num)
    res = []
    
    temp = min_jumps_cache(num - 1, jumps +1, cache)
    res.append(temp)
    if mults:
        for mult in mults:
            res.append(min_jumps_cache(mult , jumps +1, cache))
    temp = min(res)
    cache[num] = min(temp, cache[num]) if num in cache else temp
    return temp

It seems to me the issue here is you can't really cache an answer until you have calculated both its "left and right" solutions to find the answer. Is there something else I am missing here?

Upvotes: 1

Views: 117

Answers (1)

btilly
btilly

Reputation: 46497

Your solution is fine so far as it goes.

However it will be more efficient to do a breadth-first solution from the bottom up. (This can trivially be optimized more. How is an exercise for the reader.)

def path (n):
    path_from = {}
    queue = [(1, None)]
    while True:
        value, prev = queue.pop(0)
        value not in path_from:
            path_from[value] = prev
            if value == n:
                break # EXIT HERE
            queue.append((value+1, value))
            for i in range(2, min(value+1, n//value + 1)):
                queue.append((i*value, value))

    answer = []
    while n is not None:
        answer.append(n)
        n = path_from[n]

    return(answer)

print(path(100))

Upvotes: 2

Related Questions