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.

gistfile1.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
# https://blog.svpino.com/2015/05/07/five-programming-problems-every-software-engineer-should-be-able-to-solve-in-less-than-1-hour
# http://stackoverflow.com/questions/2136910/can-i-unit-test-an-inner-function-in-python

"""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.
"""

def cons(head, tails):
    """
    >>> cons('a', [['b'],['c']])
    [['a', 'b'], ['a', 'c']]
    >>> cons('a', [['b','c'],['c','d']])
    [['a', 'b', 'c'], ['a', 'c', 'd']]
    >>> cons(1, [])
    [1]
    >>> cons(1, [[2,3],[3,4]])
    [[1, 2, 3], [1, 3, 4]]
    """
    result = []
    # check the length, not equality as the input can be either null list or null tuple
    if len(tails) == 0: return [head]
    for t in tails:
        result.append([head] + t)
    return result

def random_values(values):
    """
    >>> random_values([])
    [[]]
    >>> random_values([1])
    [[1], [-1]]
    >>> random_values([1,2])
    [[1, 2], [1, -2], [-1, 2], [-1, -2]]
    >>> random_values(range(1,4))
    [[1, 2, 3], [1, 2, -3], [1, -2, 3], [1, -2, -3], [-1, 2, 3], [-1, 2, -3], [-1, -2, 3], [-1, -2, -3]]
    >>> random_values((1,))
    [[1], [-1]]
    >>> random_values((1,2))
    [[1, 2], [1, -2], [-1, 2], [-1, -2]]
    """
    #if values == []: return [[]]
    if len(values) == 0: return [[]]
    else:
        res = random_values(values[1:])
        return cons(values[0], res) + cons(-values[0], res)
        
def get_ones_zeros(size):
    """
    >>> get_ones_zeros(0)
    [[]]
    >>> get_ones_zeros(1)
    [[0], [1]]
    >>> get_ones_zeros(2)
    [[0, 0], [0, 1], [1, 0], [1, 1]]
    >>> get_ones_zeros(3)
    [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
    """
    if size == 0: return [[]]
    else:
        res = get_ones_zeros(size - 1)
        return cons(0, res) + cons(1, res)

def glue(values, glues):
    """
    >>> glue([1,2,3,4,5,6,7,8,9], [0,0,0,0,0,0,0,0,0])
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> glue([1,2,3,4,5,6,7,8,9], [1,0,0,0,0,0,0,0,0])
    [12, 3, 4, 5, 6, 7, 8, 9]
    >>> glue([1,2,3,4,5,6,7,8,9], [0,1,0,0,0,0,0,0,0])
    [1, 23, 4, 5, 6, 7, 8, 9]
    >>> glue([1,2,3,4,5,6,7,8,9], [0,1,1,1,1,1,1,1,1])
    [1, 23456789]
    """
    
    index_j = 0
    index_i = 0
    size = len(values)
    
    result = []
    value_stack = values[0]
    
    while index_i < size:
        
        # the case over the boundary
        if index_i + 1 >= size:
            result.append(value_stack)
            break
        
        new_value = values[index_i + 1]
        # normal case
        if glues[index_j] == 0:
            result.append(value_stack)
            value_stack = new_value
        else:
            value_stack = value_stack * 10 + new_value
                
        index_i += 1
        index_j += 1

    return result
    
def get_numbers(stop = 9):
    """returns all the possible numbers combined from 1 to 9
    i.e., 1,2,...,9 
    i.e., 1, 23, ..., 89
    
    Algorithm:
        1. Think about the magic glue, when glue is applied the values are glued to make multiple digits value
        2. There are only maximal 8 possible glue position. 
    
    >>> get_numbers(3)
    set([(1, 23), (123,), (12, 3), (1, 2, 3)])
    >>> get_numbers(4)
    set([(12, 34), (1, 2, 3, 4), (1, 2, 34), (12, 3, 4), (123, 4), (1, 234), (1234,), (1, 23, 4)])
    >>> get_numbers(5)
    set([(12, 3, 4, 5), (1, 234, 5), (12, 3, 45), (1, 2, 3, 4, 5), (12, 345), (123, 45), (1, 2, 34, 5), (1, 2, 3, 45), (1, 2345), (1, 23, 4, 5), (1, 2, 345), (12345,), (1, 23, 45), (12, 34, 5), (1234, 5), (123, 4, 5)])
    """
    values = range(1, stop+1)
    one_zeros = get_ones_zeros(stop)
    result = []
    for one_zero in one_zeros:
        res = glue(values, one_zero)
        # list cannot be a member of a set, so the result should be turn into a tuple
        result.append(tuple(res))
    return set(result)
    
def solution(stop = 9, goal = 100):
    """
    >>> solution(9)
    [1, 2, 34, -5, 67, -8, 9]
    [1, 23, -4, 56, 7, 8, 9]
    [12, 3, -4, 5, 67, 8, 9]
    [123, -4, -5, -6, -7, 8, -9]
    [1, 23, -4, 5, 6, 78, -9]
    [12, 3, 4, 5, -6, -7, 89]
    [12, -3, -4, 5, -6, 7, 89]
    [123, -45, -67, 89]
    [123, 45, -67, 8, -9]
    [1, 2, 3, -4, 5, 6, 78, 9]
    [123, 4, -5, 67, -89]
    """
    numbers = get_numbers(stop)
    for number in numbers:
        variations = map(lambda y: [number[0]] + y, random_values(number[1:]))
        for v in variations:
            summed_value = sum(v)
            if goal == summed_value:
                print(v)
    
if __name__ == "__main__":
    import doctest
    doctest.testmod()