93. Arithmetic expressions.md

93. Arithmetic expressions

Question

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2

14 = 4 * (3 + 1 / 2)

19 = 4 * (2 + 3) − 1

36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

Solution

A very interesting question. Initially evaluated the arithmetic expression strings which leads to the slow version below. The fast version extensively uses functions.

There are only five types of binary expression tree given four numbers and three operators.

Fast (~1s)

from itertools import permutations, combinations, product, count
from operator import mul, add, sub, truediv

def p93():

    def f1(a, b, c, d, op1, op2, op3):
        return op2(op1(a, b), op3(c, d))  # (a b) (c d)

    def f2(a, b, c, d, op1, op2, op3):
        return op3(op2(op1(a, b), c), d)  # ((a b) c) d

    def f3(a, b, c, d, op1, op2, op3):
        return op3(op1(a, op2(b, c)), d)  # (a (b c)) d

    def f4(a, b, c, d, op1, op2, op3):
        return op1(a, op2(b, op3(c, d)))  # a (b (c d))

    def f5(a, b, c, d, op1, op2, op3):
        return op1(a, op3(op2(b, c), d))  # a ((b c) d)

    func_list = [f1, f2, f3, f4, f5]

    def calculate(increase_nums):
        unique = set()
        for a, b, c, d in permutations(increase_nums):
            for op1, op2, op3 in product([add, sub, mul, truediv], repeat=3):
                for f in func_list:
                    try:
                        val = f(a, b, c, d, op1, op2, op3)
                        if val > 0 and val == int(val):
                            unique.add(int(val))
                    except ZeroDivisionError:
                        pass
        return next(i for i in count(1) if i not in unique)

    return ''.join(str(n) for n in max((increase_nums for increase_nums in combinations(range(10), 4)), key=calculate))

Slow (~13s)

from itertools import permutations, combinations, product, count

operators = ['+', '-', '*', '/']

def evaluate(s):
    """evaluate arithmetic expression string
    which contains only digits, brackets and
    four arithmetic operators (+, −, *, /)
    """
    def eval(s):
        nonlocal i
        nums, op = [], '+'
        while i < len(s):
            if s[i] == ')': break
            if s[i] in operators:
                op = s[i]
                i += 1
                continue
            if s[i] == '(':
                i += 1
                n = eval(s)
            else:
                n = int(s[i])  # assume that s only contains single digit numbers
            if op == '+': nums.append(n)
            if op == '-': nums.append(-n)
            if op == '*': nums[-1] *= n
            if op == '/': nums[-1] /= n
            i += 1
        return sum(nums)

    i = 0
    return eval(s)

def p93():
    def eval_cases(a, b, c, d, op1, op2, op3, unique):
        s = [''] * 5
        s[0] = f"({a}{op1}{b}){op2}({c}{op3}{d})"  # (a b) (c d)
        s[1] = f"(({a}{op1}{b}){op2}{c}){op3}{d}"  # ((a b) c) d
        s[2] = f"({a}{op1}({b}{op2}{c})){op3}{d}"  # (a (b c)) d
        s[3] = f"{a}{op1}({b}{op2}({c}{op3}{d}))"  # a (b (c d))
        s[4] = f"{a}{op1}(({b}{op2}{c}){op3}{d})"  # a ((b c) d)
        for ss in s:
            try:
                val = evaluate(ss)  # can use the built-in eval() which is much slower
                if val > 0 and val == int(val):
                    unique.add(int(val))
            except ZeroDivisionError:
                pass

    def calculate(increase_nums):
        unique = set()
        for a, b, c, d in permutations(increase_nums):
            for op1, op2, op3 in product(operators, repeat=3):
                eval_cases(a, b, c, d, op1, op2, op3, unique)
        return next(i for i in count(1) if i not in unique)

    return ''.join(str(n) for n in max((increase_nums for increase_nums in combinations(range(10), 4)), key=calculate))

Answer

1258