Project Euler #29 - distinct powers

프로젝트 오일러 29번

2이상 100 이하 a, b에 대해 a^b 형태로 표현할 수 있는 수는 몇 개?

4^2 == 2^4 이런 것 때문에 소인수 분해하고 지지고 볶고 해 봤는데.. 그냥 다 세는 게 나은 듯 하다. 기껏 100*100번 loop도는 건데..

print len({a**b for a in range(2,101) for b in range(2,101)})

파이썬의 리스트 표현 굳!!

Project Euler #22 - 이름 숫자

알파벳을 숫자로 변환하고 주어진 공식으로 순위와의 가중합을 구하는 문제

포럼에 올라온 글에 자극받아서 아예 한 줄 코드로 만들어 봤다.

print sum([(i+1)*sum([ord(c)-64 for c in name]) for i,name in enumerate(sorted([name.strip('"') for name in open('p022_names.txt').read().split(',')]))])

ord는 문자에 해당하는 아스키번호를 알려주는 함수라고 한다.

아래와 같이 정상적인(?) 코드를 작성할 수도 있다.

ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alphanum = {}
for i,c in enumerate(ABC):
    alphanum[c] = i + 1

def calcname(name):
    return sum([alphanum[s] for s in name])

with open('/Users/Dongug/Downloads/p022_names.txt') as f:
    names = [name.strip('"') for name in f.readline().split(',')]

rs = 0
for i,name in enumerate(sorted(names)):
    rs += (i + 1) * calcname(name)

print rs

Project Euler #18 - Maximum path sum I

최대합 경로 문제

처음엔 이렇게 풀었다.

st = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

og = []
for line in st.split('\n'):
    og.append([int(e) for e in line.split()])

for i in range(len(og)-1):
    og[i+1][0] = og[i][0] + og[i+1][0]
    for j in range(len(og[i])-1):
        og[i+1][j+1] = max(og[i][j],og[i][j+1]) + og[i+1][j+1]
    og[i+1][-1] = og[i][-1] + og[i+1][-1]
    
print max(og[-1])

포럼 글을 읽다보니.. 삼각형을 뒤집으면 문제가 훨씬 쉽게 풀린다.

st = '''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

og = [[int(e) for e in line.split()] for line in st.split('\n')][::-1]

l = len(og)
for i in range(l):
    for j in range(l - i-1):
        og[i+1][j] += max(og[i][j],og[i][j+1])

print og[-1][-1]

처음 이런 코드를 작성할 때는 어떤 리스트의 몇번째 위치에 어떤 값이 들어 있는지 헷갈려서 머리 싸매고 했었는데.. 100번까지 풀고 블로그 정리용으로 다시 작성하니까 훨씬 쉽다. 조금이나마 발전이 있는 것 같아서 기분 up.

Project Euler #16 - Power digit sum

2^1000 의 숫자들을 다 더하면?

300자리 정도 되겠지만 큰 정수에 강한 파이썬을 믿어보자~

print sum([int(s) for s in str(2**1000)])

2**1000000 계산은 위의 코드보다 빠른 방법이 있는데.. 1000제곱 정도는 이것보다 빠른 방법을 못 찾겠다.

Project Euler #8 - Largest product in a series

1000개의 연속된 숫자들 중 연속된 13개의 곱 중 최대값은?

1. 한칸씩 이동하면서 13개의 곱을 계산하면 된다.
2. 조금 빠르게 하려면, 13개 안에 0이 있는지를 체크해서 있으면 계산 안 하면 된다.
3. 더 빠르게 하려면.. 0이 없도록 숫자들 덩어리를 만들고, 각 덩어리 안에서는 처음 13개의 곱을 구한 다음에 한칸씩 이동하면서 제일 앞의 수로 나누고 한칸 뒤의 수를 곱해주면 된다.

2는 어려워 보이지 않으니.. 먼저 해 보자.

st = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450'''

ns = [int(s) for s in st.replace('\n','')]

def prod(l):
    r = 1
    for i in l: r*= i
    return r

mx = 0
ndigit = 13
for i in range(len(ns)-ndigit):
    if 0 not in ns[i:i+ndigit]:
        p = prod(ns[i:i+ndigit])
        if p > mx: mx = p

print mx

리스트에 들어 있는 값을 모두 더할 때는 간단히 sum(range(10)) 처럼 쓸 수 있다. 리스트에 있는 값을 모두 곱하는 명령어는..?? 없다. 구글링하다 보면, 아주 오래 전 파이썬 개발자(파이썬으로 개발하는 사람 말고 파이썬을 만드는 사람) 중 한 명이 그런 명령어를 만들자고 제안했었는데, 귀도 반 로썸 아저씨가 그런 거 필요 없다고 단칼에 거절한 걸 찾을 수 있다.
위의 코드처럼 별도의 함수를 만들거나, 그게 귀찮으면 아래처럼 reduce 를 쓰면 된다.

from operator import mul
mx = 0
ndigit = 13
for i in range(len(ns)-ndigit):
    if 0 not in ns[i:i+ndigit]:
        p = reduce(mul,ns[i:i+ndigit])
        if p > mx: mx = p

이제 위의 3번을 구현해 보자. 0이 없을 경우 2번은 만번 이상 곱셈을 하지만 3번은 곱셈 1000번, 나눗셈 1000번으로 끝난다. 2번은 0이 있는지 반복해서 체크하는데, 3에서는 한번만 체크할테니 그것도 시간을 아끼는 요인이 될 거다.

ns = [s for s in st.replace('\n','').split('0') if len(s) >= 13]

from operator import mul

def findmx(s):
    t = [int(x) for x in s]
    p = mx = reduce(mul,t[:13])
    for i in range(13,len(t)):
        p /= t[i-13]
        p *= t[i]
        mx = max(p,mx)
    return mx

gmx = 1
for s in ns:
    gmx = max(findmx(s),gmx)

print gmx

5분의 1 정도로 시간이 줄었다.


---
누구나 구현할 수 있는 쉬운 난이도이면서도 생각할 꺼리가 있는 재미있는 문제다. 내가 생각하지 못한 다른 개선 요소가 있을 수도..

Project Euler #6 - Sum square difference

1부터 100까지 더한 다음에 제곱한 수에서, 1, 4, 9, ..., 10000 을 빼면?

파이썬스럽게 list comprehension 을 써 봤다.

sum(range(101)) ** 2 - sum([x*x for x in range(101)])

문제 풀이 끝.


물론 이렇게 할 수도 있다.

sm1 = sm2 = 0
for i in range(101):
    sm1 += i
    sm2 += i*i

print sm1**2 - sm2

요기 페이지 설명에 따르면 파이썬을 만든 귀도 반 로썸 아저씨는 람다함수보다 list comprehension 을 선호한다고 한다. 많이 써 보자!