Буквометик

@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, но отказался из-за каких-то уже непонятных соображений

Новые блоги и статьи Все статьи Все блоги /
Право. Администации порталов. Законы и беззаконие. Hrethgir 26.06.2026 У меня сейчас так везде по форуму - не могу создавать сообщений, но запись по случаю этому https:/ / www. cyberforum. ru/ blogs/ 223907/ blog10939-page2. html#comments Hrethgir, не подскажете кто это. . .	сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .	сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .	сукцессия 3 anaschu 25.06.2026 Примерный план работ по модели
сукцессия 2 anaschu 25.06.2026 параметризировочная калибровочная таблица будущей модели	Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал (мат мет мод 29) anaschu 23.06.2026 Многофункциональное здание: как одно здание порождает конфликты требований, которые никто не планировал Материалы для обсуждения с МГСУ · 2026 Рисунки внутри приложенного ворд файла. Что за. . .	28. Конкретное развертывание плана номер 1 из поста номер 27 anaschu 22.06.2026 Можно ли из модели получить конкретные строительные требования? Честно — напрямую из текущей модели такие ответы не получить. Но цепочка логики есть, и она не такая длинная. Где разрыв . . .	27. Планы на разработку функциональных требований к строительству внутри модели пищеблока (или не только его?) anaschu 22.06.2026 Что уже реализовано и даёт конфликты «бесплатно» Самый простой конфликт уже работает — конфликт за ресурс-работника. Заданий больше, чем доступных поваров → очередь в queue1. Это прямое отражение. . .

@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

Буквометик

Решение