问Python中的euler 43项目

EN

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

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