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`

This line is too long as per the coding-style (108/100).

    :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.

This line is too long as per the coding-style (112/100).

Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at :math:`1`.

This line is too long as per the coding-style (115/100).

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.

This line is too long as per the coding-style (113/100).

The search space is iterated, and any partial results (that may form the tail of subsequent sequences) will be cached

This line is too long as per the coding-style (117/100).

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

This line is too long as per the coding-style (120/100).

    :math:`1`. While this would be sensible for a single :math:`n`, performing this for many values of :math:`n` will

This line is too long as per the coding-style (117/100).

    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 \\\\

This line is too long as per the coding-style (107/100).

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

This line is too long as per the coding-style (102/100).

    Observe the coalescence of these two sequences when they both reach the value :math:`16`. These two sequences

This line is too long as per the coding-style (113/100).

    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_]*)|(__.*__))$).