Решаем криптарифмы с помощью алгебры и python

Если вы увлекались математикой в возрасте до 12 лет, то, наверное, встречались с криптарифмами - числовыми ребусами.

Числовым ребусом называется корректное арифметическое выражение (обычно - равенство), часть цифр в котором заменена на буквы и звездочки. Правила просты: одинаковые буквы заменяются на одинаковые цифры, разные - на разные.

Задача - восстановить исходные цифры, получив верное равенство.

Числовые ребусы хороши для тренировки у младшеклассников навыков логического мышления и счета в столбик. Однако и взрослым программистам может быть интересно поискать ответ на общий вопрос - а как, всё таки, алгоритмизировать процесс решения ребуса?

Формулировка задачи

На вход программы подается арифметический ребус. Он представляет из себя строку и состоит из букв, цифр, знаков арифметических действий , знака и круглых скобок.

Если ребус корректно преобразуется в арифметическое сравнение, программа должна вернуть список его решений. Например, на КОЗА*2 = СТАДО программа вернет что-то вроде [8653*2 = 17306, 7693*2 = 15386], что решит нашу задачу.

Часть первая. Наивный алгоритм.

Искусство программирования учит нас: что бы решить задачу, представьте, что она уже решена. В данном случае, определим функцию, решающую ребусы:

def solve(rebus: str) -> list[str]:
    # Решаем ребус
    return solutions

def test_rebus_solver():
    solutions = solve("КОЗА+КОЗА = СТАДО")
    solutions.sort()        
    assert solutions == ["7693+7693 = 15386", "8653+8653 = 17306"]

Предобработка ребуса

Прежде всего, стоит упростить задачу, преобразовав текущее выражение. А именно:

1. Уберем знак . Для этого обернем выражение справа и слева в скобки и вычтем одно из другого.

   КОЗА*2 = СТАДО => (КОЗА*2)-(СТАДО)

2. Составим множество уникальных букв в выражении. Для упрощения восприятия, я буду записывать в своем псевдокоде список в виде последовательности строк, разделенных запятыми:

   [К,О,З,A,С,Т,Д]

3. Разобьем выражение на токены. Токен - строка, представляющая либо арифметическое действие, либо скобку, либо строку из букв и цифр.

   (КОЗА*2)-(СТАДО) => [(,КОЗА,*,2,),-,(,СТАДО,)]

4. Уберем из списка токенов скобки. Для этого преобразуем выражение внутри него в обратную польскую запись (Reverse Polish Notation, PPN)

   [(,КОЗА,*,2,),-,(,СТАДО,)] => [КОЗА,2,*,СТАДО,-]

   Для переписывания выражения в RPN используем, например, алгоритм Shunting Yard.

Операции 1-4 можно назвать предобработкой исходного ребуса. Объединим их в функцию:

def rebus_preprocessing(rebus: str) -> list[str], set[str]:
    # 1) Убираем знак =
    # 2) Составляем список букв под замену 
    # 3) Токенезируем выражение
    # 4) Переводим выражение в RPN

    return rpn_rebus, letters

def test_rebus_preprocessing():
    rpn_rebus, letters = rebus_preprocessing("КОЗА*2 = СТАДО")
    assert rpn_rebus == ["КОЗА","2",'*',"СТАДО",'-']
    assert letters == {'К','О','З','A','С','Т','Д'}

Поиск решений

Первая - простая - идея состоит в том, что бы перебрать все возможные замены букв на цифры и проверить полученное после каждой замены арифметическое выражение на равенство нулю.

Напишем функцию под это:

def naive_rebus_solver(rpn_rebus: list[str], letters: set[str]) -> list[dict[str,str]]
    # Перебираем все возможные подстановки. Возвращаем список корректных подстановок
    return substitutions 

def test_naive_rebus_solver():
    rpn_rebus, letters = rebus_preprocessing("КОЗА*2 = СТАДО")
    substitutions = naive_rebus_solver(rpn_rebus, letters)
    substitutions_pairs = sorted([
        tuple(sorted([tuple(item) for item in s.items()]))
        for s in substitutions
    ])
    assert substitutions_pairs == [
      (('А', '3'), ('Д', '0'), ('З', '5'), ('К', '8'), ('О', '6'), ('С', '1'), ('Т', '7')), 
      (('А', '3'), ('Д', '8'), ('З', '9'), ('К', '7'), ('О', '6'), ('С', '1'), ('Т', '5'))
  ]

Как же мы будем делать перебор?

Арифметические выражения, записанные с помощью RPN, замечательно удобно вычислять. Например, представим себе, что мы хотим вычислить 8653*2 - 17306 . В обратной польской записи это выражение перепишется как:

Затем наш вычислитель идет по списку токенов, и по очереди кладет их в стек, пока не обнаружит операцию. Обнаружив её, он извлекает из стека два последний числа, применяет к ним операцию и снова кладет в стек. Если изначальное арифметическое выражение корректно, когда мы дойдем до конца списка, в стеке будет лежать единственное число - результат вычислений.

Остается перебрать все подстановки. На этот случай python есть удобнейший itertools.permutations:

from itertools import permutations

def naive_rebus_solver(rpn_rebus, letters):

    substitutions = []
    substitution = {l:'' for l in letters}

    for permutation in permutations('0123456789', len(letters)):
        for i, s in enumerate(letters):
            substitution[s] = permutation[i]
        # ... 

Нужно отметить, что pythonic way здесь в том, что бы использовать таблицы подстановки. substitution_table = str.maketrans(substitution). Это немного ускоряет процесс подстановки букв в токены. Однако ускорение не столь существенно, и ради ясности подхода, было решено пренебречь этой возможностью языка.

Подставляем, вычисляем, сравниваем с нулем каждую подстановку. Готово!

Часть вторая. Не такой наивный алгоритм.

Поигравшись с наивным алгоритмом, представленным выше, обнаруживаем в нем один недостаток. Он медленный.

Легко видеть, что в худшем случае нам придется перебрать подстановок. Не так уж много - однако, тест ТРАВА+КОРОВА+ДОЯРКА = МОЛОКО, содержащий как раз 10 букв, исполняется на моей машине 18 секунд.

Пути решения проблемы:

• Переписать на более быстрый язык программирования

• Распараллелить

• Попробовать оптимизировать цикл подстановки-и-подсчета

Всё это - хорошие пути решения, но можно поступить проще.

Задумаемся над тем, как эту задачу бы решал ребенок. Врят ли он стал бы механически перебирать миллионы вариантов подстановки. Покумекав слегка, умный математический школьник изобретет примерно следующее:

1. Рассмотрим последнюю букву в каждом из слагаемых.

2. Переберем несколько вариантов этой буквы, затем добавим в рассмотрение предпоследнюю.

3. Будем делать так, пока не решим весь ребус.

Когда матшкольнику случится подрасти и поступить в универ, он может встретить концепцию кольца - множества элементов, замкнутого относительно сложения, вычитания и умножения. Самые простые для понимания кольца - кольца остатков от деления. Действительно, для любого a,b,p верно:

(a%p + b%p)%p == (a+b)%p

(a%p - b%p)%p == (a-b)%p

(a%p * b%p)%p == (a*b)%p

К сожалению, вообще говоря, это неверно для деления. Система чисел, замкнутая относительно операции деления, помимо первых трех, зовется у математиков полем - и если мы рассматривали простое p, то могли бы утверждать, что у множества остатков от деления на p есть свойства поля. В данном случае, однако, мы будем последовательно рассматривать в роли p числа 10, 100, 1000... то есть, по сути, брать несколько последних цифр от каждого значения в нашем выражении.

Мы получаем цепочку ребусов такого вида:

А+А = О (mod 10)

ЗА+ЗА = ДО (mod 100)

ОЗА+ОЗА = АДО (mod 1000)

КОЗА+КОЗА = ТАДО (mod 10000)

КОЗА+КОЗА = СТАДО (mod 100000)

Мы должны последовательно решить каждый из них с учетом решений предыдущих. А именно, первый ребус дает варианты:

2+2 = 4, 3+3 = 6, 4+4 = 8, 5+5 = 0, 6+6 = 2, 7+7 = 4, 8+8 = 6, 9+9 = 8

Для каждого из этих вариантов мы пытаемся решить второй ребус, подставив в него предварительно буквы А и О в соответствии с вариантом. Допустим, {А:2, О:4}. В таком случае, второй ребус имеет следующие варианты решения:

32+32 = 64, 52+52 = 04, 82+82 = 64, 92+92 = 84

Для каждого из эти вариантов мы решаем третий ребус...

В конце концов, мы получим все варианты, каждый из которых решает пятый ребус. Это множество вариантов гарантированно содержит все ответы на наш ребус, и может содержать некоторое количество ложных ответов. К примеру, ребус А+А=В решенный таким образом имел бы в качестве кандидатов на решения сложения двух равных цифр, перечисленные выше, но верными были бы только 2+2 = 4, 3+3 = 6, 4+4 = 8. Нам не составит никакого труда отфильтровать итоговый список вариантов, проверив каждый из них на оригинальном ребусе уже без всяких алгебраических колец.

Посчитаем выигрыш в скорости!

• Тест КОЗА+КОЗА = СТАДО (7 букв) дает на моей машине ровно 3 секунды исполнения наивным алгоритмом, и 0.0037 секунд умным. Более точным будет указать, что метод calc, производящий в моей программе, собственно, вычисление подставленного значения ребуса, при наивном методе вызывается 483840 раза. В умном - 773 раза.

• Тест ТРАВА+КОРОВА+ДОЯРКА = МОЛОКО исполняется наивным методом 18 секунд, вызывая calc 2177280 раза. Умным - 0.038 секунд, а calc вызывается 2502 раза, включая частичные подсчеты.

Заключение

Мораль нашей истории проста. Приложив немного алгебры, можно значительно упростить себе жизнь.

Попробовать реализацию алгоритма в действии вы можете в онлайн-демо:

Полный код опубликован на github. Помимо всего вышеперечисленного там можно найти две интересные вещи, которые я решил не включать в статью: распараллеливание на python и рабочую реализацию функции на облаке Яндекса, исполняющей роль сервера для демки.

Настоящая статья написана по мотивам кружковых занятий Малого Мехмата МГУ для старших классов. Надеюсь, вам было интересно читать её не меньше, чем нам писать.

Спасибо за внимание!