project euler 43

오일러 프로젝트 43 번

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.

d1을 첫째 자리수, d2를 둘째 자리수...라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐
위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=43

좀 무지막지한 문제다. 일단 문제의 조건을 글자 그대로 옮기면 다음과 같이 되는데…

from functools import reduce

def ls_to_int(*xs):
  return reduce(lambda x, y: x*10 + y, xs, 0)

def e43():
  r = []
  for d1 in set(range(10)):
    for d2 in set(range(10)) - {d1}:
      for d3 in set(range(10)) - {d1, d2}:
        for d4 in set(range(10)) - {d1, d2, d3}:
          if (d2*100 + d3*10 + d4) % 2 == 0:
            for d5 in set(range(10)) - {d1, d2, d3, d4}:
              if (d3*100 + d4*10 + d5) % 3 == 0:
                for d6 in set(range(10)) - {d1, d2, d3, d4, d5}:
                  if (d4*100 + d5*10 + d6) % 5 == 0:
                    for d7 in set(range(10)) - {d1, d2, d3, d4, d5, d6}:
                      if (d5*100 + d6*10 + d7) % 7 == 0:
                        for d8 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7}:
                          if (d6*100 + d7*10 + d8) % 11 == 0:
                            for d9 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7, d8}:
                              if (d7*100 + d8*10 + d9) % 13 == 0:
                                for d10 in set(range(10)) - {d1, d2, d3, d4, d5, d6, d7, d8, d9}:
                                  if (d8*100+d9*10+d10) % 17 == 0:
                                    r.append(ls_to_int(d1, d2, d3, d4, d5, d6, d7, d8, d9, d10))

  print(sum(r))  
%time e43()

# 16695334890
# Wall time: 124 ms

좀 더 알아보기 쉽게 구조를 변경해보자.

알고리듬은 다음과 같다.

  1. 1~9 사이의 숫자로부터 각각 시작한다.
  2. 각 숫자의 뒤에 남은 숫자들을 하나씩 더 붙여나간다.
  3. 3회차부터는 각 조건들을 검사해서 맞는 것만 남긴다.
  4. 9회차까지 완료하면 조건을 만족하는 숫자들만 남게된다.

조건의 경우, 숫자의 길이로부터 몇 번째 소수로 나눠봐야 하는지 알 수 있다. 행수는 다소 많아지지만 훨씬 깔끔하다.

from functools import reduce

def check(xs:str, c:str) -> bool:
    checkers = [1, 1, 1, 2, 3, 5, 7, 11, 13, 17]
    l = len(xs)
    a = int(xs[-2])
    b = int(xs[-1])
    return (a * 100 + b * 10 + int(c)) % checkers[l] == 0

def getValue(xs:str) -> int:
    return reduce(lambda x, y: 10*x+y, [int(c)  for c in xs], 0)

def test(xs:[str]) -> [str]:

    depth = len(xs[0])

    if depth > 9:
        return xs

    result = []

    for x in xs:
        for i in "0123456789":
            if i not in x:
                if len(x) > 2:
                    if check(x, i):
                        a = x + str(i)
                        result.append(a)
                else:
                    a = x + str(i)
                    result.append(a)

    return test(result)

def e43():
    xs = [str(i) for i in range(1, 10)]
    y = test(xs)
    print(sum((getValue(i) for i in y)))

%time e43()
# 16695334890
# Wall time: 252 ms