Буквометик

@VadimK76 · Регистрация: 22.02.2023

Студворк — интернет-сервис помощи студентам

Доброго времени суток. Не могу оптимизировать решение вот такой задачи:

Буквомётики это головоломки, в которых каждой букве надо сопоставить цифру таким образом, чтобы было выполнено предложенное тождество.
Например буквомётик,
SEND+MORE=MONEY
можно решить, если мы сопоставим буквам цифры следующим образом:
O - 0, M - 1, Y - 2, E - 5, N - 6, D - 7, R - 8, S - 9
В итоге получим корректное тождество 9567+1085=10652.
На вход вашей программе подаётся буквомётик, в котором слева от знака равенства находится сумма двух чисел, а справа - одно число. Вам надо вывести его решение. Обратите внимание, что число не может начинаться с нуля.

Решил ее с помощью itertools.permutations, но каждый время выполнения разное (от 0, 1 сек до 109 сек). Код прилигаю

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from itertools import permutations
 
s = input().replace('+', ' ').replace('=', ' ')
s2 = set(s.replace(' ', ''))
s = s.split(' ')
otv = -1
 
for i in permutations(range(10), len(s2)):
    y = dict(zip((list(s2)), i))
    if int(y[s[0][0]]) == 0 or int(y[s[1][0]]) == 0 or int(y[s[2][0]]) == 0:
        continue
    if int(''.join(map(str, [y.get(key) for key in s[0]])))+int(''.join(map(str, [y.get(key) for key in s[1]]))) == int(''.join(map(str, [y.get(key) for key in s[2]]))):
        otv = ' '.join('{} {}'.format(key, val) for key, val in sorted(y.items()))
        break
 
print(otv)

Пытался его ускорить и сделать через один list comprehension и срезы, но и это не помогло:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import permutations
 
s = input().replace('+', ' ').replace('=', ' ')
s2 = list(set(s.replace(' ', '')))
s3 = list(s)
s = s.split(' ')
otv = -1
 
for i in permutations(range(10), len(s2)):
    if i[0] == 0 or i[s2.index(s[1][0])] == 0 or i[s2.index(s[2][0])] == 0:
        continue
    y = dict(zip(s2, i))
    zy = [str(y[i]) for i in s3 if i.isalpha()]
    if int(''.join(zy[:len(s[0])])) + int(''.join(zy[len(s[0]):len(s[0])+len(s[1])])) == int(''.join(zy[len(s[0])+len(s[1]):])):
        otv = ' '.join('{} {}'.format(key, val) for key, val in sorted(y.items()))
        break
 
print(otv)

Отчаялся и пришел на форум. Заранее спасибо

@Red white socks · 24.02.2023, 14:01

VadimK76, с этим что-нибудь получилось?

Сообщение от Red white socks

Сделаем такую химеру: если количество элементов в множестве букв не превышает 6 - решаем вашим вариантом с полным перебором, а если 7 и более - моим.

@VadimK76 · 25.02.2023, 14:44 **[ТС]**

Red white socks , химета тоже не справилась. Падает на 46ом. Полный перебор довел до 9 букв в множестве, после код стала падать из-за превышения лимита времени. Прикладываю тайминги (идут по порядку увелечения букв в множестве полного перебора).

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from itertools import permutations, chain
 
 
def check_correct(d: dict, first_letters) -> bool:
    if len(set(d.keys())) != len(set(d.values())):
        return False
    for x in first_letters:
        if d.get(x) == 0:
            return False
    return True
 
 
def replace_letters(word: str, d: dict, n: int) -> str:
    return ''.join(map(lambda x: str(d[x]), word[-n:]))
 
 
def check_equal(words: str, d: dict, n=0) -> bool:
    sum_words = sum(map(lambda x: int(replace_letters(x, d, n)), words[:-1]))
    return str(sum_words)[-n:] == replace_letters(words[-1], d, n)
 
def final_check(expr:str, d:dict) -> bool:
    for key, value in d.items():
        expr = expr.replace(key, str(value))
    return eval(expr.replace('=','=='))
 
 
def find_solution(expr: str) -> list:
    words = list(map(lambda x: x.strip(), expr.replace('+','=').split('=')))
    max_len = max(map(len, words))
    first_letters = set(map(lambda x: x[0], words))
    variants = [{}]
    symbols = set()
    for i in range(1, max_len + 1):
        new_symbols = set(map(lambda x: x[-i] if i <= len(x) else x[-1], words)) - symbols
        new_variants = []
        for v in variants:
            for current in permutations(range(10), len(new_symbols)):
                v_new = dict(chain(v.items(), zip(new_symbols, current)))
                if check_correct(v_new, first_letters) and check_equal(words, v_new, i):
                    new_variants.append(v_new)
        symbols |= new_symbols
        variants = new_variants[:]
 
    final_variants = list(filter(lambda x: final_check(expr, x), variants))
    return final_variants
 
def men6(s):
    s = s.replace('+', ' ').replace('=', ' ')
    s2 = set(s.replace(' ', ''))
    s = s.split(' ')
    otv = -1
 
    for i in permutations(range(10), len(s2)):
        y = dict(zip((list(s2)), i))
        if int(y[s[0][0]]) == 0 or int(y[s[1][0]]) == 0 or int(y[s[2][0]]) == 0:
            continue
        if int(''.join(map(str, [y.get(key) for key in s[0]]))) + int(''.join(map(str, [y.get(key) for key in s[1]]))) == int(''.join(map(str, [y.get(key) for key in s[2]]))):
            otv = ' '.join('{} {}'.format(key, val) for key, val in sorted(y.items()))
            break
    return otv
 
s = input()
if len(set(s)) <= 11:
    print(men6(s))
else:
    res = find_solution(s)
    print(' '.join([f'{key} {val}' for key, val in res[0].items()]) if res else -1)

@Red white socks · 25.02.2023, 15:14

По таймингам попыток за 15 можно восстановить сам этот пример. Но сейчас некогда

@VadimK76 · 25.02.2023, 21:07 **[ТС]**

А как это сделать, если не секрет?

@Red white socks · 25.02.2023, 22:26

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

Python
1
2
3
4
5
from time import sleep
 
...
sleep(len(words[0])-2 + 5 * (len(words[1])-2))
...

Отправляем тест, смотрим время выполнения и восстанавливаем длины первых двух слов.

Затем заменяем

Python
1
2
3
4
5
from time import sleep
 
...
sleep(ord(words[0][0])-64)
...

Отправляем на тест и по времени выполнения находим ascii первой буквы первого слова и т.д. Максимум 18 попыток.
Тут надо аккуратно, чтобы не получить ошибку отсутствия элемента в списке.
Надо запрашивать с индексами 0, 1 или 2, а также -1, -2 и -3. У нас гарантированно длины от 3 до 6, поэтому слово таким образом полностью восстанавливается и не будет ошибок в процессе теста.

Не по теме:

будет очень любопытно получить этот тест и ударить себя по лбу - как же можно быть таким дураком.
Но я раз 50 пересмотрел свой код и не вижу даже малейшей возможности ошибке проскочить. А смотрел я с очень большим пристрастием...

@VadimK76 · 26.02.2023, 12:44 **[ТС]**

Red white socks, либо я сделал что то не так, либо яндекс контест умеет обходить подобные приемы. Код выполнялся минут 20 реального времени, но тайминги такие, как будто sleepa нет (первый скрин последних таймингов). Но, если смотреть отчет последних попыток, то там, видимо, время исполнения 46го теста (это точно не сумма времени всех попыток), но и это время какое-то странное (второй скриншот)

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from itertools import permutations, chain
from time import sleep
 
def check_correct(d: dict, first_letters) -> bool:
    if len(set(d.keys())) != len(set(d.values())):
        return False
    for x in first_letters:
        if d.get(x) == 0:
            return False
    return True
 
 
def replace_letters(word: str, d: dict, n: int) -> str:
    return ''.join(map(lambda x: str(d[x]), word[-n:]))
 
 
def check_equal(words: str, d: dict, n=0) -> bool:
    sum_words = sum(map(lambda x: int(replace_letters(x, d, n)), words[:-1]))
    return str(sum_words)[-n:] == replace_letters(words[-1], d, n)
 
 
def find_solution(expr: str) -> list:
    words = expr.replace('+', '=').split('=')
    if len(words[-1]) != max(map(len, words)):
        return None
 
    first_letters = set(map(lambda x: x[0], words))
    max_len = len(words[-1])
    variants = [{}]
    symbols = set()
    for i in range(1, max_len + 1):
        new_symbols = set(map(lambda x: x[-i] if i <= len(x) else x[-1], words)) - symbols
        new_variants = []
        for v in variants:
            for current in permutations(range(10), len(new_symbols)):
                v_new = dict(chain(v.items(), zip(new_symbols, current)))
                if check_correct(v_new, first_letters) and check_equal(words, v_new, i):
                    new_variants.append(v_new)
        symbols |= new_symbols
        variants = new_variants[:]
 
    final_variants = list(filter(lambda x: check_equal(words, x), variants))
    return final_variants
 
s = input()
s2 = s.replace('+', ' ').replace('=', ' ')
s2 = s2.split(' ')
sleep(len(s2[0])-2 + 5 * (len(s2[1])-2))
res = find_solution(s)
print(' '.join([f'{key} {val}' for key, val in res[0].items()]) if res else -1)

@VadimK76 · 26.02.2023, 12:52 **[ТС]**

Red white socks , еще такой вариант, я попробовал минимальные значения диапозона (100), и код его не проходит. К примеру вот такой вариант: СSS+СSS=BSS (100+100=200). Код должен выдать С 1 S 0 B 2, а выдает -1.

Хотя нет, тогда бы тест прошла химера, т.к. полный перебор этот тест проходит

@Gdez · 26.02.2023, 18:05

VadimK76, Вместо 40-й

Python
1
variants = new_variants[:]

Попробуй

Python
1
2
if len(new_variants):
    variants = new_variants[:]

@VadimK76 · 26.02.2023, 19:28 **[ТС]**

Gdez, 46ой не прошел

@Red white socks · 26.02.2023, 19:57

VadimK76, на вашем примере стало понятно.
В процедуре check_equal в этом случае не проходит проверку '00' == '0'
Сколько уже раз зарекался не сравнивать числа как строки

Вот это должно поправить

Python
1
2
3
def check_equal(words: str, d: dict, n=0) -> bool:
    sum_words = sum(map(lambda x: int(replace_letters(x, d, n)), words[:-1]))
    return int(str(sum_words)[-n:]) == int(replace_letters(words[-1], d, n))

@VadimK76 · 26.02.2023, 20:11 **[ТС]**

Red white socks, победа!

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from itertools import permutations, chain
 
 
def check_correct(d: dict, first_letters) -> bool:
    if len(set(d.keys())) != len(set(d.values())):
        return False
    for x in first_letters:
        if d.get(x) == 0:
            return False
    return True
 
 
def replace_letters(word: str, d: dict, n: int) -> str:
    return ''.join(map(lambda x: str(d[x]), word[-n:]))
 
 
def check_equal(words: str, d: dict, n=0) -> bool:
    sum_words = sum(map(lambda x: int(replace_letters(x, d, n)), words[:-1]))
    return int(str(sum_words)[-n:]) == int(replace_letters(words[-1], d, n))
 
def final_check(expr:str, d:dict) -> bool:
    for key, value in d.items():
        expr = expr.replace(key, str(value))
    return eval(expr.replace('=','=='))
 
 
def find_solution(expr: str) -> list:
    words = list(map(lambda x: x.strip(), expr.replace('+','=').split('=')))
    max_len = max(map(len, words))
    first_letters = set(map(lambda x: x[0], words))
    variants = [{}]
    symbols = set()
    for i in range(1, max_len + 1):
        new_symbols = set(map(lambda x: x[-i] if i <= len(x) else x[-1], words)) - symbols
        new_variants = []
        for v in variants:
            for current in permutations(range(10), len(new_symbols)):
                v_new = dict(chain(v.items(), zip(new_symbols, current)))
                if check_correct(v_new, first_letters) and check_equal(words, v_new, i):
                    new_variants.append(v_new)
        symbols |= new_symbols
        variants = new_variants[:]
 
    final_variants = list(filter(lambda x: final_check(expr, x), variants))
    return final_variants
 
 
res = find_solution(input())
print(' '.join([f'{key} {val}' for key, val in res[0].items()]) if res else -1)

Добавлено через 1 минуту
Red white socks, спасибо вам большое! Осталось понять ваш код, и задачу можно считать решенной

@Red white socks · 26.02.2023, 20:20

VadimK76, долгая тяжба получилась из-за кривых рук) Детская ошибка)

@VadimK76 · 26.02.2023, 20:24 **[ТС]**

Red white socks, мое решение так и не прошло, так что вы себя недооцениваете.

@Red white socks · 26.02.2023, 20:25

Обидно, что в первой версии этой функции я приводил все к числам и сравнивал по модулю 10**n, но отказался из-за каких-то уже непонятных соображений

Новые блоги и статьи Все статьи Все блоги /
Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .	Krabik для WoW 3.3.5a, многоязычный AmbA 02.07.2026 Допилил бота, думаю что окончательно. Изменения: - добавлена многоязычность - добавлено снятие скриншотов - добавлено поддержание бафов хождения по воде (для жреца, дк и шамана) - и так, по. . .
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	25.02.2023, 15:14
	По таймингам попыток за 15 можно восстановить сам этот пример. Но сейчас некогда 1

@VadimK76 20 / 1 / 0 Регистрация: 22.02.2023 Сообщений: 16
	25.02.2023, 21:07 [ТС]
	А как это сделать, если не секрет? 0

@VadimK76 20 / 1 / 0 Регистрация: 22.02.2023 Сообщений: 16
	26.02.2023, 12:52 [ТС]
	Red white socks , еще такой вариант, я попробовал минимальные значения диапозона (100), и код его не проходит. К примеру вот такой вариант: СSS+СSS=BSS (100+100=200). Код должен выдать С 1 S 0 B 2, а выдает -1. Хотя нет, тогда бы тест прошла химера, т.к. полный перебор этот тест проходит 0

@VadimK76 20 / 1 / 0 Регистрация: 22.02.2023 Сообщений: 16
	26.02.2023, 19:28 [ТС]
	Gdez, 46ой не прошел 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	26.02.2023, 20:20
	VadimK76, долгая тяжба получилась из-за кривых рук) Детская ошибка) 0

@VadimK76 20 / 1 / 0 Регистрация: 22.02.2023 Сообщений: 16
	26.02.2023, 20:24 [ТС]
	Red white socks, мое решение так и не прошло, так что вы себя недооцениваете. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	26.02.2023, 20:25
	Обидно, что в первой версии этой функции я приводил все к числам и сравнивал по модулю 10**n, но отказался из-за каких-то уже непонятных соображений 0

Буквометик

Решение