프로젝트 오일러 043

문제

43번 문제

부분열에 관련된 특이한 성질을 가진 모든 팬디지털 수의 합

사이냅소프트

10자리 팬디지털 수

문제가 제시하는 여러 조건을 모두 만족하는지 검사하는 함수는 충분히 작성할 수 있습니다. 10자리 수에 이 조건으로 필터링한 결과만 추려서 그 합을 구하면 되는 간단한 문제입니다만... 10자리 수가 좀 많다는 게 난관입니다. 10억개가 약간 안되기 때문에 파이썬에서 그만큼 루프를 도는 건 딱 봐도 아닌 것 같습니다. 그래서 반복 횟수를 줄이는 방법이 필요합니다.

빠른 실패

7개의 조건을 모두 만족한다는 것의 반대는 7개의 조건 중 어느 하나라도 만족하지 않는다는 것입니다. 만약 첫번째 조건을 만족하지 않는다면 다른 나머지 조건에 대해서는 평가해 볼 필요도 없이 실패입니다. 이렇게 조건을 체크하는 성능을 높이는 것은 도움이 될까요?

그다지 큰 도움은 되지 않을 겁니다. 파이썬 루프에서 가장 오버헤드가 큰 부분은 for 루프 그 자체이기 때문에, 다른 방법을 사용해서 루프의 횟수 자체를 줄이는 것이 중요합니다.

반대로 조건으로 10자리 정수를 미리 걸러낸다면 어떨까요? 10억까지의 수 중에서 0으로 시작하는 수는 실제로는 9자리 정수이니 0으로 시작하는 모든 수는 범위 자체에서 뺄 수 있습니다. d4(4번째 자리) 숫자가 홀수라면 1번 조건을 만족하지 않으니, 그 뒷자리에 오는 숫자들도 모두 관심이 없습니다. 이들만 제외해도 6!×5 = 3,600 개의 후보가 빠지게 됩니다.

이런식으로 걸러내는 것을 아래와 같이 작성할 수 있습니다. 거의 하드 코딩에 가깝기 때문에 너무 이상해보이지만, 일단 실행해보면 기분 상할만큼 빠르게 답이 튀어나옵니다.

from functools import reduce

dump = lambda xs: reduce(lambda x, y: 10 * x + y, xs)


def main():
    res = [
        (d1, d2, d3, d4, d5, d6, d7, d8, d9, d10)
        for d1 in range(1, 10)
        for d2 in range(10)
        if d1 != d2
        for d3 in range(10)
        if d3 not in (d1, d2)
        for d4 in range(0, 10, 2)
        if d4 not in (d1, d2, d3)
        for d5 in range(10)
        if d5 not in (d1, d2, d3, d4) and (d3 + d4 + d5) % 3 == 0
        for d6 in (0, 5)
        if d6 not in (d1, d2, d3, d4, d5)
        for d7 in range(10)
        if d7 not in (d1, d2, d3, d4, d5, d6) and (d5 * 100 + d6 * 10 + d7) % 7 == 0
        for d8 in range(10)
        if d8 not in (d1, d2, d3, d4, d5, d6, d7)
        and (d6 * 100 + d7 * 10 + d8) % 11 == 0
        for d9 in range(10)
        if d9 not in (d1, d2, d3, d4, d5, d6, d7, d8)
        and (d7 * 100 + d8 * 10 + d9) % 13 == 0
        for d10 in range(10)
        if d10 not in (d1, d2, d3, d4, d5, d6, d7, d8, d9)
        and (d8 * 100 + d9 * 10 + d10) % 17 == 0
    ]
    print(res)
    print(sum(map(dump, res)))


if __name__ == "__main__":
    main()

팬디지털 수

팬디지털 수의 정의는 '모든 숫자가 한 번씩은 쓰인다'는 뜻이고, 10자리 0-9 팬디지털이라면 모든 숫자가 한 번씩만 쓰인다는 뜻입니다. 10자리 정수를 그저 10개의 정수 리스트라고 생각한다면, 모든 0-9 팬디지털 수는 0 - 9까지의 숫자들의 사전식 순열이라고 볼 수 있습니다.

사전식 순열을 만들 때, 각 레벨에 따라서 체크하는 함수를 호출하고 체크에 실패하면 그 이후 순열을 만들필요 없이 다음으로 넘어가는 방식으로 작성하면 위와 비슷하게 최대한의 효율을 뽑을 수 있지 않을까요?

def nperms():
    checkers = [0, 0, 0, 0, 2, 3, 5, 7, 11, 13, 17]
    def helper(head, tail, k):
        if k == 1 and head[-1] == 0:
            return
        if k > 3:
            a, b, c = head[-3:]
            if (100 * a + 10 * b + c) % checkers[k] != 0:
                return
        if k == 10:
            yield head
            return
        for (i, x) in enumerate(tail):
            yield from helper((*head, x), (*tail[:i], *tail[i+1:]), k + 1)


print(sum(map(dump, nperms())))