This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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