#!/usr/bin/env python2

"""
Optimally solve the problem of reducing a given integer number to 1
using the followng rules:

Rule 1: You can always decrease the number by 1
Rule 2: If the number is even, youy can divide it by 2
Rule 3: If the number is a multiple of 3, you can divide it by three

We search for the shortest sequence of rule applications, e.g.
10->9->3->1 (using rules 1, 3, 3).
"""

import sys
import getopt

steps = 0

def greedy(n):
    """
    Greedy approach - this will not always give the best solution!
    """
    global steps
    steps = steps+1

    if n==1:
        return 0
    if n%3 == 0:
        cost = greedy(n/3)+1
        return cost
    if n%2 == 0:
        cost = greedy(n/2)+1
        return cost

    cost = greedy(n-1)+1
    return cost


def brute(n):
    """
    Brute force solution. Recursively find the cost for all three
    alternatives, find the best, add 1.
    """
    global steps
    steps = steps+1

    if n == 1:
        return 0
    else:
        subcost = brute(n-1)
        rule = 1
        if n%2 == 0:
            tmp = brute(n/2)
            if tmp<subcost:
                subcost = tmp
                rule = 2
        if n%3 == 0:
            tmp = brute(n/3)
            if tmp<subcost:
                subcost = tmp
                rule = 3
        cost = subcost +1
        return cost




















def dprec(n):
    """
    Dynamic programming solution. As above, but cache computed results
    in a the array best[], check that before recomputing.
    """
    global steps
    steps = steps+1

    if n == 1:
        return 0
    else:
        if best[n] == 0:
            subcost = dprec(n-1)
            rule = 1
            if n%2 == 0:
                tmp = dprec(n/2)
                if tmp<subcost:
                    subcost = tmp
                    rule = 2
            if n%3 == 0:
                tmp = dprec(n/3)
                if tmp<subcost:
                    subcost = tmp
                    rule = 3
            cost = subcost +1
            best[n] = cost
        return best[n]

def dpinit(n):
    """
    Wrapper - initialize result array, then call recursive DP
    solution.
    """
    global best
    best = [0]*(n+1)
    return dprec(n)























def dpbup(n):
    """
    Bottom-up dynamic programming. This approach is good if we can
    easily determine which subproblems we need to solve (here: all).
    """
    global steps

    best = [0]*(n+1)

    for i in xrange(2, n+1):
        steps = steps+1
        subcost = best[i-1]
        rule = 1
        if i%2 == 0:
            tmp = best[i/2]
            if tmp<subcost:
                subcost = tmp
                rule = 2
        if i%3 == 0:
            tmp = best[i/3]
            if tmp<subcost:
                subcost = tmp
                rule = 3
        cost = subcost +1
        best[i] = cost
    return best[n]



















opts, args = getopt.gnu_getopt(sys.argv[1:], "brug")
selection = []
for opt, optarg in opts:
    if opt == "-b":
       selection.append("brute")
    elif opt == "-r":
       selection.append("recdp")
    elif opt == "-u":
       selection.append("bupdp")
    elif opt == "-g":
       selection.append("greedy")

if len(selection)==0:
   selection.append("brute")


end = 100
if len(args)>0:
    end = int(args[0])

for start in range(1,end+1):
    print "===========", start, "======"
    if "brute" in selection:
        print "Brute Force ",
        steps = 0
        res= brute(start)
        print "Optimal cost:  ", res, " with effort ", steps
    if "recdp" in selection:
        steps = 0
        print "Recursive DP",
        res = dpinit(start)
        print "Optimal cost:  ", res, " with effort ", steps
    if "bupdp" in selection:
        steps = 0
        print "Bottom-up DP",
        res =  dpbup(start)
        print "Optimal cost:  ", res, " with effort ", steps
    if "greedy" in selection:
        steps = 0
        print "Greedy      ",
        res =  greedy(start)
        print "\"Optimal\" cost:", res, " with effort ", steps