#five_three_iter5.py
def findSequence(goal):
# We start with the given number
# and work backwards towards 1.
node_list = [[goal, False, False]]
op_seq_list = []
NO_SOLN = 0
CONTINUE = 1
GOT_IT = 2
status = CONTINUE
# from the list of 5's and 3's generate the sequence
# of operations
def OpSeq():
# First reverse the sequence since we have arrived at it
# by working backwards from the number
op_seq_list.reverse()
seq_str ='(1'
for index, num in enumerate(op_seq_list):
if num == 5:
seq_str = seq_str + " + 5"
if num == 3:
# Put surrounding brackets only if the previous number was a 5
# and the present is a 3
if index and op_seq_list[index - 1] == 5:
seq_str = "(" + seq_str + ")*3"
else:
seq_str = seq_str + "*3"
seq_str += ")"
return seq_str
def breakOrContinue(nn, bn):
op_seq_list.append(bn)
if nn == 1:
# If we have reached 1 print
# the sequence and come out of the while loop
return GOT_IT
else:
# Append the new number and proceed from this new number
node_list.append([nn, False, False])
return CONTINUE
def try3branch(node):
ret_val = NO_SOLN
if not node[1]:
node[1] = True
if node[0] % 3 == 0:
new_num = node[0]/3
if new_num >= 1:
ret_val = breakOrContinue(new_num, 3)
return ret_val
def try5branch(node):
ret_val = NO_SOLN
if not node[2]:
node[2] = True
new_num = node[0] - 5
if new_num >= 1:
ret_val = breakOrContinue(new_num, 5)
return ret_val
def tryBackTrack():
if len(node_list) == 1:
return NO_SOLN
else:
# Remove the last entry and proceed from
# the untried branch of the previous entry
node_list.pop()
op_seq_list.pop()
return CONTINUE
while status == CONTINUE:
# Take the last entry
node = node_list[-1]
status = ( try3branch(node) or try5branch(node) or tryBackTrack() )
if status == GOT_IT:
return OpSeq()
else:
return ''
if __name__ == '__main__':
import sys
input_num = int(sys.argv[1])
op_seq = findSequence(input_num)
if op_seq:
print op_seq
else:
print 'No solution'