#!/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


def greedy(n):
    """
    Greedy approach - this will not always give the best solution!
    """
    if n==1:
        return 0
    if n%3 == 0:
        cost = greedy(n/3)+1
        print "At", n, "pick rule 3 with total cost", cost
        return cost
    if n%2 == 0:
        cost = greedy(n/2)+1
        print "At", n, "pick rule 2 with total cost", cost
        return cost

    cost = greedy(n-1)+1
    print "At", n, "pick rule 1 with total cost", cost
    return cost


def brute(n):
    """
    Brute force solution. Recursively find the cost for all three
    alternatives, find the best, add 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
        print "At", n, "pick rule", rule, " with total cost", cost
        return cost




















def dprec(n):
    """
    Dynamic programming solution. As above, but cache computed results
    in a the array best[], check that before recomputing.
    """
    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
            print "At", n, "pick rule", rule, " with total cost", cost
            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).
    """
    best = [0]*(n+1)

    for i in xrange(2, n+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
        print "At", i, "pick rule", rule, " with total cost", cost
        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")


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

if "brute" in selection:
    print "Brute Force"
    print "==========="
    res= brute(start)
    print "Optimal cost:", res
if "recdp" in selection:
    print "Recursive DP"
    print "============"
    res = dpinit(start)
    print "Optimal cost:", res
if "bupdp" in selection:
    print "Bottom-up DP"
    print "============"
    res =  dpbup(start)
    print "Optimal cost:", res
if "greedy" in selection:
    print "Greedy"
    print "============"
    res =  greedy(start)
    print "\"Optimal\" cost:", res