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 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 = [0]+[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)[0]+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[0]>ret[0]:
# ans = (ret[0]+1, n//2)
# if n % 3 == 0:
# ret = optimal_sequence(n // 3)
# if ans[0] > ret[0]:
# ans = (ret[0]+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)
input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
print(x, end=' ')
```