digits.py

# coding=utf-8
"""
This script is used to calculate properties of strings containing binary operators.
See https://lyness.io/experimenting-with-bracketing-and-binary-operators for more details.
"""

import itertools


def all_expressions(generic_expression, operation_combinations):
    """
    Merges a source expression and combinations of binary operators to generate a list of all possible expressions.
    @param ((str,)) operation_combinations: all combinations of binary operators to consider
    @param str generic_expression: source expression with placeholder binary operators
    @rtype: (str,)
    """
    expression_combinations = []
    for combination in operation_combinations:
        expression_combinations.append(generic_expression.format(*combination))
    return expression_combinations


def all_bracketings(expr):
    """
    Generates all possible permutations of parentheses for an expression.
    @param str expr: the non-bracketed source expression
    @rtype: str
    """
    if len(expr) == 1:
        yield expr
    else:
        for i in range(1, len(expr), 2):
            for left_expr in all_bracketings(expr[:i]):
                for right_expr in all_bracketings(expr[i + 1:]):
                    yield "({}{}{})".format(left_expr, expr[i], right_expr)


def calculate_expressions(min_digits, max_digits, operations):
    """Perform all calculations with the given operations and in the range of digits specified.
    @param (str,) operations: the operations considered as valid binary operators
    @param int min_digits: the minimum number of digits to consider
    @param int max_digits: the maximum number of digits to consider
    """
    operations_string = "".join(operations)
    print("\t".join(["Digit", "Operations", "Num operations", "Num digits", "Max value", "Max expression", "Min value",
                     "Min expression", "Smallest non-zero value", "Smallest non-zero expression", "Total expressions",
                     "Total valid expressions"]))
    for num_digits in range(min_digits, max_digits + 1):
        for digit in range(0, 10):
            operation_iterable = itertools.product(*[operations] * (num_digits - 1))
            operation_combinations = []
            min_value = None
            min_expression = None
            max_value = None
            max_expression = None
            smallest_value = None
            smallest_expression = None
            expression_count = 0
            valid_expression_count = 0
            template = " ".join(str(digit) * num_digits)
            for operation in operation_iterable:
                operation_combinations.append(operation)
            for bracketed_expression in all_bracketings(template):
                for expression in all_expressions(bracketed_expression.replace(" ", "{}"), operation_combinations):
                    try:
                        value = eval(expression)  # eval ONLY used here because we completely trust the input!
                        if max_value is None or value > max_value:
                            max_value = value
                            max_expression = expression
                        if min_value is None or value < min_value:
                            min_value = value
                            min_expression = expression
                        if value != 0 and (smallest_value is None or abs(value) < smallest_value):
                            smallest_value = abs(value)
                            smallest_expression = expression
                        valid_expression_count += 1
                    except ZeroDivisionError:
                        pass
                    expression_count += 1
            print("\t".join([str(digit), operations_string, str(len(operations)), str(num_digits),
                             str(max_value), max_expression, str(min_value), min_expression, str(smallest_value),
                             str(smallest_expression), str(expression_count), str(valid_expression_count)]))


if __name__ == "__main__":
    min_num_digits = 1
    max_num_digits = 8
    operation_set = ["+", "-", "*", "/"]
    calculate_expressions(min_num_digits, max_num_digits, operation_set)