chrisl0lz - 1 year ago 665
Python Question

# Primitive Calculator - Dynamic Approach

I'm having some trouble getting the correct solution for the following problem:

Your goal is given a positive integer n, find the minimum number of
operations needed to obtain the number n starting from the number 1.

More specifically the test case I have in the comments below.

`````` # Failed case #3/16: (Wrong answer)
# got: 15 expected: 14
# Input:
# 96234
#
# 15
# 1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
# Correct output:
# 14
# 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
#  (Time used: 0.10/5.50, memory used: 8601600/134217728.)

def optimal_sequence(n):
sequence = []

while n >= 1:
sequence.append(n)

if n % 3 == 0:
n = n // 3
optimal_sequence(n)

elif n % 2 == 0:
n = n // 2
optimal_sequence(n)

else:
n = n - 1
optimal_sequence(n)

return reversed(sequence)

n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
print(x, end=' ')
``````

It looks like I should be outputting 9 where I'm outputting 4 & 5 but I'm not sure why this isn't the case. What's the best way to troubleshoot this problem?

You are doing a greedy approach. Whey you have n == 10 you check and see it's divisible by 2 so you assume that's the best step, which is wrong in this case.

What you need to do is proper dynamic programming. `v[x]` will hold the minimum number of steps to get to result `x`.

``````def solve(n):
v = [0]*(n+1)  # so that v[n] is there
v[1] = 1  # length of the sequence to 1 is 1
for i in range(1,n+1):
if not v[i]: continue
if v[i+1] == 0 or v[i+1] > v[i] + 1: v[i+1] = v[i] + 1
# Similar for i*2 and i*3

solution = []
while n > 1:
solution.append(n)
if v[n-1] == v[n] - 1: n = n-1
if n%2 == 0 and v[n//2] == v[n] -1: n = n//2
# Likewise for n//3
solution.append(1)
return reverse(solution)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download