Это третья глава второй части статьи про 51 задачу из проекта Эйлера. Если вы пришли сюда, чтобы просто понять принцип задачи, а сам код хотите писать сами, то вам нужна первая часть данной статьи. Если же вы хотите увидеть решение, где я привожу и объясняю готовый код (скачать файл с готовым кодом) на python с четким ответом на задачу, а также поясняю некоторые нюансы, то оставайтесь здесь, но предварительно прочитав вторую главу второй части данной статьи. Итак, продолжаем.
Код
Мы пришли к выводу, что учитывать нам нужно числа и с четырьмя повторяющимися цифрами.
Под это условие подходит три типа чисел:
- Число с четырьмя одинаковыми цифрами (например, 5474449);
- Число с тремя одинаковыми цифрами и двумя другими одинаковыми цифрами (например, 55333)
- Число с тремя парами разных одинаковых чисел (например, 5837387)
Нас интересует только первый и второй тип чисел, рассматривать мы их будем отдельно друг от друга.
Первый тип чисел отсеять от других не сложно. В таких числах четыре одинаковые цифры, а значит все три элемента списка num_list (списка, который содержит повторяющиеся цифры) должны быть равны между собой.
Что делать дальше? Дальше нам необходимо представить это число как число с тремя одинаковыми цифрами. Всего есть четыре варианта такого представления (число 5474449 - это просто пример):
- 5474449 - где повторяющаяся цифра имеет позиции 1, 3, 4;
- 5474449 - где повторяющаяся цифра имеет позиции 3, 4, 5;
- 5474449 - где повторяющаяся цифра имеет позиции 1, 3, 5;
- 5474449 - где повторяющаяся цифра имеет позиции 1, 4, 5;
Как это сделать? Сначала мы формируем список list_a, содержащий позиции всех четырех одинаковых цифр в числе. Далее, для этого большого числа с четырьмя одинаковыми цифрами, мы формируем четыре числа с тремя одинаковыми цифрами, и рассматриваем каждое поочереди, отдельно друг от друга, следуя алгоритму для чисел с тремя одинаковыми цифрами из предыдущей главы.
Первый тип чисел зацепился на предыдущей проверке, следовательно нам нужно отфильтровать второй от третьего. Все опять же довольно просто. У второго типа чисел в списке повторяющихся цифр num_list есть хотя бы два одинаковых элемента, а у третьего типа все три элемента разные, следовательно выполняем соответствующую проверку.
Далее из списка num_list нам нужно удалить элемент, отличающийся от двух других. И вуаля - мы имеем число с тремя повторяющимися цифрами, а как работать с таким числом - мы знаем.
Первый и второй тип чисел мы отфильтровали, а третий нас не интересует, следовательно, наша программа готова.
Запустив программу, долгожданный результат мы получим примерно через 50 секунд. Это значит, что программа оптимизирована неплохо (хотя, конечно, в нее можно внести достаточно улучшений - это я понял уже когда начал писать статью об этой задаче :) ). Наконец, вот сам результат:
[5074009, 5174119, 5374339, 5474449, 5574559, 5774779, 5874889, 5974999]
По условию задачи нам необходимо найти меньшее из этих чисел. Таким образом,
Ответ: 5074009.
Вот и все, задача решена. К сожалению, проверить правильность своего ответа я не могу, ведь, как я говорил в самой первой части статьи про эту задачу, я нигде не смог найти ни решения (именно на языке Python), ни самого ответа. По этой причине я и решил написать эти статьи, чтобы такие же новички, как и я, имели больше полезной информации в открытом доступе.
Если вам было что-то непонятно, спрашивайте. Если у вас есть предложения по улучшению статей или программы, предлагайте. Комментарии открыты для всех ^_^
А на этом все! Большое спасибо за прочтение!