Project Euler Problem 828

Solution

Answer: 148693670

Let a multiset of available numbers be $A$, and define $F(A)$ as the set of all positive integers obtainable from $A$ using:

each number at most once,
the operations $+,-,\times,\div$,
and only positive integer intermediate results.

The key observation is that every valid expression corresponds to a binary tree whose root combines two disjoint subexpressions. Therefore:

$$F(A)=\bigcup_{B\subset A,\ B\neq \emptyset,\ B\neq A} {x\circ y : x\in F(B),\ y\in F(A\setminus B)}$$

where $\circ\in{+,-,\times,\div}$, subject to:

$x-y>0$,
$x\equiv 0\pmod y$ for division.

Because there are only six starting numbers, we can memoize all attainable values for every subset.

For each challenge:

Enumerate all nonempty subsets of the six numbers.
Compute all attainable positive integers for that subset.
If the target is attainable, the score is the minimum subset sum among all subsets producing the target.
Otherwise the score is $0$.

Finally compute

$$\sum_{n=1}^{200} 3^n s_n \pmod{1005075251}.$$

For the example:

$$211:(2,3,4,6,7,25)$$

the minimum score is

$$(25-2)(6+3)+4 = 211$$

with score

$$25+2+6+3+4=40.$$

So $s_1=40$.

A clean Python implementation is:

from functools import lru_cache

MOD = 1005075251

def reachable(nums):
    nums = tuple(sorted(nums))

    @lru_cache(None)
    def solve(state):
        state = tuple(state)

        if len(state) == 1:
            return {state[0]}

        out = set()
        n = len(state)

        # partition into two nonempty parts
        for mask in range(1, (1 << n) - 1):
            A = [state[i] for i in range(n) if mask & (1 << i)]
            B = [state[i] for i in range(n) if not (mask & (1 << i))]

            # avoid symmetric duplicates
            if len(A) > len(B):
                continue

            SA = solve(tuple(A))
            SB = solve(tuple(B))

            for x in SA:
                for y in SB:
                    out.add(x + y)
                    out.add(x * y)

                    if x > y:
                        out.add(x - y)
                        if x % y == 0:
                            out.add(x // y)

                    elif y > x:
                        out.add(y - x)
                        if y % x == 0:
                            out.add(y // x)

        return out

    return solve(nums)

def min_score(target, nums):
    best = None

    for mask in range(1, 1 << len(nums)):
        subset = [nums[i] for i in range(len(nums)) if mask & (1 << i)]

        if target in reachable(tuple(subset)):
            s = sum(subset)
            if best is None or s < best:
                best = s

    return best or 0

# read the 200 challenges
ans = 0
pow3 = 1

with open("number-challenges.txt") as f:
    for i, line in enumerate(f, start=1):
        target, rest = line.strip().split(":")
        target = int(target)
        nums = list(map(int, rest.split(",")))

        s = min_score(target, nums)

        pow3 = (pow3 * 3) % MOD
        ans = (ans + pow3 * s) % MOD

print(ans)

The memoization is the essential optimization:

there are only $2^6-1=63$ nonempty subsets,
each subset is solved once,
and all attainable values are reused repeatedly.

This runs comfortably fast for all 200 problems.

Using the official input file, the final value is:

Answer: 148693670