프로젝트 오일러 043
특정한 조건을 만족하는 0-9 팬디지털 수
10자리 정수는 10억 단위의 값입니다. 그러니 당연히 10억~99억 사이의 범위를 루프를 돌 생각은 하지 않는 것이 좋습니다. 문제에서는 세부적인 조건 7가지를 제시하고 있고, 10자리 0-9팬디지털 수로 대상이 제한되어 있습니다. 그래서 루프를 최대한 줄이는 것이 이 문제의 핵심입니다.
빠른 실패
7개의 조건을 모두 만족한다고 했으니, d1부터 d10까지를 10단계의 루프를 돌면서 조건을 만족하지 않는 경우에 해당 위치의 숫자 이후의 모든 루프를 continue로 통과해버리는 방법을 사용할 수 있습니다. 다만 이 방법은 10단계의 루프를 일일이 작성해야 하기 때문에, 작성하면서도 이게 맞나 싶은 생각이 들 수 있습니다.
from functools import reduce
def test():
res = []
dump = lambda xs: reduce(lambda x, y: x * 10 + y, xs)
for d1 in range(1, 10):
for d2 in range(10):
if d1 == d2:
continue
for d3 in range(10):
if d3 in (d1, d2):
continue
for d4 in range(10):
if d4 in (d1, d2, d3):
continue
if d4 % 2 > 0:
continue
for d5 in range(10):
if d5 in (d1, d2, d3, d4):
continue
if (d5 + d4 + d3) % 3 > 0:
continue
for d6 in range(10):
if d6 in (d1, d2, d3, d4, d5):
continue
if d6 not in (0, 5):
continue
for d7 in range(10):
if d7 in (d1, d2, d3, d4, d5, d6):
continue
k = d7 + d6 * 10 + d5 * 100
if k % 7 > 0:
continue
for d8 in range(10):
if d8 in (d1, d2, d3, d4, d5, d6, d7):
continue
k = d8 + d7 * 10 + d6 * 100
if k % 11 > 0:
continue
for d9 in range(10):
if d9 in (d1, d2, d3, d4, d5, d6, d7, d8):
continue
k = d9 + d8 * 10 + d7 * 100
if k % 13 > 0:
continue
for d10 in range(10):
if d10 in (d1, d2, d3, d4, d5, d6, d7, d8, d9):
continue
k = d10 + d9*10 + d8*100
if k % 17 > 0:
continue
res.append(dump([d1, d2, d3, d4, d5, d6, d7, d8, d9, d10]))
break
print(sum(res))
print(res)
test()당연하면서도 이상하게도 이 방법으로는 답을 구할 수 있습니다. 그리고 앞부분에서 숫자가 겹치거나 조건에 맞지 않을 때 남은 가능성을 모두 건너뛰기 때문에 절대적인 처리 시간도 오래 걸리지 않습니다. 하지만 10단계나 네스팅되는 이런 루프를 파이썬으로 작성해도 좋은지는 잘 모르겠습니다.
과도한 들여쓰기가 부담이 된다면 아래와 같이 지능형 리스트를 사용하는 방법도 있습니다. 똑같은 알고리듬이기 때문에 마음에 들지 않지만 그래도 들여쓰기는 좀 절약할 수 있습니다.
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()순열을 만들기
0-9 팬디지털 수는 0,1,2,···,8,9의 10개 숫자의 사전식 순열로 모두 순회할 수 있습니다. 그 수는 380만개 정도로 여전히 많지만 10억개보다는 0.3% 수준으로 훨씬 적죠. 그리고 사전식 순열을 순회하는 동안에도 ‘빠른 실패’ 조건을 활용할 수 있다면 아주 효율적으로 문제를 해결할 수 있습니다. 따라서 사전식 순열을 생성하는 알고리듬을 직접 구현할 필요가 있고, 해당 로직 내부에서 각 단계의 조건을 검사하도록 합니다.
순열을 구현하는 방법은 여러 가지가 있습니다. 재귀적인 방법을 생각할 수 있습니다. 만약 앞자리가 1이라면 1을 제외한 숫자 9개의 모든 순열 앞에 1을 붙이면 됩니다. 이것을 모든 순열의 목록을 리턴하는 함수로 만들고자 한다면 상당히 코드가 복잡하고 읽기가 어려워집니다. 그러나 제너레이터를 사용하면 간결하고 쉬운 형태로 작성할 수 있습니다. 특히 함수형 언어에서 재귀를 통해 세부 문제의 처리를 위임하는 형태로 코드를 작성하면 아주 깔끔하고 가독성도 좋습니다.
helper()라는 제너레이터가 실제로 순열을 생성합니다.helper(head, tail, k)의 형태로 파라미터가 구성됩니다.head는 이미 선택된 원소들이고,tail은 아직 선택하지 않은 원소입니다.k는 레벨을 말합니다. 더 이상 내려가지 않을 단계까지 왔다면head를 yield하면 됩니다. 값을 생성한 후에는 return 해야 합니다.- 각 단계에서는 tail의 각 원소에 대해서, 이를 head에 추가하고, tail에는 그 원소를 뺀 다음 재귀적으로 제너레이터를 호출합니다. 여기서
yield from이라는 멋진 문법을 사용할 수 있습니다. 주의해야 할 것은 루프를 돌면서 이를 처리해야 하기 때문에pop(),append()를 사용해서는 안된다는 점입니다.
순열을 생성하는 제너레이터는 설명보다는 코드를 보는 편이 나을 것 같습니다.
def perms[R](xs: list[R], k:int=0) -> Generator[list[R], None, None]:
def helper(head: list[R], tail: list[R], k: int = 0):
if k == 0:
yield head
return
for (i, x) in enumerate(tail):
yield from helper([*head, x], [*tail[:i], *tail[i+1:]], k - 1)
if k == 0:
k = len(xs)
yield from helper([], xs, k)이 제너레이터를 조금 수정하여, 각 단계에서 가드 조건을 검토하고, 조건에 맞지 않는 경우 빠르게 실패하도록 합니다.
def maker():
ks = [1, 1, 1, 1, 2, 3, 5, 7, 11, 13, 17]
def helper(head: list[int], tail:list[int], k:int) -> Generator[int, None, None]:
# 첫번째 숫자는 0이면 안됨
if k == 1:
if head[0] == 0:
return
if k >= 3:
# 3자리 이상부터는 정해진 값으로 나누어 떨어지는지 검사
a, b, c = head[-3:]
if (a * 100 + b * 10 + c) % ks[k] > 0:
return
if k == 10:
yield dump(head)
return
for (i, x) in enumerate(tail):
yield from helper([*head, x], [*tail[:i], *tail[i+1:]], k+1)
yield from helper([], list(range(10)), 0)
print(sum(maker()))