#!/usr/bin/env python3
''' http://www.dgp.toronto.edu/~flaps/progprobs.html
there are three operators: concat, plus, minus
with eight spaces tween nine digits, search space = 3**8 = 6561 '''

from itertools import product
import operator

def concat(a,b):
    return a * 10 ** len(str(b)) + b

assert concat(21,10) == 2110

def interleave(digits, postdigits, ops, postops):
    if ops == []:
        return postdigits + digits, postops
    a,b,*c = digits
    op, *ops = ops
    if op == concat:
        return interleave( [ concat(a,b) ] + c, postdigits, ops, postops )
    else:
        return interleave( [b] + c, postdigits + [a], ops, postops + [op] )

#interleave([1,2], [], [op.add], [])
#interleave([1,2,3,4], [], [op.add, concat, op.sub], [])

def sumify(digits, ops):
    if ops == []:
        return digits[0]
    op, *ops = ops
    a,b,*c = digits
    return sumify([ op(a,b) ] + c , ops)

assert 6 == sumify([1,2,3], [operator.add, operator.add])
assert 0 == sumify([1,2,3], [operator.add, operator.sub])

def display(digits, ops, acc):
    if ops == []:
        return acc + ' ' + str(digits[0])
    a,*b = digits
    a = str(a)
    op, *ops = ops
    op = '+' if op == operator.add else '-'
    return display(b, ops, ' '.join([acc, a, op]))

assert display([1,2,3], [operator.add,operator.sub], '') == ' 1 + 2 - 3'


digits = [ 1 + x for x in range(9) ]
ops    = [operator.add, operator.sub, concat]

for p in product(ops, repeat=8):
    a,b = interleave(digits, [], p, [])
    if sumify(a,b) == 100:
        print(display(a,b, ''))