fork download
copy 
  1. #five_three_iter5.py
  2. def findSequence(goal):
  3.     # We start with the given number
  4.     # and work backwards towards 1.
  5.     node_list = [[goal, False, False]]
  6.     op_seq_list = []
  7.     NO_SOLN = 0
  8.     CONTINUE = 1
  9.     GOT_IT = 2
  10.     status = CONTINUE
  11.  
  12.     # from the list of 5's and 3's generate the sequence
  13.     # of operations
  14.     def OpSeq():
  15.         # First reverse the sequence since we have arrived at it
  16.         # by working backwards from the number
  17.         op_seq_list.reverse()
  18.         seq_str ='(1'
  19.         for index, num in enumerate(op_seq_list):
  20.             if num == 5:
  21.                 seq_str = seq_str + " + 5"
  22.             if num == 3:
  23.                 # Put surrounding brackets only if the previous number was a 5
  24.                 # and the present is a 3
  25.                 if index and op_seq_list[index - 1] == 5:
  26.                     seq_str = "(" + seq_str + ")*3"
  27.                 else:
  28.                     seq_str = seq_str + "*3"
  29.         seq_str += ")"
  30.         return seq_str
  31.  
  32.     def breakOrContinue(nn, bn):
  33.         op_seq_list.append(bn)
  34.         if nn == 1:
  35.             # If we have reached 1 print
  36.             # the sequence and come out of the while loop
  37.             return GOT_IT
  38.         else:
  39.             # Append the new number and proceed from this new number
  40.             node_list.append([nn, False, False])
  41.             return CONTINUE
  42.  
  43.     def try3branch(node):
  44.         ret_val = NO_SOLN
  45.         if not node[1]:
  46.             node[1] = True
  47.             if node[0] % 3 == 0:
  48.                 new_num = node[0]/3
  49.                 if new_num >= 1:
  50.                     ret_val = breakOrContinue(new_num, 3)
  51.         return ret_val
  52.  
  53.     def try5branch(node):
  54.         ret_val = NO_SOLN
  55.         if not node[2]:
  56.             node[2] = True
  57.             new_num = node[0] - 5
  58.             if new_num >= 1:
  59.                 ret_val = breakOrContinue(new_num, 5)
  60.         return ret_val
  61.  
  62.     def tryBackTrack():
  63.         if len(node_list) == 1:
  64.             return NO_SOLN
  65.         else:
  66.             # Remove the last entry and proceed from
  67.             # the untried branch of the previous entry
  68.             node_list.pop()
  69.             op_seq_list.pop()
  70.             return CONTINUE
  71.  
  72.     while status == CONTINUE:
  73.         # Take the last entry
  74.         node = node_list[-1]
  75.         status = ( try3branch(node) or try5branch(node) or tryBackTrack() )
  76.  
  77.     if status == GOT_IT:
  78.         return OpSeq()
  79.     else:
  80.         return ''
  81.  
  82.  
  83. if __name__ == '__main__':
  84.     import sys
  85.     input_num = int(sys.argv[1])
  86.     op_seq = findSequence(input_num)
  87.     if op_seq:
  88.         print op_seq
  89.     else:
  90.         print 'No solution'
  91.  
Not running #stdin #stdout 0s 0KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ulQJJ
language:
Python (cpython 2.7.16)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!