Маски

Что означает маска 12*3? и каким числам она соответствует?

Маска — образец записи числа: цифры стоят на своих местах, ? — ровно одна любая цифра, * — любая последовательность цифр, даже пустая. Маска говорит только о записи числа, а делимость проверяют отдельно.

Маске 12?4 соответствуют десять чисел: 1204, 1214, …, 1294. Маске 12*4 — бесконечно много: 124, 1204, 12004, 1234564. Пустая звёздочка и звёздочка «0» — разные числа: 124 и 1204. Разложим по частям маски 12*3? несколько чисел:

Каждый ? заполняется независимо: в маске 1?? цифры не обязаны совпадать. Попробуй сам — поменяй маску или число:

Как проверить в программе, подходит ли число под маску?

Функцией fnmatch(str(n), mask) из модуля fnmatch: маска пишется в ней так же, как в условии. Первый аргумент — запись числа, второй — маска; ответ True или False.

from fnmatch import fnmatch mask = '12*3?'print(fnmatch('1234', mask), fnmatch('120034', mask))print(fnmatch('12304', mask), fnmatch('123', mask))

fnmatch сравнивает запись целиком: 912345 под маску 12*3? не подходит, хотя 1234 в ней есть. Границу и делимость она не проверяет — их пишут отдельно. А сравнение строк медленнее остатка, поэтому сначала проверяй делимость, потом маску.

Среди чисел, не превышающих 10¹⁰, найди все, что соответствуют маске 3?12?14*5 и делятся на 1917. Десять миллиардов проверок — это часы. Как сократить перебор?

Перебирать только кратные 1917: начать с 0 и шагать по 1917. Чисел станет в 1917 раз меньше, а делимость проверять уже не нужно. Третий аргумент range — шаг:

from fnmatch import fnmatch for n in range(0, 10**10 + 1, 1917):    if fnmatch(str(n), '3?12?14*5'):        print(n, n // 1917)

Пять миллионов кандидатов — пара секунд. Числа идут по возрастанию, так что вывод уже в нужном порядке. 0 тоже кратен 1917, но под маску не подходит, и начинать с него безопасно.

Если нужен остаток — «при делении на 123 даёт остаток 42», — начинают с самого остатка: range(42, limit, 123) перебирает 42, 165, 288, … — ровно числа вида 123 · k + 42.

Числа до 10¹² по маске 4?8?15?16?23, дающие при делении на 123 остаток 42. Даже с шагом 123 это 8 миллиардов кандидатов. Что делать?

Не искать числа, а построить их по маске: на месте каждого ? — цифра от 0 до 9. Четыре знака ? — это 10⁴ = 10 000 чисел, и все они заведомо подходят под маску. Все наборы из четырёх цифр перебирает product из модуля itertools, а число собирает f-строка:

from itertools import product found = []for a, b, c, d in product('0123456789', repeat=4):    n = int(f'4{a}8{b}15{c}16{d}23')    if n % 123 == 42:        found.append(n) print(len(found), max(found))

product('0123456789', repeat=4) выдаёт наборы ('0', '0', '0', '0'), ('0', '0', '0', '1'), … до ('9', '9', '9', '9'). Подходят 85 чисел, наибольшее — 498915816123. Граница 10¹² здесь ни при чём: все числа маски двенадцатизначные и меньше её.

Если ? стоит первым, ноль на его место ставить нельзя: число не начинается с 0. Для первого знака бери цифры '123456789'.

А если в маске есть *? Длина вставки заранее не известна. Как построить числа по маске 123*678, не превышающие 10⁸, и найти среди них кратные 13?

Оценить, сколько цифр может занять звёздочка, и перебрать вставки каждой длины, начиная с пустой. В маске шесть обязательных цифр, а числа до 10⁸ — не длиннее восьми цифр. Значит, вставка — от 0 до 2 цифр:

from itertools import product for k in range(3):    for x in product('0123456789', repeat=k):        n = int('123' + ''.join(x) + '678')        if n % 13 == 0:            print(n, n // 13)

''.join(x) склеивает набор цифр в строку. При k = 0 product выдаёт один пустой набор — так проверяется и 123678 без вставки. Нули внутри вставки не теряются: набор ('0', '0') даёт 12300678. Всего кандидатов 1 + 10 + 100 = 111 вместо семи миллионов кратных 13.

С двумя звёздочками перебирают обе длины так, чтобы вместе они не превышали свободное место. Одно и то же число тогда можно собрать по-разному: 1223 по маске 1*2*3 получится, если первая звёздочка пустая, а вторая — «2», и наоборот. Поэтому ответы складывают в множество, оно хранит каждое число один раз, а в конце выводят sorted(found).

Что выбрать — шаг или построение? Сравни количество кандидатов. Для 3?12?14*5 и делителя 1917 кратных пять миллионов, а построение дало бы 100 · (1 + 10 + 100) = 11 100 чисел — тоже годится. Когда делитель маленький, а маска короткая, построение выигрывает в тысячи раз.

В тренировочных работах знаки маски иногда определены иначе: «? означает одну чётную цифру». Или маску нужно «найти в записи числа». Как быть?

Определение знаков всегда читают в условии и переводят в язык fnmatch: набор цифр в квадратных скобках — одна цифра из набора, звёздочки по краям — «где-то в записи».

from fnmatch import fnmatch # ? — одна чётная цифра: [02468]mask = '7[02468]23[02468]64*8'for n in range(0, 10**10 + 1, 2026):    if fnmatch(str(n), mask):        print(n)

[02468] — одна чётная цифра, [13579] — одна нечётная. Если строишь числа по маске, на месте такого ? перебирай '02468' вместо всех цифр.

«В записи числа можно найти маску 12*45» значит, что перед маской и после неё могут стоять любые цифры. Это та же проверка со звёздочками по краям: fnmatch(str(n), '*12*45*').

Маска встречается и вместе с делителями: «соответствует маске и имеет ровно 8 делителей». Порядок проверок тот же — сначала дешёвые: кратность через шаг, потом маска, и только у прошедших ищи делители.

• ? и *одна любая цифра; любые цифры, даже ни одной
• Проверкаfnmatch(str(n), mask)
• Шаг k, остаток rrange(r, limit + 1, k), для кратных r = 0
• Только ?построить: product(digits, repeat=q), первая цифра не 0
• Звёздочкадлины вставки от 0 до оценки; две * — во множество
• Чётная цифра[02468]