Как мне разрешать упражнения «Crypt Kicker», предложенные в «Проблемах программирования (руководство по обучению конкурса программирования)»?

StackOverflow https://stackoverflow.com/questions/2175356

  •  24-09-2019
  •  | 
  •  

Вопрос

«Проблемы по программированию (руководство по обучению конкурса программирования)», вероятно, является одной из самых хороших упражнений, книга по алгоритмам. Я решил первые 11 упражнений, но теперь я застрял с проблемой «Crypt Kicker»:

Crypt Kicker.
Обычный, но небезопасный метод шифрования текста - развернуть буквы алфавита. Другими словами, каждая буква алфавита последовательно заменяется в тексте какой-то другой буквой. Чтобы убедиться, что шифрование обратимо, ни одно количество букв не заменяется на одно и то же буква.

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

Вход
Вход состоит из линии, содержащей целое число N, за ним, а затем n строчные слова, по одному на линию, в алфавитном порядке. Эти N слов составляют словарь слов, которые могут появляться в расшифрованном тексте.
Следуя словарю несколько строк ввода. Каждая строка зашифрована, как описано выше.

В словаре нет более 1000 слов. Ни одно слово не превышает 16 букв. Зашифрованные линии содержат только строчные буквы и пробелы и не превышают длиной 80 символов.

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

Образец ввода 6
а также
Дик
Джейн
пышность
обнаруживать
Йерль

BJVG XSB HXSN XSB QYMM XSB RQAT XSB PNetFN
XXXX YYY ZZZZ WWW YYYY AAA BBBB CCC DDDDDD

Образец вывода
Дик и Джейн и слойки и пятно и йорль ...

какой стратегия Должен ли я предпринять, чтобы решить это упражнение? Я думал о классическом и закуривом обратному решению, но я пытаюсь избежать того, пока не найду чего-то более умных.

PS: Это не домашнее задание, связанное с домашними задачами, я просто пытаюсь улучшить свои общие навыки.

Это было полезно?

Решение

Keyraray проведет замену таблицы.

  • Начните с пустой клейки, это версия 0

  • Соответствуйте самое длинное зашифрованное слово для длительного словаря и добавьте в килограмм (если есть два самых длинных, выбирать любые), это версия 1.

  • Расширяя некоторые буквы следующего самого длинного закрепленного слова.

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

  • Если некоторые буквы совпадают, добавьте остальные буквы в KeeRaray, это версия 2.

  • Расширяя некоторые буквы следующего самого длинного закрепленного слова.

  • Проверьте, соответствуют ли дешифрованные буквы буквы в той же позиции в любом словаре.
  • Если нет совпадения, вернитесь к версии 1 и попробуйте другое слово
  • Если некоторые буквы совпадают, добавьте остальные буквы в Keebray, это версия 3.

Повторите, пока все слова не будут расшифрованы.

Если в версии 0 ни одно из самых длинных слов не создает частичный дешифру в более короткие слова, очень вероятно, нет решения.

Другие советы

Незначительная оптимизация может быть выполнена путем перечисления возможностей перед запуском Backtracking. В Python:

dictionary = ['and', 'dick', 'jane', 'puff', 'spot', 'yertle']
line = ['bjvg', 'xsb', 'hxsn', 'xsb', 'qymm', 'xsb', 'rqat', 'xsb', 'pnetfn']

# ------------------------------------

import collections

words_of_length = collections.defaultdict(list)

for word in dictionary:
  words_of_length[len(word)].append(word)

possibilities = collections.defaultdict(set)
certainities = {}

for word in line:
    length = len(word)
    for i, letter in enumerate(word):
        if len(words_of_length[length]) == 1:
            match = words_of_length[length][0]
            certainities[letter] = match[i]
        else:
            for match in words_of_length[length]:
              possibilities[letter].add(match[i])

for letter in certainities.itervalues():
    for k in possibilities:
        possibilities[k].discard(letter)

for i, j in certainities.iteritems():
    possibilities[i] = set([j])

# ------------------------------------

import pprint
pprint.pprint(dict(possibilities))

Выход:

{'a': set(['c', 'f', 'o']),
 'b': set(['d']),
 'e': set(['r']),
 'f': set(['l']),
 'g': set(['f', 'k']),
 'h': set(['j', 'p', 's']),
 'j': set(['i', 'p', 'u']),
 'm': set(['c', 'f', 'k', 'o']),
 'n': set(['e']),
 'p': set(['y']),
 'q': set(['i', 'j', 'p', 's', 'u']),
 'r': set(['j', 'p', 's']),
 's': set(['n']),
 't': set(['t']),
 'v': set(['c', 'f', 'o']),
 'x': set(['a']),
 'y': set(['i', 'p', 'u'])}

Если у вас есть некоторые возможности одноэлементных возможностей, вы можете устранить их от ввода и повторной обработки алгоритма.

РЕДАКТИРОВАТЬ: Переключился на установку вместо списка и добавленного печатающего кода.

Я на самом деле попробовал довольно разный подход. Я построил TRE из словарных слов. Затем я прохожу через Три и предложение рекурсивно (пересекая ТРИ в DFS).

В каждом пространстве я убедитесь, что ударил конец слова в TRIE, и если так, я вернусь в корню. По пути я отслеживаю записанные письма, которые я сделал до сих пор. Если у меня когда-либо у меня есть задание, которое противоречит предыдущему заданию, которое я потерю неудачу и разгадаю рекурсию в точку, которую я могу сделать следующую возможную ассигнование.

Это звучит хитрым, но кажется, хорошо работает. И это действительно не так сложно код!

Еще одна возможная оптимизация, если у вас есть «достаточно» текста, чтобы иметь дело, и вы знаете язык текста, вы можете использовать буквы частоты (см.: http://en.wikipedia.org/wiki/Letter_frequency). Это, конечно, очень приблизительный подход при работе с 6/7 слов, но будет самым быстрым способом, если у вас есть несколько страниц для декодирования.

Редактировать: О решении Max, вы можете попытаться извлечь некоторые характеристики слова тоже, такие как повторяющиеся буквы. Очевидно, что замечало, что слойки в словаре и Qymm в зашифрованном тексте являются единственными четырем буквенными словами, заканчивающимися с двойной буквой, дает прямой ответ на 3 из букв. В более сложных сценариях вы должны уметь сузить возможности для каждой буквы.

Вот реализация Java с дополнительными уточнениями к алгоритм Предлагается @Carlos Gutiérrez.

Алгоритм крипта кикера и решение, что пошло не так?

  • Уточнение состоит в том, чтобы добавить шаблон слов, чтобы уменьшить пространство поиска для слов. Например, слова «ABC» и «ее» имеют один и тот же рисунок, в то время как «AAC» и «ее» не так, как трех разных букв, не совпадают, не совпадают.

  • Более того, алгоритм может быть реализован рекурсивно, что более интуитивно и разумно.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top