3N+1 Problem/Leonardong

첫째 ¶

~cpp 
class AOI3nPlus1ProblemRunner:
    def getMaximumCycleLength(self, aFrom, aTo):
        max = 0
        for i in range( aFrom, aTo + 1):
            cycleLength = self.getCycleLength(i)
            if max < cycleLength:
                max = cycleLength
        return max
    def getCycleLength( self, aStart ):
        n = aStart
        cycleLength = 1
        while n is not 1:
            cycleLength = cycleLength + 1
            if n % 2 is not 0:
                n = 3 * n  + 1
            else:
                n = n / 2
        return cycleLength
    def run(self):
        numFrom = input("")
        numTo = input("")
        print self.getMaximumCycleLength(numFrom, numTo)
        
#########################################################################           
import unittest

class AOI3nPlus1ProblemTestCase(unittest.TestCase):
    def setUp(self):
        self.runner = AOI3nPlus1ProblemRunner()
    def testGetMaximumCycleLength(self):
        self.assertEquals( 1, self.runner.getMaximumCycleLength( 1, 1 ) )
        self.assertEquals( 20, self.runner.getMaximumCycleLength( 1, 10 ) )
        self.assertEquals( 125, self.runner.getMaximumCycleLength( 100, 200 ) )
        self.assertEquals( 89, self.runner.getMaximumCycleLength( 201, 210 ) )
        self.assertEquals( 174, self.runner.getMaximumCycleLength( 900, 1000) )
    def testGetCycleLength(self):
        self.assertEquals( 1, self.runner.getCycleLength(1) )
        self.assertEquals( 5, self.runner.getCycleLength(16) )
        self.assertEquals( 16, self.runner.getCycleLength(22) )

#########################################################################
if __name__ == '__main__': 
##    unittest.main()
    AOI3nPlus1ProblemRunner().run()

[edit]

둘째 ¶

~cpp 
import psyco
MAXIMUM = 10000
class AOI3nPlus1ProblemRunner:
    def __init__(self):
        self.cycleLens = {}
    def getMaximumCycleLen(self, aFrom, aTo): 
        maximum = 0
        for i in range( aFrom, aTo + 1):
            if self.getCycleLen(i) > maximum:
                maximum = self.getCycleLen(i)
            self.cycleLens[i] = maximum
        return maximum
    def getCycleLen( self, n ):
        if n not in self.cycleLens:
            self.storeCycleLen( n )
        return self.getStoredCycleLen(n)
    def run(self): 
        numFrom = input("") 
        numTo = input("") 
        print self.getMaximumCycleLen(numFrom, numTo)

    def storeCycleLen(self, aN):
        n = aN
        cycleLen = 1
        while n is not 1: 
            if n in self.cycleLens:
                cycleLen  = cycleLen + self.cycleLens[n] - 1
                break
            cycleLen += 1           
            if n % 2 is not 0: 
                n = 3 * n + 1 
            else:
                n = n / 2
        self.cycleLens[aN] = cycleLen
    def getStoredCycleLen(self, aN):
        if aN not in self.cycleLens:
            return 0
        return self.cycleLens[aN]
         
#########################################################################            
import unittest 
 
class AOI3nPlus1ProblemTestCase(unittest.TestCase): 
    def setUp(self):
        self.runner = AOI3nPlus1ProblemRunner() 
    def testGetMaximumCycleLen(self): 
        self.assertEquals( 1, self.runner.getMaximumCycleLen( 1, 1 ) ) 
        self.assertEquals( 20, self.runner.getMaximumCycleLen( 1, 10 ) ) 
        self.assertEquals( 125, self.runner.getMaximumCycleLen( 100, 200 ) ) 
        self.assertEquals( 89, self.runner.getMaximumCycleLen( 201, 210 ) ) 
        self.assertEquals( 174, self.runner.getMaximumCycleLen( 900, 1000) ) 
    def testGetCycleLen(self): 
        self.assertEquals( 1, self.runner.getCycleLen(1) ) 
        self.assertEquals( 5, self.runner.getCycleLen(16) ) 
        self.assertEquals( 16, self.runner.getCycleLen(22) )
    def testStoreCycles(self):
        self.assertEquals( 0, self.runner.getStoredCycleLen(0) )
        self.runner.storeCycleLen(22)
        self.assertEquals( 16, self.runner.getStoredCycleLen(22) )
    def testTime(self):
         # goal = 999,999 in 4 sec
        self.runner.getMaximumCycleLen(1,MAXIMUM)
##        self.runner.getCycleLen(MAXIMUM)
        self.runner.storeCycleLen(MAXIMUM)
######################################################################### 
if __name__ == '__main__':
    psyco.full()
    unittest.main(argv=('','-v')) 
##    AOI3nPlus1ProblemRunner().run()

[edit]

셋째 ¶

~cpp 
# 45m after tuning
# total = 3h 11m 11s
import unittest
TEST_MAX =  100000
MAX =       1000000
##TEST_MAX =  MAX - 1

storedCycleLens = [0] * MAX
CUTOFF = 100

def preProcessing():
    i = 1
    cycleLen = 1
    while i < MAX:
        storedCycleLens[i] = cycleLen
        cycleLen += 1
        i *= 2

def getCycleLen(aN):
    n = aN
    result = 1
    while n != 1:
        result += 1
        if n % 2 != 0:
            result += 1
            n = (3*n+1) / 2
        else:
            n /= 2
            if n < MAX and\
               storedCycleLens[n] != 0:            
                result += storedCycleLens[n] - 1
                break
##            if getStoredCycleLen(n) is not 0:
##                return getStoredCycleLen(n) + result - 1
    return result
def storeCycleLen(aN):
    storedCycleLens[aN] = getCycleLen(aN)

def getStoredCycleLen(aN):
    if aN < 0 or aN >= MAX:
        return 0
    return storedCycleLens[aN]

def getMaxCycleLen(aStart, aEnd):
    maximum = 0
    interval = 1
    if CUTOFF < aEnd - aStart:
        interval = 2
        if aStart % 2 == 0:
            aStart -= 1
    for n in range(aStart, aEnd+1, interval):
        cycleLen = getCycleLen(n)
        if maximum < cycleLen:
            maximum = cycleLen
        storedCycleLens[n] = cycleLen
    return maximum

class MyTestCase(unittest.TestCase):
    def testGetCycleLen(self):
        tests = [(1,1), (9,20), (16,5), (MAX-1,259)]
        for n, expected in tests:
            self.assertEquals( expected, getCycleLen(n) )
        for n in range(MAX-1000, MAX):
            getCycleLen(n)
    def testgetMaxCycleLen(self):
        tests = [(1,1,1),  (1,16,20), (900,1000,174), (1,1000,179)]
        for start, end, expected in tests:
            self.assertEquals(expected, getMaxCycleLen( start, end ) )
    def testStoreCycleLen(self):
        tests = [(1,1),  (16,5),   (MAX-1,259)]
        for n, expected in tests:
            storeCycleLen( n )
            self.assertEquals( expected , getStoredCycleLen(n) )
    def testTime(self):
        getMaxCycleLen(1, TEST_MAX)
##        self.assertEquals(525, getMaxCycleLen(1, MAX))
if __name__ == '__main__':
    preProcessing()
##    unittest.main()
    timeTest = MyTestCase("testTime")
    runner = unittest.TextTestRunner()
    runner.run(timeTest)

[edit]

Thread ¶

절대 쉽지 않은 문제였다. 아직 수행시간이 턱없이 길다. 사전형 멤버를 이용해 계산했던 부분은 저장해두어 다시 쓰도록 하였다. 답답하다. PsyCo라는 모듈을 새롭게 알알게되었다. --Leonardong

싸이코? --강희경

셋째 코드에서 해본 새로운 시도는 다음과 같다.

MAX(100000)개의 원소를 가진 리스트에 계산했던 CycleLength를 저장한다.
3n+1은 항상 짝수이므로 짝수 검사를 한 번 건너뛴다.
2의 제곱수들은 CycleLength를 예상할 수 있으므로 입력 받기 전에 미리 계산해둔다.
CycleLength를 구하는 과정에서 n이 짝수일 때만 저장된 값이 있는지를 검사한다.
구하는 범위가 Cutoff보다 크면 시작하는 수가 홀수일 때 CycleLength가 클 것이므로 홀수부터 시작해서 짝수는 무시하고 구한다.

파이선만으로 12초가 걸린다. 새로운 걸 한 번씩 시도할 때마다 시간이 줄어들어 신기했다. 중간에 코드를 고치면서 시간 테스트만 돌리다가 답이 잘못 나오는 코드를 가지고 한동안 작업했었다. 새로운 기능을 추가하면 테스트를 전부 돌려야겠다. --Leonardong

확신이 가지 않는 cutoff부분을 빼더라도 PsyCo를 쓰면 2초 안에 통과한다. 3시간 동안 10초 정도를 줄였는데, 10분만에 10초를 줄였다. 시간을 줄여야 하는데 정말 수가 안 떠오르면 PsyCo가 꽤 도움이 될 것이다. 남용은 조심해야겠다.--Leonardong

AOI, 3N+1Problem