Make equations to generate numbers

numbers.py

# -*- coding: utf-8 -*-
#
#   numbers.py
#
#   David Janes
#   2016-10-21
#
#   Program to solve (more generally):
#
#   Take the digits 5, 4, 3, 2 and 1, in that order. 
#   Using those digits and the four arithmetic signs — plus, minus, times and divided by — 
#   you can get 1 with the sequence 5 - 4 + 3 - 2 - 1. 
#   You can get 2 with the sequence (5 - 4 + 3 - 2) x 1.
#
#   The question is ... how many numbers from 1 to 40 can you get using the 
#   digits 5, 4, 3, 2, and 1 in that order along with the four arithmetic signs?

import re
import itertools
import pprint

def make_equations(ndigits):
    """This will generate all the raw equations, with a placeholder for the operator to be added.
    Or to put it another way, this generates all the bracketing combinations

    The key insight to make this work is where the brackets should go is 
    basically counting in binary, where a 1 indicates "bracket here"

        0000    ( 1 2 3 4 5 )
        0001    ( 1 2 3 4 ) ( 5 )
        0010    ( 1 2 3 ) ( 4 5 )

    Sidenote:
    I initially though that two brackets in row could allow this equation to be skipped,
    but it's not so. E.g. 0110 generates ( 1 2 ) 3 ( 4 5 ) which is not generated elsewhere

    """
    equations = []
    for code in xrange(0, 2 ** (ndigits - 1)):
        breaks = [ ( 2 ** position ) & code and 1 or 0 for position in xrange(0, ndigits - 1) ]
        breaks.append(0)

        parts = [ "(" ]
        for index in xrange(0, ndigits):
            parts.append(str(ndigits - index))

            if breaks[index]:
                parts.append(")")
                parts.append("%s")
                parts.append("(")
            elif index < ndigits - 1:
                in_break = False
                parts.append("%s")

        parts.append(")");

        equations.append(" ".join(parts))

    return equations

def make_all_operators(ndigits):
    """Make all the combinations of operators that can be inserted into the equation.

    e.g. 
        + + + +
        + + + -
        ...
        * * * *

    Fortunately, Python has us covered"""

    return list(itertools.product('+-*/', repeat=ndigits - 1))

def evaluate(equation):
    """Evaluate the equation with the operators

    This code is convoluted because:
    - we need to operate in floating point to avoid integer rounding
    - some of the math can produce division by zero
    """
    equation = re.sub("([\d]) ", r"\1.0 ", equation) 
    try:
        result = eval(equation)
    except ZeroDivisionError:
        return

    if result != int(result):
        return

    return int(result)

def print_result(resultd):
    keys = resultd.keys()
    keys.sort()

    for key in keys:
        equations = resultd[key]

        print "%-3d =" % key, equations[0]
        for equation in equations[1:]:
            print "     ", equation

if __name__ == '__main__':
    ndigits = 5

    equations = make_equations(ndigits)
    all_operators = make_all_operators(ndigits)

    resultd = {}

    for equation in equations:
        for operators in all_operators:
            equation_filled = equation % operators

            result = evaluate(equation_filled)
            if result == None:
                continue

            resultd.setdefault(result, []).append(equation_filled)

    print_result(resultd)