allinomial.py

# allinomial.py
# Author: Dustin King (cathodion@gmail.com)
#
# This is my answer to the problem presented here:
# http://www.leighhalliday.com/solution-software-engineer-interview-challenge
#
# """ Write a program that outputs all possibilities to put + or -
# or nothing between the numbers 1, 2, ..., 9 (in this order)
# such that the result is always 100.
# For example: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100. """
#
# This took me about an hour and 15 minutes, without comments,
# and without having looked at the solution.
# Another 40 or so minutes writing comments (which should probably
# have been docstrings).


# Initial operators.
# Each operator is either '+' or '-', indicating addition/subtraction
# or None, indicating concatenation.
operators = [None, None, None, None, None, None, None, None]

# Return an incremented copy of ops, as though the
# list of operators were a base-3 number with least significant
# digit first.  Works like an adder but ternary.
# See: http://en.wikipedia.org/wiki/Adder_(electronics)
# (I should have called it carry instead of overflow.)
def incOps(ops):
    newOp, overflow = None, True
    newOps = []
    for op in ops:
        if overflow:
            newOp, overflow = incOp(op)
        else:
            newOp = op

        newOps.append(newOp)

    return newOps

# Return the successor and overflow of the operator.
# For use in incOps. Basically a 1-digit base-3 adder.
def incOp(op):
    if op is None:
        return '+', False
    elif op == '+':
        return '-', False
    else: # op == '-':
        return None, True

# Return the string representation of the expression
# of the digits 1 through 9 with specified operators.
def stringify(ops):
    s = ''
    for i in range(9):
        s += str(i + 1)
        if i < 8 and ops[i]:
            s += ' ' + ops[i] + ' '
    return s

# Calculate the integer value of the expression
# of the digits 1 through 9 with specified
# operators.
# Produces a list of positive or negative terms,
# then sums the list.
def calculate(ops):
    term = '1'
    sign = '+'
    terms = []
    for i in range(8):
        digit = i + 2
        op = ops[i]
        if op is None:
            term += str(digit)
        elif sign == '+':
            terms.append(int(term))
            sign = op
            term = str(digit)
        else:
            terms.append(-1 * int(term))
            sign = op
            term = str(digit)
    if term:
        if sign == '+':
            terms.append(int(term))
        else:
            terms.append(-1 * int(term))

    return sum(terms)

if __name__ == '__main__':
    for ignore in range(3**8):
        operators = incOps(operators)
        try:
            if calculate(operators) == 100:
                print (stringify(operators) + " = 100")
        except:
            print ('FAIL: ', operators)
            raise