CODEWITHSUNDEEP
python-3.xalgorithmdynamic-programming
Dhruv Singh
Dhruv Singh

Reputation: 51

Dynamic Programming Primitive calculator code optimization

I am currently doing coursera course on algorithms. I have successfully completed this assignment. All test cases passed. My code looks messy and I want to know if there is any thing availiable in Python which can help run my code faster. Thanks

The problem statement is as follows: You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given a positive integer 𝑛, find the minimum number of operations needed to obtain the number 𝑛 starting from the number 1.

# Uses python3
import sys

def optimal_sequence(m):
    a=[0,0]
    for i in range(2,m+1):
        if i%3==0 and i%2==0:
            a.append(min(a[i//2],a[i//3],a[i-1])+1)
        elif i%3==0:
            a.append(min(a[i//3],a[i-1])+1)
        elif i%2==0:
            a.append(min(a[i//2],a[i-1])+1)
        else:
            a.append((a[i-1])+1)
    return backtrack(a,m)
def backtrack(a,m):
    result=[]
    result.append(m)
    current = m
    for i in range(a[-1],0,-1):
        if current%3==0 and a[current//3]==(i-1):
            current=current//3
            result.append(current)
        elif current%2==0 and a[current//2]==(i-1):
            current = current//2
            result.append(current)
        elif a[current-1]==(i-1):
            current = current-1
            result.append(current)
    return result

n = int(input())
if n == 1:
    print(0)
    print(1)
    sys.exit(0)

a= (optimal_sequence(n))
print(len(a)-1)
for x in reversed(a):
    print(x,end=" ")

Upvotes: 1

Views: 213

Answers (1)

trincot
trincot

Reputation: 351369

I would use a breadth first search for number 1 starting from number n. Keep track of the numbers that were visited, so that the search backtracks on already visited numbers. For visited numbers remember which is the number you "came from" to reach it, i.e. the next number in the shortest path to n.

In my tests this code runs faster than yours:

from collections import deque

def findOperations(n):
    # Perform a BFS
    successor = {} # map number to next number in shortest path
    queue = deque() # queue with number pairs (curr, next)
    queue.append((n,None)) # start at n
    while True:
        curr, succ = queue.popleft()
        if not curr in successor: 
            successor[curr] = succ
            if curr == 1:
                break
            if curr%3 == 0: queue.append((curr//3, curr))
            if curr%2 == 0: queue.append((curr//2, curr))
            queue.append((curr-1, curr))
    # Create list from successor chain  
    result = []
    i = 1
    while i:
        result.append(i)
        i = successor[i]
    return result

Call this function with argument n: 

findOperations(n)

It returns a list.

Upvotes: 1

Related Questions