Блог

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

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

Пример:

 #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)
  

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

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

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

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

Например, если слово monkey, компьютеру просто будет присвоено —-e- Первым шагом для него было бы удалить из своего словаря все слова, которые не состоят из 6 букв, и все слова, которые не полностью соответствуют шаблону ‘—-e-‘ и поместить это в новый список. Как мне это сделать?

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

Мой текущий метод выполнения этого выглядит следующим образом:

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

Является ли это наиболее эффективным способом?

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

Является ли это эффективным алгоритмом? Существуют ли лучшие реализации?

В регулярных выражениях нет ничего особенно волшебного, и сопоставление их со всем вашим словарем все равно займет 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% слов, что означает, что вы в любом случае исключаете большинство возможностей. Даже это не оптимально — может случиться так, что определенные символы с большей вероятностью будут встречаться дважды в слове и, следовательно, исключат большую долю кандидатов — но это ближе.

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

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