Это вторая глава второй части статьи про 51 задачу из проекта Эйлера. Если вы пришли сюда, чтобы просто понять принцип задачи, а сам код хотите писать сами, то вам нужна первая часть данной статьи. Если же вы хотите увидеть решение, где я привожу и объясняю готовый код (скачать файл с готовым кодом) на python с четким ответом на задачу, а также поясняю некоторые нюансы, то оставайтесь здесь, но предварительно прочитав первую главу второй части данной статьи. Итак, продолжаем.
Код
Мы пришли к выводу, что искать нам нужно искать числа с тремя повторяющимися цифрами.
Основной код начинается с того, что мы перебираем простые числа из генератора. Мы выводим это число (для удобства наблюдения за поведением кода) и создаем его представление в виде строки и множества.
Множества в python не содержат повторяющихся элементов, следовательно, если в числе есть повторяющиеся цифры, то количество элементов во множестве будет меньше, чем в строке. То есть, есть число, к примеру, 56663. Его строковое представление - это '56663', а множество из этой строки будет выглядеть так - {'5', '6', '3'} (как оно будет отсортировано мы не знаем, да нам это и не нужно). Таким образом, если в числе есть три повторяющиеся цифры, то разность между количеством элементов строки и множества будет составлять два. Этот факт мы и проверяем в первой строке кода (59 строка в файле).
Далее мы создаем список из строки (ведь строка не поддерживает метод remove) и, перебирая элементы из множества, удаляем их из списка (из списка ['5', '6', '6', '6', '3'] постепенно удалить элементы множества {'5', '6', '3'}). Таким образом, в списке у нас останется только две повторяющиеся цифры. В программе на этот список ссылается переменная num_list.
Однако на практике не все так гладко. Возьмем, к примеру такое простое число: 55733. Разность между количеством элементов строки и множества будет составлять два ('55733' - 5 элементов, {'5', '7', '3'} - 3 элемента), однако в этом числе нет трех повторяющихся цифр, в нем встречаются две разных пары повторяющихся цифр. Как же отсеять такие числа? Очень просто. У нужных нам чисел список num_list содержит два одинаковых элемента. А у чисел, которые нам нужно выкинуть - два разных. Вот и добавляется дополнительная проверка в пятой строке кода (65 строка в файле).
Далее мы должны сформировать ключ для словаря. Для этого в список list_a мы записываем позиции повторяющихся цифр в числе, а в список list_num число без повторяющихся цифр. Затем преобразуем эти списки в строки и формируем из двух строк одну (переменная info) - это и будет являться ключом для словаря. Так, для числа 56003 ключом будет являться строка '23563'. Затем формируем сам словарь summary. В самом начале программы мы присваиваем этой переменной значение {}, то есть создаем пустой словарь. Сформировав для числа ключ, мы пытаемся обратиться к значению словаря по этому ключу в надежде на то, что какое-либо число уже формировало этот ключ и, следовательно, создало значение по этому ключу в словаре. Если наши надежды оправдались, то мы просто добавляем текущее число в список, который является значением по сформированному ключу в словаре. Если же на этот раз вселенная окажется к нам неблагосклонна, то интерпретатор Python выбросит исключение KeyError (действительно, мы же обращаемся по несуществующему ключу), которое нам необходимо поймать, и создать-таки значение для сформированного ключа в словаре. Значением будет являться список из одного элемента - текущего числа. И теперь самое важное - как только количество элементов в списке, который является значением в словаре по сформированному для текущего числа ключу (по переменной info) станет больше или равно переменной quantity (значение которой необходимо присвоить в самом начале программы, для нашей задачи необходимо найти восемь простых чисел, следовательно quantity = 8), программа должна вывести на экран этот список и завершить свое выполнение. Минимальное число из этого списка и будет являться ответом на задачу...
... скажем мы и будем не правы. Например, число 5074009 - простое, имеет три повторяющиеся цифры, значит оно сохранится в списке, к которому можно будет получить доступ по ключу '1455749'. Также в этот же список должны сохранится все простые числа вида 5*74**9, где вместо * - какие-то одинаковые цифры. Следуя этой логике в списке должно оказаться также число 5474449, ведь оно простое, и имеет повторяющиеся цифры на тех же позициях. Но это число вообще не будет рассматриваться нашей программой. Почему? Взгляните на первую строку кода (59 строка в файле). Разность между строчным представлением числа и множеством должна составлять 2. А для числа 5474449 она будет составлять 3, ведь технически в этом числе четыре повторяющиеся цифры. Что же делать? Как представить это число так, чтобы программа думала, что в нем три повторяющиеся цифры?
К сожалению никак. Нам придется рассматривать такие случаи отдельно, о чем я расскажу в третьей главе второй части данной статьи. Мы на финишной прямой!