Project Euler. #14. Longest Collatz sequence

By | 2013/03/01

Project Euler (http://projecteuler.net/) 문제13

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

다음의 수열은 양의 정수의 집합으로 정의된다 :

n → n/2 (n is even)
n → 3n + 1 (n is odd)

위의 룰을 이용하여 13부터 시작하면 다음과 같은 순서가 나온다 :

13 40 20 10 5 16 8 4 2 1

이 수열(13에서 시작하고 1로 끝나는)은 10개의 숫자로 이루어져있다. 비록 이것이 증명된 바는 아니지만 (Collatz Problem), 어떤 숫자로 시작하더라도 1로 끝이 난다고 간주된다.

100만 아래의 숫자중, 어떤 숫자가 가장 긴 체인을 만들어 내는가?

주의 : 체인이 시작되고 나서 100만이 넘는 숫자가 나오는 것은 가능하다.

처음에 Maximum Chain 수를 구하라는지 알고, 이것을 구해서 525를 입력했는데 자꾸 틀렸다는 메시지만 떴다. 이게 아닌가 싶어서 삽질하다가 문제를 다시 한번 읽고서야 Maximun Chain을 만들어내는 시작 숫자를 묻는 것임을 알고 제대로 된 답을 입력할 수 있었다. 지난 번에도 그랬는데, 항상 문제를 제대로 읽어야지 하면서도 종종 실수를 하게 된다.


def nextNum(n):
    numOfChain = 1
    while n!=1:
        if n%2==0:
            n=n/2
        else:
            n=3*n+1
        numOfChain +=1
    return numOfChain

n=1
chains = []
while n<1000000:
    chains.append(nextNum(n))
    n+=1
print chains.index(max(chains))+1

&#91;/python&#93;

1부터 100만 이하의 숫자를 하나씩 검사하면서 시작 숫자들마다의 모든 체인 수를 리스트에 저장했다. 그리고 해당 리스트에서 가장 높은 체인 수의 인덱스에 +1을 해줌으로서 정답을 찾아내는 방식으로 해결하였는데, 정답을 도출해내는데 약 20여초가 소모된다. 이러면 또 불길해지지... 분명 더 좋은 방법이 있을텐데. 수열을 검사하다가 이미 체인이 얼마인지 체크한 적이 있는 시작 숫자가 나오면 더 이상 규칙대로 다음 숫자를 확인해볼 것도 없이 그냥 넘어가면 될 것이라는 구상만 하고 더 이상 코딩을 접었다. 시간도 워낙 늦은 새벽이었고 잠도 많이 오고...

정답을 입력하고 다른 사람들의 코드를 보니 20여초는 양반이었다. 1분을 넘어가는 사람들도 수두룩하다. 자신들의 코드가 시간을 많이 소모한다는 글이 많았다. 그 중 아무런 글도 없이 그냥 파이썬 코드만 달랑 올라온 것을 찾았다. 그 코드를 복사/붙여넣기 해서 실행해보니 약 2초만에 정답 출력! 

&#91;python&#93;

#Developed by jdowning on Project Euler
def solve():
    longestLength = 0
    longestStartingNumber = -1
    dictionary = {1 : 1}
    
    for i in range(1, 1000000):
        numberLength = getSequenceLengthForNumber(dictionary, i)
        
        if(numberLength > longestLength):
            longestLength = numberLength
            longestStartingNumber = i
            
    print(longestStartingNumber)
        
def getSequenceLengthForNumber(lengthDictionary, number):
    nextNumber = nextTerm(number)
    length = 0
    
    if(nextNumber in lengthDictionary):
        length = lengthDictionary[nextNumber]
    else:
        length = getSequenceLengthForNumber(lengthDictionary, nextNumber)
        
    length = length + 1
    lengthDictionary[number] = length
    return length
    
def nextTerm(number):
    if(number%2 == 0):
        ret = number/2
    else:
        ret = number*3 + 1
    return ret

solve() 함수를 실행하면 정답을 출력해준다. 딱 이 코드가 내가 대충 구상했던 방식이다. 규칙대로 다음 숫자를 검사하고, 해당 숫자가 이전에 검사한 적이 있는 숫자면 이에 해당되는 체인 수를 바로 알고 있으므로 넘어가고, 처음 보는 숫자라면 해당 숫자의 체인을 계산 후 사전에 체인 수를 저장하는 방식이다. 이렇게 되면 엄청난 연산을 줄일 수 있게 되니 속도가 빠를 수 밖에. 내가 막연히 생각했던 것보다 훨씬 깔끔하게 잘 짜여진 것 같다.

파이썬 관련해서 여기저기 자료를 찾다가 어느 블로그에서 이런 글을 봤다. Don't make your code simple, make your code understandable. 코드가 짧을 수록 좋은 것은 아닌 것은 잘 알지만, 그래도 코드 라인을 좀 더 줄이기 위해서 고급 기능, 고급 모듈들을 사용하는 법을 익히는데 정신이 팔려서는, 내 코드를 더 이해가능하게 만드는데 소홀히 하지 않았나 하는 반성을 하게 된다.

어떤 코드는 읽어도 무슨 말인지 모르겠고, 짜증나서 읽고 이해하기도 싫은 코드가 있는 반면에 이런 코드는 한 눈에 이해할 수 있도록 잘 짜여진 것 같다. 다른 사람들도 내 코드를 보면서 쉽게 이해할 수 있는 깔끔한 코드라는 생각을 하고 있을까?