Project Euler 93

题目

Arithmetic expressions

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\).

解决方案

直接枚举。

为了加速，先将其转为后缀表达式。可以发现，转化成后缀表达式后，一共有\(5\)种不同的运算顺序。 遍历每个后缀表达式模板，填入枚举的数字和运算符后，再用后缀表达式直接做运算。

枚举量：一共有\(\dbinom{9}{4}\)个候选答案。对于每个组合，其中可以以任意顺序填入后缀表达式中，一共有\(4!\)种。一共要做\(3\)次运算，因此运算符的组合有\(4^3\)种。因此需要进行\(\dbinom{9}{4}\times 4!\times 4^3\times 5=967680\)次的枚举。

在此过程中，需要注意除数为\(0\)的情况。

代码

from itertools import permutations, product, combinations, count

# value_pos_list = [p for p in set(permutations([-1, -1, -1, 1, 1, 1, 1])) if all(sum(p[:i + 1]) > 0 for i in range(
# len(p)))]
# print(value_pos_list)
op_list = list("".join(l) for l in product("+-*/", repeat=3))


def cal(s: str):
    ls = []
    for t in s:
        if t.isdigit():
            ls.append(int(t))
        else:
            x, y = ls[-2], ls[-1]
            ls.pop()
            if t == '+':
                ls[-1] = x + y
            elif t == '-':
                ls[-1] = x - y
            elif t == '*':
                ls[-1] = x * y
            elif y:
                ls[-1] = x / y
            else:
                return 0
    w = ls[0]
    return round(w) if abs(w - round(w)) < 1e-8 else 0


def solve(values):
    st = set()
    for per in permutations(values):
        digit = "".join(str(x) for x in per)
        for op in op_list:
            st.add(cal(digit[:2] + op[0] + digit[2:] + op[1:]))
            st.add(cal(digit[:3] + op[:2] + digit[3] + op[2]))
            st.add(cal(digit[:3] + op[0] + digit[3] + op[1:]))
            st.add(cal(digit + op))
            st.add(cal(digit[:2] + op[0] + digit[2] + op[1] + digit[3] + op[2]))

    for i in count(1, 1):
        if i not in st:
            return i - 1
    return -1


mx = 0
for v in combinations(list(range(1, 10)), 4):
    w = solve(v)
    if w > mx:
        mx = w
        ans = "".join(str(x) for x in v)
print(ans)