# 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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment