Longest Collatz sequence

collatze_sequence.py

"""
Requires Python3
Solves this: https://projecteuler.net/problem=14
Illustrates the following concepts:
    * Object oriented programming, in particular subclassing int and list
    * Generator pattern (Sequence is a generator)
    # Properties

To save space, does not store full sequence in results, everything is calculated on demand 
Uses up to about 400 MB 

TODO:
Could be vastly improved by not having to derive each number. Consider that once we found the sequence
for say 25, we can save that and short-circuit the sequence calculation
"""

class Number(int):
    """
    Add a few properties to a regular integer
    """

    @property
    def is_even(self):
        """ 
        Returns True if I am an even number
        Returns False if I am an odd number
        This is a "property"; i.e. it looks like an attribute but is actually a function
        """
        return self % 2 == 0

    @property
    def is_odd(self):
        """ 
        Returns True if I am an odd number 
        Returns False if I am an odd number
        This is a "property"; i.e. it looks like an attribute but is actually a function
        """
        return not self.is_even

    @property
    def raw(self):
        """ Convert myself to a regular integer """
        return int(self)

    @property
    def as_string(self):
        """ Convert myself into a string """
        return str(self.raw)

class Sequence(list):
    """
    A sequence defined by an alogrithm, uses generator pattern
    """
    def __init__(self, starting_int):
        """
        Save the raw starting point, call init which will convert to Number object
        """
        self.starting_int = starting_int
        self.init(starting_int)

    def init(self, starting_number):
        self.starting_number = Number(starting_number)
        self._number = Number(starting_number)

    def __iter__(self):
        """
        Part 1 of generator pattern, I have to return the iterator
        Short-circuit if we are already 1 or less
        """
        if self.starting_number.raw <= 1:
            # Return the iterator of an empty list, which will raise StopIteration for me
            return iter([])
        return self

    @property
    def length(self):
        return len(self.sequence)

    def __next__(self):
        """
        Called as we step through our sequence calculations
        self._number is the step we are at in our sequence
        """
        ret = None

        # Calculate based on the number property even/odd
        if self._number.is_even:
            ret = Number(self._number / 2)
        else:
            ret = Number((3 * self._number) + 1)

        # Check to see if I need to stop now
        if ret <= 1:
            # I do, so make sure we are stopping at 1
            # And also reset myself so that I can re-do the calculation
            assert ret == 1
            self.init(self.starting_int)
            raise StopIteration
        self._number = ret
        return ret.raw

    @property
    def sequence(self):
        """
        Initiates the sequence calculation
        We return our starting number, the sequence in the middle, and then 1
        because that is defined as being in the sequence but the sequence calc itself excludes them
        """
        return [self.starting_number.raw] + list(self) + [1]

    def __repr__(self):
        return 'Number "{}" results in chain of length {}\n{}\n'.format(
            self.starting_number.as_string, 
            len(self.sequence), 
            ", ".join([str(n) for n in self.sequence])
            )

class App:
    """
    Our application logic
    """

    def __init__(self, maximum=1000000):
        """
        Alright, let's go
        """
        self.maximum = maximum
        # Do tests to ensure we are working properly
        self.tests()

        from collections import defaultdict
        # defaultdict is a useful form of dictionary
        # part of Python's standard library
        # in this case it makes a dictionary of lists
        # and I don't need to initiate each list for each key, it does it for me
        self.results = defaultdict(list)

        self.main()

    def main(self):
        """
        Step through numbers, initiate sequences, save our work as we go
        """
        for n in range(self.maximum):
            seq = Sequence(n)
            self.results[seq.length].append(seq)

        # Find the longest chain by getting the max key
        longest_chain = max(self.results.keys())

        # Now print out each result found at that key (probably only one though)
        print("Results:")
        for r in self.results[longest_chain]:
            print(r)

    def tests(self):
        """
        Uses assertion statements that ensure we have the right logic working for us
        If assertion fails then error is reported, and program stops
        """
        n = Number(12)
        assert n.is_even == True
        assert n.is_odd == False

        n = Number(13)
        assert n.is_even == False
        assert n.is_odd == True

        seq = Sequence(13)
        assert seq.sequence == [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
        assert seq.length == 10

if __name__ == "__main__":

    app = App()