#!/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 '''

import itertools

C, P, M = [ '', ' + ', ' - ' ]
DIGITS  = [ str(1 + x) for x in range(9) ]

def stringify(digits, ops, acc=''):
    digit, *digits = digits
    if digits == []:
        return acc + digit
    op, *ops = ops
    return stringify(digits, ops, acc + digit + op)

assert stringify(DIGITS[0:4], [P,M,P], '') == '1 + 2 - 3 + 4'
assert stringify(DIGITS[0:4], [P,C,M], '') == '1 + 23 - 4'


for p in itertools.product([C,P,M], repeat=8):
    s = stringify(DIGITS, p)
    if eval(s) == 100:
        print(s)