Project Euler 32

Question: 

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

문제:

n자리 숫자 중 1부터 n까지 정확히 한 번씩만 사용해서 만든 수를 팬디지털수라 한다. 예를 들어, 15234는 1부터 5까지 사용해서 만든 팬디지털수이다.

더 재미있는 팬디지털은 39 × 186 = 7254 같은 것이다. 곱해진 두 수와 그 곱은 1부터 9까지 사용해서 만든 팬디지털 곱이 된다.

위의 예와 같이 1부터 9까지 사용해서 만들 수 있는 모든 팬디지털 곱에 대해 그 곱들의 합을 구하여라.

힌트: 몇몇 곱들은 여러 방법의 곱으로 다르게 표현될 수 있지만 합에는 한 번만 더해야 한다.

Solution:

1부터 9까지 수를 한 번만 사용해서 m * n = l 꼴을 만들어야한다.

from itertools import permutations
import time
nums = '123456789'
num = list() # m * n = L의 [m,n,L]를 저장한다.
results = list() # L을 저장한다.

start = time.time()

for i in range(1,5): # multiplicand 는 4자리수 이하임을 가정한다.
    for j in permutations(nums,i): # i개의 combination 을만든다. j는 multiplicand
        multiplicand = ''.join(list(j))
        a = len(multiplicand) # j의 자릿수를 찾는다.
        
        for k in range(1,3): # multiplier 는 2자리수 이하임을 가정한다.
            for x in permutations(''.join(list(set(nums) - set(j))),k): 의 수를 제외하고 k개의 조합에서 고른다.
                multiplier = ''.join(list(x))
                result = int(multiplicand) * int(multiplier) # 곱셈연산 
                original = list(multiplier) + list(multiplicand) + list(str(result))
                if len(original) == len(set(original)) and len(original) == 9: #pandigital 판별
                    if not '0' in str(result): # 0이 들어가있는 경우를 걸러준다.
                        num.append([int(multiplicand),int(multiplier),result])
                        results.append(result)

print(sum(list(set(results))))
print("Found in...{:.2f}s".format(time.time() - start))

0.32s 걸렸다.

num에 저장된 모든 경우의 수들이다.

결과 값들은 중복되는 것들이 있음으로 주의하자.

45228