Python 中的欧拉项目 43

Question

我遇到了另一个困难的欧拉计划问题 Link to the problem

我的第一直觉是尝试一个简单的暴力解决方案，这花了太多时间运行。

所以我想到了一个更好的解决方案，但我不知道如何编码。

我想：

生成所有必要的三胞胎。
把所有的组合放在一起。
计算总和。

我执行了第 1 步，结果如下所示：

Multiples of 17: [[0, 1, 7], [0, 3, 4], [0, 5, 1], [0, 6, 8], [0, 8, 5], [1,   0, 2], [1, 3, 6], [1, 5, 3], [1, 7, 0], [1, 8, 7], [2, 0, 4], [2, 3, 8], [2, 8, 9], [3, 0, 6], [3, 4, 0], [3, 5, 7], [3, 7, 4], [3, 9, 1], [4, 0, 8], [4, 2, 5], [4, 5, 9], [4, 7, 6], [4, 9, 3], [5, 1, 0], [5, 2, 7], [5, 6, 1], [5, 7, 8], [6, 1, 2], [6, 2, 9], [6, 8, 0], [6, 9, 7], [7, 1, 4], [7, 3, 1], [7, 4, 8], [7, 6, 5], [7, 8, 2], [8, 1, 6], [8, 5, 0], [8, 6, 7], [9, 0, 1], [9, 1, 8], [9, 3, 5], [9, 5, 2], [9, 8, 6]] etc...

现在对我来说棘手的部分来了。我尝试将它们与嵌套循环放在一起，但这真的很混乱。如果您有任何建议，请告诉我:)

Answer 1

首先，蛮力解决方案几乎不需要任何时间运行。

正如@MooingRawr 所建议的那样，如果您使用 itertools.permutations，则只有 ~ 0.9 x 9! 0123456789 的排列不要以零开头。

from itertools import permutations

primes = [17, 13, 11, 7, 5, 3, 2]

total = 0

# Generate permutations of 10 distict digits -- 10 factorial
for i in permutations('0123456789'):

  # Discard those that begin with zero -- one-tenth of 10!
  if i[0] == '0':
    continue 

  # Convert into a string and assume that it is valid
  n = ''.join(list(i))
  valid = True

  # Check if the last three digits are divisible by 17, ...
  #    ... then shift left and check if those digits are divisible by 13, etc.
  for j in xrange(0, len(primes)):
    x = n[len(primes) - j:len(primes) - j + 3]
    if int(x) % primes[j]:
      valid = False
      break

  # Print and add
  if valid:
    print 'Valid number: %s' % n
    total += int(n)

print 'Total: %d' % total

如果你运行这个解决方案 here，它会在几秒钟内运行，这对 PE 来说应该没问题。

不过，您提出的方法确实效率更高。请注意，您硬编码了七个循环，我只是使用 factors 来生成它们，其中 factor[i] 是 d_i d_i+1 d_i+2.

您担心生成所有组合，但使用递归这很简单，每次迭代都会检查最后两位数字并找到有效的下一位数字。

factors = [1, 2, 3, 5, 7, 11, 13, 17]
valid_len = len(factors)
valid_sequences  = []
total = 0

# Checks for a 3-digit number with 3 unique digits
def not_unique(digits):
  return (digits[0] == digits[1]) or (digits[1] == digits[2]) or (digits[0] == digits[2])


# For each of the prime numbers, generate all valid triples that have unique digits
for i in xrange(0 ,len(factors)):
  current_map = {}
  for j in xrange(factors[i], 1000, factors[i]):
    digits = str(j).zfill(3)

    # Prune those numbers that have non-unique digits
    if not_unique(digits):
      continue

    # current_map is of the form {'d1d2':[list of all possible valid d3s], ...}
    if digits[:2] not in current_map:
      current_map[digits[:2]] = [digits[2]]
    else:
      current_map[digits[:2]].append(digits[2])

  valid_sequences.append(current_map)


# Checks each triple starting with the 3 most significant digits
# Get the last two digits, and find all the valid values for the next one digit
# Perform recursively
def get_matches_starting_with(sequence, index):
  global total
  if index == valid_len:
    print 'Valid number: %s' % sequence
    total += int(sequence)
  else:
    pair = sequence[-2:]
    if pair in valid_sequences[index]:
      for digit in valid_sequences[index][pair]:
        if not digit in sequence:
          get_matches_starting_with(sequence + digit, index + 1)

all_matches = []
for pair in valid_sequences[0]:
  if pair[0] == '0':
      continue
  for digit in valid_sequences[0][pair]:
    triple = pair + digit
    all_matches.append(get_matches_starting_with(triple, 1))

print 'Total: %d' % total

您可能想要运行解决方案 here 并可能在中间步骤打印值以查看发生了什么。

p运行探索状态的数量仍有很多机会。您的方法将其从 3265920 降低到大约 3000。

Python 中的欧拉项目 43

Project euler 43 in Python

python

list

project