Primitive Calculator - Dynamic Approach

Question

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
    #
    # Your output:
    # 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)

    input = sys.stdin.read()
    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?

Answer 1

private int count(int n, Map<Integer, Integer> lookup) {
        if(lookup.containsKey(n)) {
            return lookup.get(n);
        }
        
        if(n==1) {
            return 0;
        } else {
            int result;
            if(n%2==0 && n%3==0) {
                result =1+ 
                        //Math.min(count(n-1, lookup), 
                      Math.min(count(n/2, lookup), 
                            count(n/3, lookup));
            } else if(n%2==0) {
                result = 1+ Math.min(count(n-1, lookup), 
                                count(n/2, lookup));
            } else if(n%3==0) {
                result = 1+ Math.min(count(n-1, lookup), count(n/3, lookup));
            } else {
                result = 1+ count(n-1, lookup);
            }
            //System.out.println(result);
            lookup.put(n, result);
            return result;
        }
    }

Answer 2

def optimal_sequence(n):
hop_count = [0] * (n + 1)

hop_count[1] = 1
for i in range(2, n + 1):
    indices = [i - 1]
    if i % 2 == 0:
        indices.append(i // 2)
    if i % 3 == 0:
        indices.append(i // 3)

    
    min_hops = min([hop_count[x] for x in indices])

    
    hop_count[i] = min_hops + 1


ptr = n
optimal_seq = [ptr]
while ptr != 1:

    
    candidates = [ptr - 1]
    if ptr % 2 == 0:
        candidates.append(ptr // 2)
    if ptr % 3 == 0:
        candidates.append(ptr // 3)

    
    ptr = min(
        [(c, hop_count[c]) for c in candidates],
        key=lambda x: x[1] 
    )[0]
    optimal_seq.append(ptr)

return reversed(optimal_seq)

Answer 3

def DPoptimal_sequence(n,operations):
    MinNumOperations=[0]
    l_no=[]
    l_no2=[]

    for i in range(1,n+1):
        MinNumOperations.append(None)
        for operation in operations:
            if operation==1:
                NumOperations=MinNumOperations[i-1]+1

            if operation==2 and i%2==0:
                NumOperations=MinNumOperations[int(i/2)]+1
            if  operation==3 and i%3==0:
                NumOperations=MinNumOperations[int(i/3)]+1
            if MinNumOperations[i]==None:
                MinNumOperations[i]=NumOperations
            elif NumOperations<MinNumOperations[i]:
                MinNumOperations[i]=NumOperations
        if MinNumOperations[i] ==  MinNumOperations[i-1]+1:
            l_no2.append((i,i-1))
        elif MinNumOperations[i] ==  MinNumOperations[int(i/2)]+1 and i%2 == 0:
            l_no2.append((i,int(i/2)))
        elif MinNumOperations[i] ==  MinNumOperations[int(i/3)]+1 and i%3 == 0:
            l_no2.append((i,int(i/3)))

        l_no.append((i,MinNumOperations[i]-1))
    #print(l_no)
    #print(l_no2)
    x=MinNumOperations[n]-1
    #print('x',x)
    l_no3=[n]
    while n>1:
        a,b = l_no2[n-1]
        #print(a,b)
        if b == a-1:
            n = n-1
            #print('1111111111111')
            #print('n',n)
            l_no3.append(n)
        elif b == int(a/2) and a%2==0:
            n = int(n/2)
            #print('22222222222222222')
            #print('n',n)
            l_no3.append(n)
        elif b == int(a/3) and a%3==0:
            n = int(n/3)
            #print('333333333333333')
            #print('n',n)
            l_no3.append(n)
    #print(l_no3)
    return x,l_no3

Answer 4

One more solution:

private static List<Integer> optimal_sequence(int n) {
    List<Integer> sequence = new ArrayList<>();

    int[] arr = new int[n + 1];

    for (int i = 1; i < arr.length; i++) {
        arr[i] = arr[i - 1] + 1;
        if (i % 2 == 0) arr[i] = Math.min(1 + arr[i / 2], arr[i]);
        if (i % 3 == 0) arr[i] = Math.min(1 + arr[i / 3], arr[i]);

    }

    for (int i = n; i > 1; ) {
        sequence.add(i);
        if (arr[i - 1] == arr[i] - 1)
            i = i - 1;
        else if (i % 2 == 0 && (arr[i / 2] == arr[i] - 1))
            i = i / 2;
        else if (i % 3 == 0 && (arr[i / 3] == arr[i] - 1))
            i = i / 3;
    }
    sequence.add(1);

    Collections.reverse(sequence);
    return sequence;
}

Answer 5

Here's my Dynamic programming (bottom-up & memoized)solution to the problem:

public class PrimitiveCalculator {

    1. public int minOperations(int n){
    2.    int[] M = new int[n+1];
    3.    M[1] = 0; M[2] = 1; M[3] = 1;
    4.    for(int i = 4; i <= n; i++){
    5.        M[i] = M[i-1] + 1;
    6.        M[i] = Math.min(M[i], (i %3 == 0 ? M[i/3] + 1 : (i%3 == 1 ? M[(i-1)/3] + 2 : M[(i-2)/3] + 3)));
    7.        M[i] = Math.min(M[i], i%2 == 0 ? M[i/2] + 1: M[(i-1)/2] + 2);
    8.    }
    9.    return M[n];
   10. }

    public static void main(String[] args) {
        System.out.println(new PrimitiveCalculator().minOperations(96234));
    }
}

Before going ahead with the explanation of the algorithm I would like to add a quick disclaimer:

A DP solution is not reached at first attempt unless you have good experience solving lot of DP problems.

Approach to solving through DP

If you are not comfortable with DP problems then the best approach to solve the problem would be following:

1. Try to get a working brute-force recursive solution.
2. Once we have a recursive solution, we can look for ways to reduce the recursive step by adding memoization, where in we try remember the solution to the subproblems of smaller size already solved in a recursive step - This is generally a top-down solution.
3. After memoization, we try to flip the solution around and solve it bottom up (my Java solution above is a bottom-up one)
4. Once you have done above 3 steps, you have reached a DP solution.

Now coming to the explanation of the solution above:

Given a number 'n' and given only 3 operations {+1, x2, x3}, the minimum number of operations needed to reach to 'n' from 1 is given by recursive formula:

min_operations_to_reach(n) = Math.min(min_operations_to_reach(n-1), min_operations_to_reach(n/2), min_operations_to_reach(n/3))

If we flip up the memoization process and begin with number 1 itself then the above code starts to make better sense. Starting of with trivial cases of 1, 2, 3 min_operations_to_reach(1) = 0 because we dont need to do any operation. min_operations_to_reach(2) = 1 because we can either do (1 +1) or (1 x2), in either case number of operations is 1. Similarly, min_operations_to_reach(3) = 1 because we can multiply 1 by 3 which is one operation.

Now taking any number x > 3, the min_operations_to_reach(x) is the minimum of following 3:

1. min_operations_to_reach(x-1) + 1 because whatever is the minimum operations to reach (x-1) we can add 1 to it to get the operation count to make it number x.
2. Or, if we consider making number x from 1 using multiplication by 3 then we have to consider following 3 options:
   • If x is divisible by 3 then min_operations_to_reach(x/3) + 1,
   • if x is not divisible by 3 then x%3 can be 1, in which case its min_operations_to_reach((x-1)/3) + 2, +2 because one operation is needed to multiply by 3 and another operation is needed to add 1 to make the number 'x'
   • Similarly if x%3 == 2, then the value will be min_operations_to_reach((x-2)/3) + 3. +3 because 1 operation to multiply by 3 and then add two 1s subsequently to make the number x.
3. Or, if we consider making number x from 1 using multiplication by 2 then we have to consider following 2 options:
   • if x is divisible by 2 then its min_operations_to_reach(x/2) + 1
   • if x%2 == 1 then its min_operations_to_reach((x-1)/2) + 2.

Taking the minimum of above 3 we can get the minimum number of operations to reach x. Thats what is done in code above in lines 5, 6 and 7.

Answer 6

List<Integer> sequence = new ArrayList<Integer>();
     
while (n>0) {
    sequence.add(n);
        if (n % 3 == 0&&n % 2 == 0)
            n=n/3;
        else if(n%3==0)
            n=n/3;
        else if (n % 2 == 0&& n!=10)
            n=n/2;
        else
            n=n-1;
    }
Collections.reverse(sequence);
return sequence;

Answer 7

You are doing a greedy approach. When n == 10, you check and see if it's divisible by 2 assuming 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):
    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)