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