Kevin Zhao
BAN USER(1)limitation:input array can only contain single digit integer ,meaning {1,2,3} is a valid input versus {11,2,3} is not
(2)special case:resizing the array is required ,if each digit in the input is a 9.For example:{9,9,9}===>{1,0,0,0}
_____________________________________
Python Code:
def plusplus(value_list):
carry = 0;
i=len(value_list)
for digit in reversed(value_list):
i=i-1
try:
if int(digit) > 9:
raise Exception()
next_digit = (int(digit) + 1)%10
except:
print 'input array is not valid,which can only hold single digit integers'
value_list[i] = str(next_digit)
#if there is a carry,do the plus operation for the next left digit of the value_list
if next_digit == 0:
carry = 1
continue
else:
break
#special case:resizing the array is required ,if each digit in the input is a 9.For example:{9,9,9}===>{1,0,0,0}
else:
if carry == 1:
value_list.insert(0, 1)
return value_list
'''
Main Entry
'''
console_input = raw_input("Enter something(ex:9,9,9,9): ")
input_list = console_input.split(',')
result_list = plusplus(input_list)
print result_list
I'm a newbie here.This is my very first try on careercup. : )
My thought is pretty straightforward:Given user input 2,1,3,4,I list out all possible combinations of different operands beforehand,like (+,+) or (+,-) or (-,+ )...all the way to (/,/).Then combine the user input with these operands combinations to get the math expression (something like 2+1+3 or 2+1-3 or 2-1+3 .......).Then,I evaluate every expression.
Time complexity:because it's brute-force solution ,no wonder that time complexity is O(4^n)
________________________________________
Python code:
from fractions import Fraction
"""
function
example:product('+-*/',2)---->++ +- +* +/ -+ -- -* ........
"""
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
"""
Main entry
"""
# receive user input
input = raw_input("Enter something(ex:2,1,3,4 or 1,2,1/2): ")
# operands list ,example: [2,1,3,4]
items = input.split(',')
# all possible operators' combinations ,example:[(+,+),(+,-),(+,*)...........,(/,/)]
operators = product('+-*/',repeat = len(items)-2)
# try every possible operator combination and find out the right one
for operator in operators:
expression = str(float(items[0]))
for i in range(len(items)-2):
expression = expression + operator[i] + str(float(items [i+1])) # combine the operands and the operators to produce the expression,example:2+1+3
if float(eval(expression)) == Fraction(items[len(items)-1]):# evaluate the math expression we just got above
print expression
break;
else:
print 'no expression'
}
________________________________________
Sample:
(1)input:2,1,3,4----->output:2.0-1.0+3.0
(2)input:1,2,3,4,5/4---->output:1.0*2.0-3.0/4.0
@Psycho: agree!!
- Kevin Zhao July 24, 2012