Project Euler problem 118 reads, "Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631} all of the elements belonging to it are prime. How many distinct sets containing each of the digits one through nine exactly once contain only prime elements."
This is the only problem I've encountered so far that doesn't provide an answer to an easier version of the question. As a result, it is difficult for me to check the algorithm I've made. Do you see what could be the problem?
I coded up a pretty straightforward dynamic programming approach. For that, I will answer the question, "How many distinct sets containing each of the digits in S exactly once contain only prime elements", for different values of S, and then combine their results to answer the original question.
First, I generate a list of all the relevant primes. This is every prime with 9 or fewer digits, that has no duplicate digits, and that doesn't have a 0 as one of its digits. I then use this list to create a set count dictionary. The keys to this dictionary are frozensets that represent which digits each prime has, and the values are integers that count the number of relevant primes that reduce to that set:
from itertools import chain, combinations
from functools import cache
from collections import defaultdict
from pyprimesieve import primes
primes = [
p for p in primes(10**9) if len(set(str(p))) == len(str(p)) and "0" not in str(p)
]
set_counts = defaultdict(int)
for p in primes:
set_counts[frozenset(map(int, str(p)))] += 1
set_counts will then serve as the base case for our recursion.
Next, we need a way to break down our problem into relevant subproblems. So I wrote a function which will generate all of the ways to split a set into two disjoint nonempty subsets:
@cache
def set_decomps(s):
"""
Generates all possible ways to partition a set s
into two non-empty subsets
"""
l = list(
map(
lambda x: (frozenset(x), s - frozenset(x)),
chain.from_iterable(combinations(s, r) for r in range(1, len(s))),
)
)
return l[: len(l) // 2]
Finally, we should be able to just use a simple memoized approach to use these together to solve the problem, and all of its subvariants.
@cache
def dp(s):
"""
Returns the number of ways to create a set containing prime numbers
Such that the set of all the digits in the primes is equal to s
With no duplicates or extra digits
"""
base = set_counts[s]
if len(s) > 1:
for a, b in set_decomps(s):
base += dp(a) * dp(b)
return base
print(dp(frozenset(range(1,10)))) # prints 114566, which is wrong
Obviously there is a flaw in my approach.
The flaw is this. Consider the set {2,5,47,89,631}. Different initial splits can lead to it. One is {1,2,3,6}, {4,5,7,8,9} and another is {1,3,6,8,9} {2,4,5,7}. There are many more. And therefore you are overcounting.
To leave you the fun of the problem, I won't tell you how to fix this overcounting. I'll just tell you that if you are counting multiple ways to get to a particular set, then your number will be too high.