1

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=" ")

1 Answer 1

1

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.

1
  • Thanks. I didn't even think like this. Apr 14, 2019 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.