[[AlgorithmQuiz/3Plus1]]을 [[Iterator]] 및 [[Generator]]를 이용해서... --[[whitekid]]

{{{#!python
import sys
from types import *

class ThreePlusOneIterator(object):
    def __init__(self, num):
        object.__init__(self)

        assert type(num) == IntType
        assert 0 <= num and num<=1000000

        self._initial =  self._current = num
        self._cycleLength = None

    def __iter__(self): return self.next()

    def next(self):
        while self._current <> 1:
            if self._current % 2 == 0: self._current /= 2
            else: self._current = self._current * 3 + 1

            yield self._current


    def _getCycleLength(self):
        if not self._cycleLength:
            self._cycleLength = len(list(iter(ThreePlusOneIterator(self._initial)))) + 1
        return self._cycleLength

    cycleLength = property(_getCycleLength)



class App:
    def run(self):
        for line in sys.stdin:
            (i, j) = line.strip().split()
            print i, j, self.getMaxCycle( int(i), int(j))


    def getMaxCycle(self, i, j):
        """ 주어진 수의 사이의 Max Cycle 구하기 """
        maxCycle = 0
        for x in range(min(i,j), max(i,j)+1):
            maxCycle = max(maxCycle, ThreePlusOneIterator(x).cycleLength )
        return maxCycle


if __name__ == '__main__':
    App.run()
}}}

아래는 테스트케이스
{{{#!python
import unittest

from ThreePlusOne import *

class ThreePlusOneTestCase(unittest.TestCase):
    def testOneStep(self):
        assert 11 == iter(ThreePlusOneIterator(22)).next()
        assert 34 == iter(ThreePlusOneIterator(11)).next()

    def test(self):
        seq = map( lambda x: int(x), '11 34 17 52 26 13 40 20 10 5 16 8 4 2 1'.split())
        assert seq == list(iter(ThreePlusOneIterator(22)))

    def testCycleLength(self):
        assert ThreePlusOneIterator(22).cycleLength == 16
        assert ThreePlusOneIterator(1).cycleLength == 1


class ThreePlusOneAppTestCase(unittest.TestCase):
    def testGetMaxCycles(self):
        assert App().getMaxCycle(3, 5) == 8

    def testRun(self):
        app = App()


if __name__ == '__main__':
    unittest.main()
}}}

Generator를 사용하면
{{{#!python
def getCycle(seed):
    while True:
        yield seed
        if seed == 1: break
        seed = seed % 2 and seed * 3+1 or seed / 2

def getCycleCountByRange(start, end):
    for i in range(start, end+1):
        yield len([x for x in getCycle(i)])

def run(data):
    for line in data.split('\n'):
        start, end = map(int, line.split())
        print start, end, \
            max([count for count in getCycleCountByRange(start, end)])


if __name__ == '__main__':
    run('''1 22
2 999
3 777
3 98''')
}}}