[TODO] describe what this is.

countingproblem.py

#/usr/bin/env python

# memo = {}

def f(part, target, sub_sum=0.0, previous=0.0, chosen_path=''):
    # if memo.get((part, target)):
    #     print memo[(part, target)]
    #     return
    if part == '':
        if target == (sub_sum + previous):
            #memo[(part, target)] = chosen_path + ' = %s ' % target
            print chosen_path + ' = %s ' % target
	    return
	
    for i in xrange(len(part)):
        current, remainder = int(part[:i + 1]), part[i + 1:]
        if len(chosen_path) == 0:
            f(remainder, target, sub_sum + previous, current, str(current))
        else:
        	# - + / *
            f(remainder, target, sub_sum + previous, -current, chosen_path + ' - %s' % current)
            f(remainder, target, sub_sum + previous, current, chosen_path + ' + %s' % current)
            f(remainder, target, sub_sum, previous / current, chosen_path + ' / %s' % current)
            f(remainder, target, sub_sum, previous * current, chosen_path + ' * %s' % current)

#f("3", 3) #  3
# f("33", 0) #  3 - 3
# f("33", 9) # 3 * 3
# f("33", 1) # 1
# f("33", 33) # 33
f("333", 3) # 33
#f("1234", 36) #  
#f("314159265358", 27182)

print 'FIN'

# f("314159265358", 27182) should print:      
# 3 + 1 - 415 * 92 + 65358 = 27182 
# 3 * 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 / 1 + 4 * 159 + 26535 + 8 = 27182 
# 3 * 14 * 15 + 9 + 26535 + 8 = 27182 
# 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182