 banchan86
6/2/2017 - 6:50 AM

## This uses dynamic programming to figure out the fastest way to get from any number to 1 with 3 operations (division by 2, division by 3 and

This uses dynamic programming to figure out the fastest way to get from any number to 1 with 3 operations (division by 2, division by 3 and minus 1)

``````# Uses python3
import sys

#this is a dynamic programming approach in an iterative function
def optimal_sequence(n):
array_previous_numbers = [None]*(n+1)
array_min_ops = +[None]*n

for number in range(1, n+1):
previous_number = number - 1
min_ops = array_min_ops[previous_number]+1
# this operation records the value of computing optimal_sequence by adding 1 to the previous number.
# this answer is used as the default fill in value until a better operation is found.
# the next two if statesments

if number % 3 == 0:
candidate_previous_number = number // 3
candidate_num_ops = array_min_ops[candidate_previous_number]+1
if candidate_num_ops < min_ops:
previous_number = candidate_previous_number
min_ops = candidate_num_ops

if number % 2 == 0:
candidate_previous_number = number // 2
candidate_num_ops = array_min_ops[candidate_previous_number] + 1
if candidate_num_ops < min_ops:
previous_number = candidate_previous_number
min_ops = candidate_num_ops

array_previous_numbers[number], array_min_ops[number] = previous_number, min_ops
# this fills the two empty arrays with the previous numbers and min_ops

# this is an ingenious section to reconstruct the solution
numbers = []
countdown = n
while countdown > 0:
numbers.append(countdown)
countdown = array_previous_numbers[countdown]
numbers.reverse()
return numbers

#this is an recursive version which fails with very big numbers.
# array = {}
# def optimal_sequence(n):
#     if n == 1:
#         array[n] = 1, -1
# #        return 1, -1
#     # if 1 is reached, terminate
#     if array.get(n) is not None:
#         return array[n]
#     # if the indice in the array is not empty return the answer
#
#     ans = (optimal_sequence(n-1)+1, n-1)
#     # this operation records the value of computing optimal_sequence by adding 1 to the previous number.
#     # this answer is used as the default fill in value until a better operation is found.
#     # returns a tuple, (a,b) where a is the number of operations and b is the previous number used to get the solution
#     # the below solutions records the value of computing optimal sequences by dividing by two or 3
#
#     if n % 2 == 0:
#         ret = optimal_sequence(n//2)
#         if ans>ret:
#             ans = (ret+1, n//2)
#     if n % 3 == 0:
#         ret = optimal_sequence(n // 3)
#         if ans > ret:
#             ans = (ret+1, n // 3)
#
#     array[n] = ans
#     return ans

#greedy solution
# def optimal_sequence(n):
#     sequence = []
#     while n >= 1:
#         sequence.append(n)
#         if n % 3 == 0:
#             n = n // 3
#         elif n % 2 == 0:
#             n = n // 2
#         else:
#             n = n - 1
#     return reversed(sequence)