nekedome / project-euler

solutions/problem24.py

"""
Project Euler Problem 24: Lexicographic Permutations
====================================================

.. module:: solutions.problem24
   :synopsis: My solution to problem #24.

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

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

A permutation is an ordered arrangement of objects. For example, :math:`3124` is one possible permutation of the digits

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

:math:`1, 2, 3` and :math:`4`. If all of the permutations are listed numerically or alphabetically, we call it

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

lexicographic order. The lexicographic permutations of :math:`0, 1` and :math:`2` are:

.. math::

    012 \\mbox{ } 021 \\mbox{ } 102 \\mbox{ } 120 \\mbox{ } 201 \\mbox{ } 210

What is the millionth lexicographic permutation of the digits :math:`0, 1, 2, 3, 4, 5, 6, 7, 8` and :math:`9`?

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

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

I do not see an obvious closed-form solution to this problem, I will find the answer computationally. Python provides

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

powerful permuted iterators that make this task very simply. The ``itertools`` module will be used to simply iterate

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

over the permutations of the digits :math:`0` through :math:`9` until the millionth element is reached. The digits in

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

this element will then be translated into a big-endian integer, this corresponds to the millionth number in the

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

sequence.

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

.. literalinclude:: ../../solutions/problem24.py
   :language: python
   :lines: 41-
"""

from itertools import islice, permutations


def solve():
    """ Compute the answer to Project Euler's problem #24 """
    target = 1000000
    range_limit = 10
    digit_permutations = permutations(range(range_limit))
    digits = next(islice(digit_permutations, target - 1, target))
    answer = sum([digit * 10 ** (range_limit - 1 - i) for i, digit in enumerate(digits)])
    return answer


expected_answer = 2783915460

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