Project Euler #43 - sub-string divisibility

프로젝트 오일러 43번

2,3,4번째 자리는 2로 나누어 떨어지고, 3,4,5번째 자리는 3으로, 4,5,6번째 자리는 7로... 나누어 떨어지는 10자리 pandigital 수를 모두 더하면?

답을 아는 입장에서.. 그런 조건을 만족하는 경우는 6개 밖에 안 되고, 엑셀을 써서 답을 찾을 수도 있다.

문제의 의도가 이게 맞는지 모르겠지만, 좀 무식한 코딩으로...

(보기에 안 좋아서 그렇지.. 이런 스타일이 속도는 괜찮다. 앞의 동전 문제에서도 마찬가지)

sm = 0
for d8 in range(17,1000,17):
    if d8 < 100 or len(set(`d8`)) == 3:
        r7 = set('1234567890') - set(`d8`)
        for d7 in r7:
            if (int(d7)*100 + d8/10) % 13 == 0:
                r6 = r7 - {d7}
                for d6 in r6:
                    if (int(d6)*100 + int(d7)*10 + d8/100) %11 == 0:
                        r5 = r6 - {d6}
                        for d5 in r5:
                            if (int(d5)*100 + int(d6)*10 + int(d7)) % 7 == 0:
                                r4 = r5 - {d5}
                                for d4 in r4:
                                    if d6 in {'5','0'}:
                                        r3 = r4 - {d4}
                                        for d3 in r3:
                                            if (int(d3)+int(d4)+int(d5)) % 3 == 0:
                                                r2 = r3 - {d3}
                                                for d2 in r2:
                                                    if d4 in set('24680'):
                                                        d1 = list(r2-{d2})[0]
                                                        sm += int(d1+d2+d3+d4+d5+d6+d7+`d8`)

print sm

41번 문제에서 썼던 permutation을 활용하면 코드가 깔끔해진다.

from itertools import permutations

sm = 0
for p in permutations('1234567890'):
    n = ''.join(p)    
    if int(n[7:]) % 17 == 0 and \
        int(n[6:9]) % 13 == 0 and \
        int(n[5:8]) % 11 == 0 and \
        int(n[4:7]) % 7 == 0 and \
        int(n[3:6]) % 5 == 0 and \
        int(n[2:5]) % 3 == 0 and \
        int(n[1:4]) % 2 == 0:
        sm += int(n)

print sm

그런데, 처음 코드는  0.0014초, 두번째 코드는 4.2초. 이 정도 차이면 지저분한 코드쪽이 나아 보인다.