Задача на операцию xor

[follower177]

Каждой букве русского алфавита (кроме букв ё и ъ) и символу пробел поставлено число от 0 до 31 соответственно (a - 0, б - 1 и т.д.).
Пусть T1 и T2 две русские осмысленные фразы длины 76 каждая. S = T1 xor T2. Как найти T1 и T2, зная S.
Небольшой пример, допустим s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25]
Подскажите в каком направлении думать?

 

[Exited3n]

Каждой букве русского алфавита (кроме букв ё и ъ) и символу пробел поставлено число от 0 до 31 соответственно (a - 0, б - 1 и т.д.).
Пусть T1 и T2 две русские осмысленные фразы длины 76 каждая. S = T1 xor T2. Как найти T1 и T2, зная S.
Небольшой пример, допустим s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25]
Подскажите в каком направлении думать?

а как у тебя s = 12 символов, а t1,2 аж по 76 0о ?

 

[ALT1RE]

S в твоем примере имеет рандомные значения?

 

[follower177]

S в твоем примере имеет рандомные значения?

В задаче которую нужно решить S =
[18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11, 0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11
3, 25, 2, 23, 16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0, 0, 14, 20, 0, 29, 8, 14, 1, 6, 18, 26, 5, 28,
4, 30, 21, 9, 6, 19, 9, 20, 13, 17, 15, 11, 6, 14, 8, 5, 16]
То есть это результат посимвольного xor T1 и T2 (T1 и T2 - это 100 процентов осмысленные фразы)
В моём примере, который я дал s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25] это результат сложения слов "безопасность" и "передвижение". Только в данном примере каждый символ кроме "ё" кодируется. То есть, (a - 0, б - 2 ..... я - 31)

 

[follower177]

а как у тебя s = 12 символов, а t1,2 аж по 76 0о ?

задаче которую нужно решить S =
[18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11, 0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11
3, 25, 2, 23, 16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0, 0, 14, 20, 0, 29, 8, 14, 1, 6, 18, 26, 5, 28,
4, 30, 21, 9, 6, 19, 9, 20, 13, 17, 15, 11, 6, 14, 8, 5, 16]

s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25] я показал для примера это результат сложения слов "безопасность" и "передвижение". Только в данном примере каждый символ кроме "ё" кодируется. То есть, (a - 0, б - 2 ..... я - 31)

 

[SuperGoga]

Каждой букве русского алфавита (кроме букв ё и ъ) и символу пробел поставлено число от 0 до 31 соответственно (a - 0, б - 1 и т.д.).
Пусть T1 и T2 две русские осмысленные фразы длины 76 каждая. S = T1 xor T2. Как найти T1 и T2, зная S.
Небольшой пример, допустим s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25]
Подскажите в каком направлении думать?

Интересно было бы получить подсказки по данной задаче или посмотреть алгоритм решения

 

[Koloboking]

Каждой букве русского алфавита (кроме букв ё и ъ) и символу пробел поставлено число от 0 до 31 соответственно (a - 0, б - 1 и т.д.).
Пусть T1 и T2 две русские осмысленные фразы длины 76 каждая. S = T1 xor T2. Как найти T1 и T2, зная S.
Небольшой пример, допустим s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25]
Подскажите в каком направлении думать?

Ты описал классическую задачу восстановления двух исходных текстов T1 и T2 по их посимвольному XOR:
S = T1 ^ T2,
где каждый символ кодируется числами от 0 до 31, включая пробел.

Уточнения:
Кодировка: а=0, б=1, ..., я=31, пробел тоже кодируется (скорее всего, как 32, но в твоём примере — от 0 до 31, значит пробел входит в этот диапазон).
Исключены: ё и ъ, их в словах не будет.
Значения S получены по S = T1 ⊕ T2, где ⊕ — битовый XOR по значениям из диапазона [0..31].
Для каждого S мы можем найти все возможные пары (x, y) такие, что x ^ y == S, где x и y — допустимые коды символов.
Но чтобы фразы были осмысленными, нужно:
Ограничить перебор только словами из настоящего русского языка. Применить словарный фильтр + проверку частот биграмм/триграмм (можно добавить позже).

Решение на Python (по примеру)​

Вот минимальный скрипт, который по S выдаёт все возможные пары слов (или строк длиной 12) из списка, удовлетворяющие x ^ y == s.
Для короткого примера:

# Маппинг: а=0, б=1, ..., я=31
alphabet = [chr(c) for c in range(ord('а'), ord('а') + 32)]  # без 'ё' и 'ъ'
char_to_code = {ch: i for i, ch in enumerate(alphabet)}
code_to_char = {i: ch for ch, i in char_to_code.items()}

# пример: s = без_опасность передвижение
s = [14, 0, 23, 11, 11, 2, 25, 11, 11, 28, 26, 25]

# все возможные коды [0..31]
codes = list(range(32))

# строим обратный словарь по XOR
from collections import defaultdict
xor_pairs = defaultdict(list)
for x in codes:
    for y in codes:
        if x ^ y < 32:
            xor_pairs[x ^ y].append((x, y))

# найти все пары строк длины len(s)
def recover_all(s):
    from itertools import product
    all_possibilities = []
    for i, val in enumerate(s):
        all_possibilities.append(xor_pairs[val])
    # теперь перебор: сужаем по словарю
    return all_possibilities

def decode(code_seq):
    return ''.join(code_to_char[c] for c in code_seq)

# пример: показать 5 вариантов
from itertools import islice
count = 0
for variant in islice(product(*recover_all(s)), 10):
    left = [a for a, _ in variant]
    right = [b for _, b in variant]
    print("T1:", decode(left), " | T2:", decode(right))

Для фразы длиной 76 символов:
Простой перебор невозможен (32² = 1024 комбинации на каждый символ → 1024⁷⁶ = ад).
Нужно использовать словарь частотных русских слов и фраз:
Построить суффиксное дерево/префиксный словарь (trie) на основе корпуса.
Применить поразрядный перебор, сохраняя только те варианты, которые продолжают осмысленную фразу (по частотам биграмм/триграмм).
Или использовать beam search.

Вероятный подход к основной задаче (S длиной 76):​

Сформировать таблицу кодирования: буквы а–я, без ё и ъ → 0..31.
Загрузить список слов из частотного корпуса (например, russian-words).
Поиск:
Использовать префиксный поиск (trie).
Для каждой позиции в S:
взять допустимые пары (x, y) с x ^ y == S.
оставить только те, которые продолжают осмысленное слово (например, если T1[0:5] уже привет, то следующая буква м может идти только если приветм... — начало известного слова или фразы).
Можно применять beam search с ограничением по количеству кандидатов (например, top-100).
Восстановить T1 и T2.

 

[Koloboking]

задаче которую нужно решить S =
[18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11, 0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11
3, 25, 2, 23, 16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0, 0, 14, 20, 0, 29, 8, 14, 1, 6, 18, 26, 5, 28,
4, 30, 21, 9, 6, 19, 9, 20, 13, 17, 15, 11, 6, 14, 8, 5, 16]

s = [14, 0, 23, 11, 11,2 ,25,11,11,28,26,25] я показал для примера это результат сложения слов "безопасность" и "передвижение". Только в данном примере каждый символ кроме "ё" кодируется. То есть, (a - 0, б - 2 ..... я - 31)

если дашь полностью задачу подскажу алгоритм

 

[SuperGoga]

Ты описал классическую задачу восстановления двух исходных текстов T1 и T2 по их посимвольному XOR:
S = T1 ^ T2,
где каждый символ кодируется числами от 0 до 31, включая пробел.

Уточнения:
Кодировка: а=0, б=1, ..., я=31, пробел тоже кодируется (скорее всего, как 32, но в твоём примере — от 0 до 31, значит пробел входит в этот диапазон).
Исключены: ё и ъ, их в словах не будет.
Значения S получены по S = T1 ⊕ T2, где ⊕ — битовый XOR по значениям из диапазона [0..31].
Для каждого S мы можем найти все возможные пары (x, y) такие, что x ^ y == S, где x и y — допустимые коды символов.
Но чтобы фразы были осмысленными, нужно:
Ограничить перебор только словами из настоящего русского языка. Применить словарный фильтр + проверку частот биграмм/триграмм (можно добавить позже).

Решение на Python (по примеру)​

Вот минимальный скрипт, который по S выдаёт все возможные пары слов (или строк длиной 12) из списка, удовлетворяющие x ^ y == s.
Для короткого примера:

# Маппинг: а=0, б=1, ..., я=31
alphabet = [chr(c) for c in range(ord('а'), ord('а') + 32)]  # без 'ё' и 'ъ'
char_to_code = {ch: i for i, ch in enumerate(alphabet)}
code_to_char = {i: ch for ch, i in char_to_code.items()}

# пример: s = без_опасность передвижение
s = [14, 0, 23, 11, 11, 2, 25, 11, 11, 28, 26, 25]

# все возможные коды [0..31]
codes = list(range(32))

# строим обратный словарь по XOR
from collections import defaultdict
xor_pairs = defaultdict(list)
for x in codes:
    for y in codes:
        if x ^ y < 32:
            xor_pairs[x ^ y].append((x, y))

# найти все пары строк длины len(s)
def recover_all(s):
    from itertools import product
    all_possibilities = []
    for i, val in enumerate(s):
        all_possibilities.append(xor_pairs[val])
    # теперь перебор: сужаем по словарю
    return all_possibilities

def decode(code_seq):
    return ''.join(code_to_char[c] for c in code_seq)

# пример: показать 5 вариантов
from itertools import islice
count = 0
for variant in islice(product(*recover_all(s)), 10):
    left = [a for a, _ in variant]
    right = [b for _, b in variant]
    print("T1:", decode(left), " | T2:", decode(right))

Для фразы длиной 76 символов:
Простой перебор невозможен (32² = 1024 комбинации на каждый символ → 1024⁷⁶ = ад).
Нужно использовать словарь частотных русских слов и фраз:
Построить суффиксное дерево/префиксный словарь (trie) на основе корпуса.
Применить поразрядный перебор, сохраняя только те варианты, которые продолжают осмысленную фразу (по частотам биграмм/триграмм).
Или использовать beam search.

Вероятный подход к основной задаче (S длиной 76):​

Сформировать таблицу кодирования: буквы а–я, без ё и ъ → 0..31.
Загрузить список слов из частотного корпуса (например, russian-words).
Поиск:
Использовать префиксный поиск (trie).
Для каждой позиции в S:
взять допустимые пары (x, y) с x ^ y == S.
оставить только те, которые продолжают осмысленное слово (например, если T1[0:5] уже привет, то следующая буква м может идти только если приветм... — начало известного слова или фразы).
Можно применять beam search с ограничением по количеству кандидатов (например, top-100).
Восстановить T1 и T2.

если дашь полностью задачу подскажу алгоритм

Задача приведена на фото. Для удобства данные:
alph = {
'а': 0, 'б': 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
}
S = [
18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11,
0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11, 3, 25, 2, 23,
16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0,
0, 14, 20, 0, 29, 8, 14, 1, 6, 18, 26, 5, 28, 4, 30,
21, 9, 6, 19, 9, 20, 13, 17, 15, 11, 6, 14, 8, 5, 16
]

 

[SuperGoga]

Ты описал классическую задачу восстановления двух исходных текстов T1 и T2 по их посимвольному XOR:
S = T1 ^ T2,
где каждый символ кодируется числами от 0 до 31, включая пробел.

Уточнения:
Кодировка: а=0, б=1, ..., я=31, пробел тоже кодируется (скорее всего, как 32, но в твоём примере — от 0 до 31, значит пробел входит в этот диапазон).
Исключены: ё и ъ, их в словах не будет.
Значения S получены по S = T1 ⊕ T2, где ⊕ — битовый XOR по значениям из диапазона [0..31].
Для каждого S мы можем найти все возможные пары (x, y) такие, что x ^ y == S, где x и y — допустимые коды символов.
Но чтобы фразы были осмысленными, нужно:
Ограничить перебор только словами из настоящего русского языка. Применить словарный фильтр + проверку частот биграмм/триграмм (можно добавить позже).

Решение на Python (по примеру)​

Вот минимальный скрипт, который по S выдаёт все возможные пары слов (или строк длиной 12) из списка, удовлетворяющие x ^ y == s.
Для короткого примера:

# Маппинг: а=0, б=1, ..., я=31
alphabet = [chr(c) for c in range(ord('а'), ord('а') + 32)]  # без 'ё' и 'ъ'
char_to_code = {ch: i for i, ch in enumerate(alphabet)}
code_to_char = {i: ch for ch, i in char_to_code.items()}

# пример: s = без_опасность передвижение
s = [14, 0, 23, 11, 11, 2, 25, 11, 11, 28, 26, 25]

# все возможные коды [0..31]
codes = list(range(32))

# строим обратный словарь по XOR
from collections import defaultdict
xor_pairs = defaultdict(list)
for x in codes:
    for y in codes:
        if x ^ y < 32:
            xor_pairs[x ^ y].append((x, y))

# найти все пары строк длины len(s)
def recover_all(s):
    from itertools import product
    all_possibilities = []
    for i, val in enumerate(s):
        all_possibilities.append(xor_pairs[val])
    # теперь перебор: сужаем по словарю
    return all_possibilities

def decode(code_seq):
    return ''.join(code_to_char[c] for c in code_seq)

# пример: показать 5 вариантов
from itertools import islice
count = 0
for variant in islice(product(*recover_all(s)), 10):
    left = [a for a, _ in variant]
    right = [b for _, b in variant]
    print("T1:", decode(left), " | T2:", decode(right))

Для фразы длиной 76 символов:
Простой перебор невозможен (32² = 1024 комбинации на каждый символ → 1024⁷⁶ = ад).
Нужно использовать словарь частотных русских слов и фраз:
Построить суффиксное дерево/префиксный словарь (trie) на основе корпуса.
Применить поразрядный перебор, сохраняя только те варианты, которые продолжают осмысленную фразу (по частотам биграмм/триграмм).
Или использовать beam search.

Вероятный подход к основной задаче (S длиной 76):​

Сформировать таблицу кодирования: буквы а–я, без ё и ъ → 0..31.
Загрузить список слов из частотного корпуса (например, russian-words).
Поиск:
Использовать префиксный поиск (trie).
Для каждой позиции в S:
взять допустимые пары (x, y) с x ^ y == S.
оставить только те, которые продолжают осмысленное слово (например, если T1[0:5] уже привет, то следующая буква м может идти только если приветм... — начало известного слова или фразы).
Можно применять beam search с ограничением по количеству кандидатов (например, top-100).
Восстановить T1 и T2.

Спасибо за ответ. Я в своей попытке руководствовался теми же принципами. Мне не удалось составить словарь фраз одинаковой длины(76 символов).

 

[Koloboking]

Спасибо за ответ. Я в своей попытке руководствовался теми же принципами. Мне не удалось составить словарь фраз одинаковой длины(76 символов).

Условие задачи:
Каждой букве русского алфавита (кроме букв «ё» и «ъ») и знаку «пробел» поставлено в соответствие число от 0 до 31:
а – 0 и – 8 р – 16 ш – 24 б – 1 й – 9 с – 17 щ – 25 в – 2
к – 10 т – 18 ы – 26 г – 3 л – 11 у – 19 ь – 27 д – 4 м – 12
ф – 20 э – 28 е – 5 н – 13 х – 21 ю – 29 ж – 6 о – 14 ц – 22
я – 30 з – 7 п – 15 ч – 23
пробел – 31
Пусть T1 и T2 — две русские осмысленные фразы длиной 76 каждая
Дана их поэлементная сумма: T1 ⊕ T2 = [18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11, 0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11, 3, 25, 2, 23, 16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0, 14, 20, 0, 29, 8, 14, 14, 1, 6, 28, 4, 30, 21, 9, 6, 19, 9, 20, 13, 17, 15, 15, 1, 6, 14, 8, 5, 16, 7, 2]
Поэлементная сумма производится с помощью операции поразрядного сложения по mod 2.
Задание:
Найти фразы T1 и T2.

ПРАВИЛО XOR (⊕):
A ⊕ B = 0 ⟺ A = B
Другими словами:
XOR равен 0 ТОЛЬКО когда оба числа одинаковые
XOR не равен 0 когда числа разные
Применительно к задаче:
В позициях 1, 10, 16, 45, 48 результат XOR = 0
Значит, T1[1] = T2[1], T1[10] = T2[10], T1[16] = T2[16], T1[45] = T2[45], T1[48] = T2[48]
Это означает, что в этих позициях обе фразы содержат абсолютно одинаковые символы.

Есть ограничение на одинаковые символы​

Ключевое ограничение: В позициях 1, 10, 16, 45, 48 символы в T1 и T2 абсолютно одинаковые.

Структурный анализ:​

Позиция: 0123456789012345678901234567890123456789012345678...
Шаблон:  ?X????????X?????X????????????????????????????X??X?
         ^    ^     ^                             ^  ^
         1    10    16                           45 48

Это значительно сужает поисковое пространство - не любые две фразы подойдут!
Предположить, что одинаковые позиции содержат частые символы (пробел, 'а', 'е', 'и', 'о')
Если позиции 1, 10, 16 = пробелы, то структура: X пробел XXXXXXXX пробел XXXXX пробел...
Это дает слова длиной: 1, 8, 5 букв в начале

нужен анализ источника задачи если других подсказок нет​

Откуда взята задача? (учебник, олимпиада, курс?)​

Какой уровень сложности?
Какая тематика курса?

 

[SuperGoga]

Условие задачи:
Каждой букве русского алфавита (кроме букв «ё» и «ъ») и знаку «пробел» поставлено в соответствие число от 0 до 31:
а – 0 и – 8 р – 16 ш – 24 б – 1 й – 9 с – 17 щ – 25 в – 2
к – 10 т – 18 ы – 26 г – 3 л – 11 у – 19 ь – 27 д – 4 м – 12
ф – 20 э – 28 е – 5 н – 13 х – 21 ю – 29 ж – 6 о – 14 ц – 22
я – 30 з – 7 п – 15 ч – 23
пробел – 31
Пусть T1 и T2 — две русские осмысленные фразы длиной 76 каждая
Дана их поэлементная сумма: T1 ⊕ T2 = [18, 0, 12, 8, 3, 12, 27, 26, 29, 12, 0, 31, 5, 19, 26, 11, 0, 2, 18, 1, 6, 5, 28, 26, 9, 27, 11, 3, 25, 2, 23, 16, 15, 30, 4, 2, 23, 13, 23, 8, 16, 19, 4, 27, 1, 0, 14, 20, 0, 29, 8, 14, 14, 1, 6, 28, 4, 30, 21, 9, 6, 19, 9, 20, 13, 17, 15, 15, 1, 6, 14, 8, 5, 16, 7, 2]
Поэлементная сумма производится с помощью операции поразрядного сложения по mod 2.
Задание:
Найти фразы T1 и T2.

ПРАВИЛО XOR (⊕):
A ⊕ B = 0 ⟺ A = B
Другими словами:
XOR равен 0 ТОЛЬКО когда оба числа одинаковые
XOR не равен 0 когда числа разные
Применительно к задаче:
В позициях 1, 10, 16, 45, 48 результат XOR = 0
Значит, T1[1] = T2[1], T1[10] = T2[10], T1[16] = T2[16], T1[45] = T2[45], T1[48] = T2[48]
Это означает, что в этих позициях обе фразы содержат абсолютно одинаковые символы.

Есть ограничение на одинаковые символы​

Ключевое ограничение: В позициях 1, 10, 16, 45, 48 символы в T1 и T2 абсолютно одинаковые.

Структурный анализ:​

Позиция: 0123456789012345678901234567890123456789012345678...
Шаблон:  ?X????????X?????X????????????????????????????X??X?
         ^    ^     ^                             ^  ^
         1    10    16                           45 48

Это значительно сужает поисковое пространство - не любые две фразы подойдут!
Предположить, что одинаковые позиции содержат частые символы (пробел, 'а', 'е', 'и', 'о')
Если позиции 1, 10, 16 = пробелы, то структура: X пробел XXXXXXXX пробел XXXXX пробел...
Это дает слова длиной: 1, 8, 5 букв в начале

нужен анализ источника задачи если других подсказок нет​

Откуда взята задача? (учебник, олимпиада, курс?)​

Какой уровень сложности?
Какая тематика курса?

Про сложность и источник задачи ничего не могу сказать, потому что сам не знаю.

 

[Koloboking]

Про сложность и источник задачи ничего не могу сказать, потому что сам не знаю.

переименуй в .py, словарь например тут, установи numba и pymorphy2 Морфологический анализ: через pymorphy2 (если установлено) и попробуй погонять

 

[SuperGoga]

переименуй в .py, словарь например тут, установи numba и pymorphy2 Морфологический анализ: через pymorphy2 (если установлено) и попробуй погонять
Посмотреть вложение 80029

Посмотреть вложение 80030

Спасибо большое за программу! Пока она выполняется, разбираю код.

 

[SuperGoga]

переименуй в .py, словарь например тут, установи numba и pymorphy2 Морфологический анализ: через pymorphy2 (если установлено) и попробуй погонять
Посмотреть вложение 80029

Посмотреть вложение 80030

Прогнал программу на наборах 50к, 100к и 300к. (Ограничение на 100к убрал.) В результате получить искомые фразы не удалось. На 50к и 100к решения получились с весом не выше 0,5, а xor проверку ни одно не прошло. На 300к выдало три решения с удачным xor, но также все решения ниже 0,5 по весу (качеству). В своей реализации я отталкиваюсь от того, что изначально рассматриваю пары символов, которые дают нужную сумму по модулю 2. Вроде это должно уменьшить количество фраз для рассмотрения. Также затратно получилось по времени выполнения кода - десятки часов.

 

[SuperGoga]

Прогнал программу на наборах 50к, 100к и 300к. (Ограничение на 100к убрал.) В результате получить искомые фразы не удалось. На 50к и 100к решения получились с весом не выше 0,5, а xor проверку ни одно не прошло. На 300к выдало три решения с удачным xor, но также все решения ниже 0,5 по весу (качеству). В своей реализации я отталкиваюсь от того, что изначально рассматриваю пары символов, которые дают нужную сумму по модулю 2. Вроде это должно уменьшить количество фраз для рассмотрения. Также затратно получилось по времени выполнения кода - десятки часов.

Также интересно как увеличить производительность выполнения кода. У меня 8 ядерный процессор и программа задействует только 10% ЦП.