With 5, isn't it better to solve the entire class of problem? I broke the problem down into 4 sub-problems, which were easily solvable. I made helper functions to evaluate a list of strings against the goal number, to create the next 3 permutations based on the seed and the list,
My solution is quite a bit longer than some of the others, but it breaks down the problem cleanly into it's parts and it solves the entire class of problem without any modification. It took me about an hour but I haven't written python in a year or so. I'm sure I could of cleaned it up better.
Here is my solution to #5:
def permutationsFromListToGoal(initialList, goal):
#takes a list of ints and returns a big list that contains all permutations of +, - and
#squeezing the two numbers together. Size of the permutations grows exponentially based on
#size of the initial list
def permutations(initalList):
incremented = []
incremented.append([str(initalList[0])])
seed = initalList[1:]
while len(seed):
allNewIncs = []
for increment in incremented:
newIncrements = incrementList(increment, seed)
for newIncrement in newIncrements:
allNewIncs.append(newIncrement);
seed = seed[1:]
incremented = allNewIncs[:]
return incremented
#takes a list of strings (including + and - operators)
#for example: ['1', '+', '234', '-', '5']
#returns 3 lists, containing strings which are the next permutations based on the seed
def incrementList(unincremented, seed):
mergedList = unincremented[:]
mergedList[len(mergedList)-1] = mergedList[len(mergedList)-1] + str(seed[0])
plusList = unincremented[:]
plusList.append('+')
plusList.append(str(seed[0]))
minusList = unincremented[:]
minusList.append('-')
minusList.append(str(seed[0]))
return [mergedList, minusList, plusList]
#evaluates a possibility, a list of strings (including + and - operators)
#for example: evalPossibility(['1', '+', '234', '-', '5'], 23)
#returns true iff possibility computes to the int 23
def evalPossibility(possibility, goal):
result = int(possibility[0])
remaining = possibility[1:];
while len(remaining):
if remaining[0] == '+':
result = result + int(remaining[1])
remaining = remaining[2:]
elif remaining[0] == '-':
result = result - int(remaining[1])
remaining = remaining[2:]
return result == goal
def evalList(initialList, goal):
bigList = permutations(initialList)
result = []
for permutation in bigList:
if evalPossibility(permutation, goal):
result.append(permutation)
return result
results = evalList(initialList, goal)
for result in results:
printable = ''
for part in result:
printable += part
printable += ' '
print printable + ' = ' + str(goal)
permutationsFromListToGoal([1,2,3,4,5,6,7,8,9],100)