Python: самое короткое решение 41 задачи из проекта Эйлера

Привет! Сегодня мы решим 41-ю задачу из Проекта Эйлера. Сделаем это сначала в развёрнутом виде, а потом максимально сократим решение.

Условие

Будем считать n-значное число пан-цифровым, если каждая из цифр от 1 до n используется в нем ровно один раз. К примеру, 2143 является 4-значным пан-цифровым числом, а также простым числом. Какое существует наибольшее n-значное пан-цифровое простое число?

Решение

Для начала импортируем модуль math. Из него нам понадобится функция ceil(), округляющая число вверх.

import math

Как не трудно догадаться по условию, нам понадобится функция, определяющая, является ли число простым. Напишем её.

def is_prime(x: int):
	  if x % 2 == 0:
        return x == 2
    for i in range(3, math.ceil(x ** 0.5), 2):
        if x % i == 0:
            return False
    return True 

2 является единственным чётным простым числом, поэтому, если число оказалось чётным, нужно проверить, не 2 ли это. Если 2 – вернуть True, иначе – False. Т. к. return производит выход из функции, после него мы уверены, что число не является чётным. Будем проверять делители x начиная с 3 до округлённого верх квадратного корня из x с шагом 2 (только нечётные). Если x поделится нацело на один из вариантов – немедленно возвращаем False, т. к. число не будет являться простым. Если никакая проверка не привела к выходу из цикла, то число является простым.

Теперь перейдём непосредственно к нашей проблеме. Определим верхнюю границу искомого числа: максимальное пан-цифровое число – это 987_654_321 (да-да, в Python в качестве разделителя в числах можно использовать символ подчёркивания). Поскольку нам нужно найти максимальное пан-цифровое простое число, следует двигаться от максимального значения вниз и выдать первое подходящее. Можно написать функцию для определения, является ли число пан-цифровым, и проверять на простоту только такие числа, но это крайне неэффективно. Среди девятизначных пан-цифровыми будут являться только 9! = 362_880, т. е. каждое 2_756-е. Как мы видим, пан-цифровые числа попадаются крайне нечасто, поэтому стоит придумать алгоритм, который будет генерировать только пан-цифровые числа.

Для генерации всех перестановок (англ. permutations) в стандартной библиотеке itertools есть специальный генератор - permutations(). На вход он принимает любой итерируемый объект (строку/список/...), а возвращает все перестановки (каждая в виде списка) данного нами объекта.

Т. к. нам нужно получить перестановки от большей к меньшей, следует указать из на входе генератора в обратном порядке. Например для девятизначного числа это будет [9, 8, 7, 6, 5, 4, 3, 2, 1]. Обобщим: для i-значного числа нам нужно составить список от i до 1:

list(range(i, 0, -1))

Нам требуется рассмотреть не только 9-значные числа, но и 8/7/6/5/4/3/2/1-значные. Оформим это. Также подадим в качестве аргумента для генератора преобразованный список, где тип каждого элемента изменим на str. Т. к. j – значение конкретной перестановки, – будет являться списком из отдельных строк, каждая из которых будет эквивалентна определённой цифре, преобразуем это значение в число. Далее остаётся проверить его на простоту, вывести, если оно таковым является, и выйти из 2 циклов. Оформим это в функцию:

def main():
    for i in list(range(9, 0, -1)):
        for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
            x = int(''.join(j))
            if is_prime(x):
                print(x)
                return

А сейчас ещё немного подумаем. Ведь в 9-значном пан-цифровом числе сумма цифр s=1+2+3+4+5+6+7+8+9=45, а 45 делится на 3. А, как мы помним, если сумма цифр числа делится на 3, то и само число делится на 3, соответственно, оно не является простым. Из этого следует, что ни одно из 9-значных пан-цифровых чисел не является простым. Аналогичные манипуляции для 2/3/5/6/8-значных пан-цифровых чисел приведут нас к выводу, что среди них также нет простых, т. к. суммы их цифр соответственно равны 3, 6, 15, 21, 36. Единственное же 1-значное пан-цифровое число – 1, – не является не простым, не сложным; но нам достаточно только 1-й части формулировки.

Итого, нам остаётся искать простые пан-цифровые числа только среди 7-значных и 4-значных, так что изменим первый цикл for:

for i in (7, 4):

На этом этапе вся программа выглядит следующим образом:

import math
import itertools

def is_prime(x: int):
    if x % 2 == 0:
        return x == 2
    for i in range(3, math.ceil(x ** 0.5), 2):
        if x % i == 0:
            return False
    return True    

def main():
    for i in (7, 4):
        for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
            x = int(''.join(j))
            if is_prime(x):
                print(x)
                return

if __name__ == '__main__':
    main()

Сокращение решения

А теперь примемся за сокращение нашей программы

Для начала избавимся от функции is_prime() и от библиотеки math, которая использовалась только в этой функции. В модуле sympy, который, к сожалению, не является стандартным, но который можно установить через pip install в командной строке, аналогичная нашей функция isprime(). Удалим и заменим соответствующие участки кода:

import itertools
import sympy 

def main():
    for i in (7, 4):
        for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
            x = int(''.join(j))
            if sympy.isprime(x):
                print(x)
                return

if __name__ == '__main__':
    main()

Уберём проверку на запуск в качестве основного приложения, удалим ненужные скобки в for, уберём создание списка из map'а, так как map возвращает итерируемый тип, который можно подать на вход itertools.permutations:

import itertools
import sympy

def main():
    for i in 7, 4:
        for j in itertools.permutations(map(str, list(range(i, 0, -1)))):
            x = int(''.join(j))
            if sympy.isprime(x):
                print(x)
                return

main()

А теперь попрошу любителей и страстных поклонников pep-8 отвернуться от экрана. Грядёт импорт нескольких библиотек в одну строку, использование других имён модулей и удаление пробелов после запятых.

import itertools as t,sympy
def m():
    for i in 7,4:
        for j in t.permutations(map(str,list(range(i,0,-1)))):
            x = int(''.join(j))
            if sympy.isprime(x):
                print(x)
                return
m()

Заметим, что обращаться к sympy под другим именем не выгодно, т. к. двойное написание "sympy" (при импорте и при обращении) займёт 10 символов, а переименование (например, "sympy as s") и обращение ("s") – уже 11.

Уже вышло вполне компактно, не так ли?

А сейчас время спорных решений – нужно избавиться от функции. Но как, ведь нам нужно выйти сразу из 2 циклов, и обычный break использовать не выйдет? После вывода ответа просто выйдем из программы. Несмотря на то, что глазом вы ответ увидеть вряд ли успеем, формально он будет выведен. Если не выходить, то программа выдаст 2 ответа, а верным является только первый. Можно было бы сделать какую-нибудь запрещённую операцию, в духе деления на ноль, но тогда в консоль будет выведено сообщение об ошибке, т. е. что-то помимо ответа.

Для выхода из программы можно использовать exit() или quit(), но они одинаковы по своей длине, так что разницы нет никакой. Я выберу exit()

Итак, программа выглядит следующим образом:

import itertools as t,sympy
for i in 7,4:
    for j in t.permutations(map(str,list(range(i,0,-1)))):
        x=int(''.join(j))
        if sympy.isprime(x):
            print(x)
            exit()

Остался последний штрих: убрать единственный лишний переход на следующую строку и знак табуляции:

import itertools as t,sympy
for i in 7,4:
    for j in t.permutations(map(str,list(range(i,0,-1)))):
        x=int(''.join(j))
        if sympy.isprime(x):
            print(x);exit()

Ура, товарищи! Программа занимает всего 159 символов. Если есть идеи, как можно уменьшить код ещё меньше, пишите в комментариях.