nekedome / project-euler

solutions/problem14.py

"""
Project Euler Problem 14: Longest Collatz Sequence
==================================================

.. module:: solutions.problem14
   :synopsis: My solution to problem #14.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem14.py>`_.

Problem Statement
#################

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

.. math::

    n &\\rightarrow \\frac{n}{2} \\; \\; \\; & \\mbox{(n is even)} \\\\
    n &\\rightarrow 3n + 1       \\; \\; \\; & \\mbox{(n is odd)}

Using the rule above and starting with :math:`13`, we generate the following sequence:
    :math:`13 \\rightarrow 40 \\rightarrow 20 \\rightarrow 10 \\rightarrow 5 \\rightarrow 16 \\rightarrow 8`
    :math:`\\rightarrow 4 \\rightarrow 2 \\rightarrow 1`

It can be seen that this sequence (starting at :math:`13` and finishing at :math:`1`) contains :math:`10` terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at :math:`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.

Solution Discussion
###################

This solution simply uses an exhaust coupled with memoisation to avoid re-computing the same value over and over.

The search space is iterated, and any partial results (that may form the tail of subsequent sequences) will be cached
along with the associated chain length.

Upon completion, search for the largest chain.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem14.py
   :language: python
   :lines: 50-
"""

from typing import Dict

from lib.numbertheory import is_even


def collatz(n: int, d: Dict[int, int]) -> int:

The name n does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name d does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    """ Compute the Collatz sequence starting at :math:`n`

    The length of a Collatz sequence starting at :math:`n` can be computed by iterating the Collatz map until it reaches
    :math:`1`. While this would be sensible for a single :math:`n`, performing this for many values of :math:`n` will
    result in a lot of redundant calculations.

    Consider the following two overlapping Collatz sequence:

    .. math::

        64 \\rightarrow 32 \\rightarrow 16 \\rightarrow 8 \\rightarrow 4 \\rightarrow 2 \\rightarrow 1 \\\\
        10 \\rightarrow  5 \\rightarrow 16 \\rightarrow 8 \\rightarrow 4 \\rightarrow 2 \\rightarrow 1

    Observe the coalescence of these two sequences when they both reach the value :math:`16`. These two sequences
    provide the lengths of Collatz sequences starting at: :math:`1,2,4,5,8,10,16,32` and :math:`64`.

    By caching all results as we go we can avoid re-computing the tail of any coalescing sequences.

    :param n: the start of the Collatz sequence
    :param d: a dictionary of existing solutions
    :return: the length of the Collatz sequence starting at :math:`n`

    .. note:: the dictionary :math:`d` will be updated with any partial results computed.
    """

    try:
        return d[n]
    except KeyError:
        if is_even(n):
            d[n] = 1 + collatz(n // 2, d)
        else:
            d[n] = 1 + collatz(3 * n + 1, d)
        return d[n]


def solve():
    """ Compute the answer to Project Euler's problem #14 """

    upper_bound = 1000000  # search limit

    # Apply the recursive to find the maximal length chain
    d = {1: 1}

The name d does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for i in range(1, upper_bound, 1):
        collatz(i, d)

    # Identify the largest chain
    v = list(d.values())

The name v does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    k = list(d.keys())
    answer = k[v.index(max(v))]

    return answer


expected_answer = 837799

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).