Project Euler #60 - prime pair sets

프로젝트 오일러 60번 - 소수짝 세트
3, 7, 109, 673은 각각 소수이면서, 두개씩 짝을 지어 붙여도 항상 소수가 된다. 예를 들어 7109, 1097 은 소수.
이런 성질을 만족하는 소수 5개짜리 세트.. 중 5개 숫자 합이 가장 작을 때?

지금까지 풀었던 문제 중에 가장 어려웠다. 계산 시간도 가장 오래 걸렸고.

4개짜리 세트를 만드는 데 673까지의 소수가 필요했으니.. 5개짜리 세트는 10배쯤 더 필요하지 않나..라고 추측해 본다.
일단 10,000까지의 소수를 모두 찾아둔다.
1200개 정도 되는 소수를 5개씩 묶는 방법은 1200^5 / 5! 너무 크다!
Partitioning해 보자. 3으로 나누어 1이 남는 소수들과 2가 남는 소수들로 나누어 볼 수 있다. 둘이 섞여 버리면 3의 배수가 되어 버리므로 10,000 이하 소수들을 다음과 같이 2개의 그룹으로 나누고, 각 그룹 안에서 5개짜리 세트를 찾으면 된다.
[3] + [x for x in primes_under_10000 if x%3 == 1]
[3] + [x for x in primes_under_10000 if x%3 == 2]

(설명이 좀 더 필요할 듯 하다. 각 자리수의 합이 3의 배수이면 이 수는 3의 배수가 되는 것은 모두 알 테고.. 각 자리수의 합이 3으로 나누어 1이 남는다는 것과 이 수를 3으로 나누었을 때 1이 남게 된다는 것은 동치이다. n 이 각 자리수의 합이 3으로 나누어 1이 남는 수라고 하면 n에서 (n보다 작은) 10^k 를 빼면 3의 배수가 된다. 10^k는 3으로 나누어 1이 남는 수이므로 n = (n - 10^k) + 10^k 는 3으로 나누어 1이 남는다. 같은 방법으로 각 자리수의 합이 3으로 나누어 2가 남는다는 것과 이 수를 3으로 나누었을 때 2가 남게 된다는 것은 동치라는 것을 보일 수 있다.)

아무튼.. 600^5 / 120 도 너무 커서 계산 불가! 다른 방법을 찾아야 한다.

일단 두개씩 비교하는 건 600^2 정도에 가능하니까..
chains라는 dictionary에 i번째 소수와 짝이 될 수 있는(두 개를 붙였을 때 소수가 되는) 소수(의 인덱스)를 저장해 둔다
0:{2,5,7,8,10}
1:{2,5,8,11}
2:{5,7,8,10}
...

그리고 chains안에 있는 0, 1, 2.. loop을 돌면서
{2,5,7,8,10} 에서 4개짜리 세트를 골라내고, (예를 들어, (2,5,8,10)이 뽑혔다면)
{5,8,10}이 chains[2]에 포함되는지 체크한다.
포함된다면, {8,10}이 chains[5]에 포함되는지, 10이 chains[8]에 포함되는지 체크한다.
여기까지 조건을 만족하면 합을 출력한다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

def choose4(lst):
    l = len(lst)
    out = []
    for i in range(l):
        for j in range(i+1,l):
            for k in range(j+1,l):
                for w in range(k+1,l):
                    out.append((lst[i],lst[j],lst[k],lst[w]))
    return out

def prob60(pnt,pn):
    l, chains = len(pnt), {}
    for i in range(l):
        for j in range(i+1,l):
            if chk_pn(int(`pnt[i]`+`pnt[j]`),pn) and chk_pn(int(`pnt[j]`+`pnt[i]`),pn):
                if i in chains: chains[i].add(j)
                else: chains[i] = {j}
    
    for i in chains:
        if len(chains[i]) >= 4:
            for comb in choose4(sorted(list(chains[i]))):
                a,b,c,d = comb
                try:
                    if {b,c,d} <= chains[a] and {c,d} <= chains[b] and d in chains[c]:
                        print pnt[i]+pnt[a]+pnt[b]+pnt[c]+pnt[d]
                except:
                    pass
    

pn = rwh_primes1(10000)
pn1 = [3]+[x for x in pn if x%3==1]
pn2 = [3]+[x for x in pn if x%3==2]

prob60(pn1,pn)
prob60(pn2,pn)

40초..
13 + 5197 + 5701 + 6733 + 8389 = 26033
여러개 나왔으면 그 중 가장 작은 것을 고를텐데, 만 이하 소수들로는 한 세트 밖에 못 만든다.
lowest sum을 찾는 문제니까 (작은수)+(작은수)+(작은수)+(작은수)+(만을 약간 넘는 수) 같은 경우가 답이 될 수도 있다.
2만5천 이하의 소수로 확장해서 다시 돌려보면 될텐데.. 오래 걸리는 걸 돌리기는 귀찮다.

Project Euler #59 - XOR 암호 해독

프로젝트 오일러 59번 - XOR decryption

이진수로 된 문자열 '10011101'을 '0101'이라는 key를 이용해서 XOR 암호화한다고 하자.

우선 앞부분 1001 과 key를 비교하면 1100 이 된다.(XOR은 같으면 0, 다르면 1로 만든다)

뒷부분 1101 과 key를 비교하면 1000 이 된다.

그래서 10011101 을 암호화하면 11001000이 된다. 

같은 방법으로, 11001000 을 '0101'로 XOR연산을 하면, 10011101 이 되어 암호를 풀게 된다.

key가 3자리 소문자 알파벳일 때 첨부한 파일의 암호를 풀고, 풀린 텍스트의 ASCII값을 모두 더하라.

1. 암호를 찾는다.

1) (1,4,7,10, ... 자리의 문자), (2,5,8,... 자리의 문자), (3,6,9,...자리의 문자)를 나눈다. 이들 각각에 대하여,

2) 모든 소문자에 대하여, 암호가 a일 때 '풀린 문자'가 정상적인 영어 알파벳인 개수, ...., 암호가 z일 때... 를 센다. 정상적인 영어 알파벳이 가장 많은 경우를 암호로 본다. 

2. 암호를 푼다.

#ord('A')=>65, ord('Z')=>90, ord('a')=>97, ord('z')=>122, ord(' ')=>32, ord('.')=>46
eng = set(range(65,91)+range(97,123)+[32,46])
encrypted = [int(x) for x in open('p059_cipher.txt').read().split(',')]
passwd = []
for i in range(3):
    enc3=[x for k,x in enumerate(encrypted) if k%3==i]
    tmpdic = {}
    for pw in range(97,123):
        tmpdic[pw] = len([x^pw for x in enc3 if x^pw in eng])
    passwd.append( max(tmpdic, key=tmpdic.get))

decrypted = [x^passwd[k%3] for k, x in enumerate(encrypted)]
#print passwd
#print ''.join([chr(x) for x in decrypted])

print sum(decrypted)

암호는 'god' (103,111,100), 암호화된 본문은 요한복음 1장 앞부분이다.

ord는 22번에서 나왔던 함수.

XOR은 컴퓨터에는 기본적인 연산이라 간단히 쓰는 방법이 있을 듯 했다. 역시나 구글링해보았더니 ^를 쓰면 된다고 한다. 어려워 보였지만, 보기만큼 어렵지는 않았다.

Project Euler #58 - spiral primes

프로젝트 오일러 58번 - 나선형 숫자 배열에서의 소수
5  4  3
6  1  2
7  8  9...
처럼 1부터 나선형으로 숫자를 하나씩 늘려갈 때 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 될 때, 한 변의 길이는?
문제의 예시를 보면, 변의 길이가 7일 때 소수의 비율은 62% 정도이다. 10% 이하로 떨어지려면 꽤 큰 수가 필요할 듯 하다.

변의 길이가 늘어날 때마다 1. 대각선에 추가되는 숫자 네 개가 어떤 것인지 공식을 만들고, 2. 그 숫자들이 소수인지 체크하고, 3. 그 때마다 소수 비율이 10% 이하로 떨어지는지 체크한다.
1. 28번과 같은 문제이다. 오른쪽 아래로 1, 9, 25, 49, ... 패턴을 보이는 데에서 시작하면 된다.
2. 100억을 넘지 않는다고 가정했을 때, a. 100억까지의 모든 소수를 찾아둔다. b. 10만까지의 소수를 찾아두고 이를 이용해서 소수인지 체크한다. 중 b가 메모리 사용이나 속도면에서 더 낫다.
3. 그냥 세면 된다.

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p ** 2 > n: return True

chk_N = 100000
pn = rwh_primes1(chk_N)

nprimes = 0
for slen in range(3,chk_N,2):
    if chk_pn(slen*slen - (slen-1),pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*2,pn): nprimes += 1
    if chk_pn(slen*slen - (slen-1)*3,pn): nprimes += 1
    if nprimes / (slen*2-1.0) < .1:
        print slen
        break

1.8초. 꽤 큰 숫자까지 체크하는 거니까 이정도로 만족

Project Euler #57 - square root convergents

프로젝트 오일러 57번 - 루트2의 전개
sqrt(2) = 1 + 1 / ( 2 + 1 / ...) 로 전개할 수 있다. 무한전개를 하나씩 끊어서 풀면,
3/2
7/5
17/12
41/29
99/70
...
이렇게 된다. 1000번까지 전개해 보면서 분자와 분모의 자리수가 다른 경우는 몇 번인지 세어 본다.

계산해 보면(또는 관찰해 보면),
뒷분모 = 앞분자+앞분모
뒷분자 = 뒷분모+앞분모

그러면 찾는 것이 어렵지 않다.

n, d, cnt = 3, 2, 0
for i in range(2,1001):
    d, n = d+n, d+d+n
    if len(str(d)) < len(str(n)): cnt += 1

print cnt

Project Euler #56 - powerful digit sum

프로젝트 오일러 56번 - 큰수의 숫자 합
a, b가 각각 100미만일 때, a^b의 각 자리의 수를 모두 더한 값의 최대값은?

a, b를 2부터 99까지 바꿔가면서 모두 계산해 보면 된다.
길게 쓰면,

mx = 0
for a in range(2,100):
    n = a
    for b in range(2,100):
        n *= a
        mx = max(mx, sum([int(x) for x in str(n)]))

print mx

짧게 쓰면,

print max([sum([int(x) for x in str(a**b)]) for a in range(2,100) for b in range(2,100)])

시간은 거의 같다. 각각 0.6초


좀 더 생각해 보면.. 4^8 의 자리수 합보다는 49^89의 합이 훨씬 큰 거다. 그럼 a, b를 2부터 99까지 움직이는 대신 90부터 99까지 움직여봐도 될 것 같다.

print max([sum([int(x) for x in str(a**b)]) for a in range(90,100) for b in range(90,100)])

0.14초. 당연한 얘기지만, 95부터 99까지 체크하는 걸로 바꾸면 더 줄어든다.

Project Euler #55 - Lychrel numbers

프로젝트 오일러 55번 - Lychrel 수
많은 경우, 어떤 수에다가 자기자신을 뒤집은 수를 더하는 과정을 반복하면 palindrome(뒤집어도 자기 자신인 수)가 된다. 예외적인 수를 Lychrel수라고 하는데, 이론적으로 증명할 수는 없지만, 위의 과정을 50번 반복해도 palindrome이 안 된다면 영원히 안 되는 것으로 간주해도 된다. 10000 보다 작은 Lychrel수는 몇 개?

문제는 길지만 풀이 과정은 짧다. 중간에 cache역할 하는 dict를 넣어봐도 시간이 별로 줄지 않는다.

def Lychrel(n):
    for i in range(50):
        n = n + int(str(n)[::-1])
        if str(n) == str(n)[::-1]:
            return False
    return True

rs = 0
for i in range(1,10000):
    if Lychrel(i): rs += 1

print rs

Project Euler #54 - Poker hands

프로젝트 오일러 54번 - 포커패
첨부된 파일에서 1번이 2번을 이기는 경우는 몇 번?

포커 규칙을 모르는 사람은 설명을 읽다가 포기할 문제다.
포커 규칙을 아는 사람도 귀찮아서 포기하기 딱 좋은 문제다.
왜 이걸 하고 있어야 하나.. 싶은 생각이 들지만 그래도 풀어보기로..
패를 점수로 바꾸는 함수를 정의했다. 점수패 0, 원패어 1, 투패어 2, ... 스트레이트플러시 8.
점수가 똑같으면 가장 높은 숫자로 비교해야 하니까(그리고, 가장 높은 숫자가 똑같으면 두번째 높은 숫자로... 동점이면 세번째 숫자... 또 동점이면 네번째 숫자, 그래도 동점이면 다섯번째 숫자로 비교해야 하니까) 높은 숫자들을 역시 점수로 변환한다.
모든 숫자가 똑같을 때 스페이드가 다이아몬드보다 높다거나 하는 규칙도 있지만 여기 문제 설명에 없으니까 코드로 구현할 때는 생략한다.

dic = {'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9,'T':10,'J':11,'Q':12,'K':13,'A':14}

#str_cards = '9H 4D JC KS JS'
def cardreader(str_cards):
    return [(dic[x[0]],x[1]) for x in str_cards.split(' ')]

#cards = [(9, 'H'), (4, 'D'), (10, 'C'), (12, 'S'), (10, 'S')]

def score(cards):
    '''
    Score - ABBCCDDEEFF
    A: high card, 1-pair, 2-pair, ...
        0 - high
        1 - 1-pair
        2 - 2-pairs
        3 - three of a kind
        4 - straight
        5 - flush
        6 - full house
        7 - four of a kind
        8 - straight flush
    BB: highest number
    CC,DD,EE,FF: highest, if none, 00
    '''
    A=B=C=D=E=F=0
    nums = [x[0] for x in cards]
    shapes = [x[1] for x in cards]
    if len(set(nums)) == 5:
        if max(nums) - min(nums) == 4:
            A = 4
            B = max(nums)
            if len(set(shapes)) == 1:
                A = 8
        elif len(set(shapes)) == 1:
            A = 5
            B, C, D, E, F = sorted(nums,reverse=True)
        else:
            A = 0
            B,C,D,E,F = sorted(nums,reverse=True)
    elif len(set(nums)) == 4:
        A = 1
        for x in nums:
            if nums.count(x) == 2: B = x
        C,D,E = sorted([x for x in nums if x != B],reverse=True)
    elif len(set(nums)) == 3:
        for x in nums:
            if nums.count(x) == 3:
                A = 3
                B = x
                C, D = sorted([x for x in nums if x != B], reverse=True)
        if A != 3:
            A = 2
            for x in nums:
                if nums.count(x) == 1: D = x
            tmp = set(nums) - {D}
            B, C = max(tmp), min(tmp)
    elif len(set(nums)) == 2:
        for x in nums:
            if nums.count(x) == 4:
                A = 7
                B = x
                C = max(set(nums) - {B})
        if A != 7:
            A = 6
            for x in nums:
                if nums.count(x) == 3:
                    B = x
                    C = max(set(nums) - {x})
    return A*10**10 + B*10**8 + C*10**6 + D*10**4 + E*10**2 + F


rs = 0
for line in open('p054_poker.txt').readlines():
    p1, p2 = line[:14], line[-15:-1]
    if score(cardreader(p1)) > score(cardreader(p2)):
        rs += 1

print rs