Python RegEx - алгоритм палача

Question

Я пытаюсь написать алгоритм палача. Моя идея такова:

• Предварительная обработка словаря, который содержит относительные буквенные частоты слов в зависимости от их длины. Шаг завершен.

Пример:

#Each key corresponds to length of the word.   

frequencyDict = {2: ['a', 'o', 'e', 'i', 'm', 'h', 'n', 'u', 's', 't', 'y', 'b', 'd', 'l', 'p', 'x', 'f', 'r', 'w', 'g', 'k', 'j'], 
  3: ['a', 'e', 'o', 'i', 't', 's', 'u', 'p', 'r', 'n', 'd', 'b', 'm', 'g', 'y', 'l', 'h', 'w', 'f', 'c', 'k', 'x', 'v', 'j', 'z', 'q'], 
  4: ['e', 'a', 's', 'o', 'i', 'l', 'r', 't', 'n', 'u', 'd', 'p', 'm', 'h', 'b', 'c', 'g', 'k', 'y', 'f', 'w', 'v', 'j', 'z', 'x', 'q'],
  5: ['s', 'e', 'a', 'o', 'r', 'i', 'l', 't', 'n', 'd', 'u', 'c', 'p', 'y', 'm', 'h', 'g', 'b', 'k', 'f', 'w', 'v', 'z', 'x', 'j', 'q'],
  6: ['e', 's', 'a', 'r', 'i', 'o', 'l', 'n', 't', 'd', 'u', 'c', 'p', 'm', 'g', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'j', 'q'],
  7: ['e', 's', 'a', 'i', 'r', 'n', 'o', 't', 'l', 'd', 'u', 'c', 'g', 'p', 'm', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'j', 'q'],
  8: ['e', 's', 'i', 'a', 'r', 'n', 'o', 't', 'l', 'd', 'c', 'u', 'g', 'p', 'm', 'h', 'b', 'y', 'f', 'k', 'w', 'v', 'z', 'x', 'q', 'j']}

У меня также есть генератор слов в словаре:

dictionary = word_reader('C:\\Python27\\dictionary.txt', len(letters))

Который основан на этой функции

#Strips dictionary of words that are too big or too small from the list
def word_reader(filename, L):
  L2 = L+2
  return (word.strip() for word in open(filename) \
          if len(word) < L2 and len(word) > 2)

• Эта конкретная игра даст вам последний гласный бесплатно. Если слово было земляным, например, пользователь получит следующую доску: e ---- e- догадаться. Итак, я хочу найти способ создать новый генератор или список со всеми вычеркнутыми словами, которые не соответствуют шаблону e ---- e.

p = re.compile('^e\D\D\D\De\D$', re.IGNORECASE) сделает это, но может найти слова которые содержат 'e' в других местах, кроме первой и второй до последней буквы.

Итак, мой первый вопрос:

1. Как мне убедиться, что «е» расположен ТОЛЬКО в первом и от второй до последней позиции
2. Как мне создать интеллектуальную функцию, которая будет иметь новое регулярное выражение при обновлении головоломки, и компьютер продолжает делать предположения?

Например, если слово «обезьяна», компьютеру просто дадут ---- e- Первым шагом будет удаление из словаря всех слов, не являющихся 6-ю буквами, и всех слов, которые не полностью соответствуют шаблону '---- e-', и помещение их в новый список. Как сделать Я собираюсь сделать это?

Затем он вычисляет НОВЫЙ частотаDict на основе относительной частоты слов, которые находятся в его NewList.

Мой текущий способ сделать это выглядит так:

   cnt = Counter()
   for words in dictionary:
      for letters in words:
         cnt[letters]+=1

Это самый эффективный способ?

Затем он использовал бы newfrequencyDict, чтобы угадать наиболее распространенную букву, предполагая, что она имеет еще не угадал. Он продолжает делать это, пока (надеюсь) слово не будет угадано.

Это эффективный алгоритм? Есть ли лучшие реализации?

Answer 1

Это довольно много вопросов.Я постараюсь ответить на несколько.

1. Ваше регулярное выражение должно выглядеть примерно так: '^e[^e][^e][^e][^e]e[^e]$'.Эти [^e] биты говорят "соответствуют любому символу, который не является" е ". Обратите внимание, что в отличие от вашего регулярного выражения, этот будет мах не буквенных символов, но это не должно быть проблемой, если вы убедитесь, что вашВ словаре есть только буквы. Обратите внимание, что после того, как вы обнаружили более одной буквы, вы должны поместить все буквы в каждый из этих разделов «не совпадают». Например, скажем, что «a» угадано, поэтому это «ea»--- e- ", теперь вы будете сопоставлять с регулярным выражением '^ea[^ae][^ae][^ae]e[^ae]$'.
2. Вы можете просто написать функцию, которая принимает строку типа" ea --- e- "и создает регулярное выражениеот него. Просто нужно а) найти все не дефисные буквы в строке, как набор (в данном случае, {'a', 'e'}), б) сгладить набор в "матч-все-но-это""фрагмент регулярного выражения ([^ae]) - обратите внимание, что порядок не важен, поэтому я использовал набор, в) заменил каждый дефис одним из них (ea[^ae][^ae][^ae]e[^ae]), и d) наконец, просто поставил '^ 'спереди и' $ 'в конце.
3. Наконец, с помощью dict частоты - хорошо, что яЭто очень отдельный вопрос.Трудно добиться большей эффективности, чем линейный поиск по всему словарю.Одно из предложений, которое я хотел бы сделать, заключается в том, что вам, возможно, не следует считать буквы несколько раз.Например, хотите ли вы, чтобы слово «земляной» приносило 2 балла в счет буквы «е»?Я бы предположил в Hangman, что вы хотите, чтобы он считался только один раз, поскольку слово «eeeeeeee» и слово «the» имеют одинаковый результат для угадывания буквы «e» (успех).Но я могу ошибаться.

Answer 2

Нет ничего особенного в регулярных выражениях, и сопоставление их со всем вашим словарем все равно займет O (n) время.Я бы порекомендовал написать свою собственную функцию, которая определяет, соответствует ли слово шаблону, и до сих пор через него проходить словарь.

Вот пример функции:

def matches_template(word, template):
  found_chars = set(x for x in template if x != '-')
  for char, template_char in zip(word, template):
    if template_char == '-':
      if char in found_chars: return False
    else:
      if template_char != char: return False
  return True

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