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()

~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() 

~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)