Алгоритм классификации слов для уровней сложности палача как "Легкий", "Средний" или "Жесткий",

Ответ 1

1. Введение

Здесь вы можете систематически подходить к этой проблеме: если у вас есть алгоритм, который хорошо играет палач, тогда вы можете с трудом усвоить каждое слово числом неправильных догадок, которые ваша программа могла бы предпринять, если угадать это слово.

2. Помимо стратегии палача

Есть идея, подразумевающая в некоторых других ответах и ​​комментариях, что оптимальная стратегия для решателя будет заключаться в том, чтобы основывать свои решения на частоте букв на английском языке или на частоте слов в каком-то корпусе. Это соблазнительная идея, но это не совсем правильно. Решатель лучше всего подходит, если он точно моделирует распределение слов, выбранных установщиком, и человек-сеттер вполне может выбирать слова, основанные на их редкости или избегая часто используемых писем. Например, хотя E является наиболее часто используемой буквой на английском языке, если сеттер всегда выбирает слова JUGFUL, RHYTHM, SYZYGY и ZYTHUM, то идеальный решатель не начинается с угадывания E!

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

3. Алгоритм палача

Здесь я расскажу о решателе, который довольно хорош (но далек от совершенства). Он моделирует установщика как выбор слов равномерно из фиксированного словаря. Это жадный алгоритм: на каждом этапе он угадывает букву, которая сводит к минимуму количество промахов, то есть слов, которые не содержат угадывания. Например, если до сих пор не было сделано никаких догадок, а возможные слова DEED, DEAD и DARE, то:

• если вы догадались D или E, пропусков нет;
• если вы угадали A, там пропустите (DEED);
• если вы догадались R, есть две промахи (DEED и DEAD);
• если вы угадаете любую другую букву, есть три промаха.

Так что либо D, либо E является хорошей предпосылкой в ​​этой ситуации.

(Благодаря Colonel Panic в комментариях, указав, что правильные догадки бесплатны в палачах - я полностью забыл об этом в моей первой попытке!)

4. Реализация

Здесь реализация этого алгоритма в Python:

from collections import defaultdict
from string import ascii_lowercase

def partition(guess, words):
    """Apply the single letter 'guess' to the sequence 'words' and return
    a dictionary mapping the pattern of occurrences of 'guess' in a
    word to the list of words with that pattern.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> sorted(list(partition('e', words).items()))
    [(0, ['star']), (2, ['mews']), (5, ['even', 'eyes']), (6, ['deed', 'peep'])]

    """
    result = defaultdict(list)
    for word in words:
        key = sum(1 << i for i, letter in enumerate(word) if letter == guess)
        result[key].append(word)
    return result

def guess_cost(guess, words):
    """Return the cost of a guess, namely the number of words that don't
    contain the guess.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> guess_cost('e', words)
    1
    >>> guess_cost('s', words)
    3

    """
    return sum(guess not in word for word in words)

def word_guesses(words, wrong = 0, letters = ''):
    """Given the collection 'words' that match all letters guessed so far,
    generate tuples (wrong, nguesses, word, guesses) where
    'word' is the word that was guessed;
    'guesses' is the sequence of letters guessed;
    'wrong' is the number of these guesses that were wrong;
    'nguesses' is len(guesses).

    >>> words = 'deed even eyes heel mere peep star'.split()
    >>> from pprint import pprint
    >>> pprint(sorted(word_guesses(words)))
    [(0, 1, 'mere', 'e'),
     (0, 2, 'deed', 'ed'),
     (0, 2, 'even', 'en'),
     (1, 1, 'star', 'e'),
     (1, 2, 'eyes', 'en'),
     (1, 3, 'heel', 'edh'),
     (2, 3, 'peep', 'edh')]

    """
    if len(words) == 1:
        yield wrong, len(letters), words[0], letters
        return
    best_guess = min((g for g in ascii_lowercase if g not in letters),
                     key = lambda g:guess_cost(g, words))
    best_partition = partition(best_guess, words)
    letters += best_guess
    for pattern, words in best_partition.items():
        for guess in word_guesses(words, wrong + (pattern == 0), letters):
            yield guess

5. Примеры результатов

Используя эту стратегию, можно оценить сложность угадывания каждого слова в коллекции. Здесь я рассматриваю шестибуквенные слова в своем системном словаре:

>>> words = [w.strip() for w in open('/usr/share/dict/words') if w.lower() == w]
>>> six_letter_words = set(w for w in words if len(w) == 6)
>>> len(six_letter_words)
15066
>>> results = sorted(word_guesses(six_letter_words))

Самые легкие слова, чтобы угадать в этом словаре (вместе с последовательностью догадок, необходимых для решения, чтобы угадать их), следующие:

>>> from pprint import pprint
>>> pprint(results[:10])
[(0, 1, 'eelery', 'e'),
 (0, 2, 'coneen', 'en'),
 (0, 2, 'earlet', 'er'),
 (0, 2, 'earner', 'er'),
 (0, 2, 'edgrew', 'er'),
 (0, 2, 'eerily', 'el'),
 (0, 2, 'egence', 'eg'),
 (0, 2, 'eleven', 'el'),
 (0, 2, 'enaena', 'en'),
 (0, 2, 'ennead', 'en')]

и самые трудные слова:

>>> pprint(results[-10:])
[(12, 16, 'buzzer', 'eraoiutlnsmdbcfg'),
 (12, 16, 'cuffer', 'eraoiutlnsmdbpgc'),
 (12, 16, 'jugger', 'eraoiutlnsmdbpgh'),
 (12, 16, 'pugger', 'eraoiutlnsmdbpcf'),
 (12, 16, 'suddle', 'eaioulbrdcfghmnp'),
 (12, 16, 'yucker', 'eraoiutlnsmdbpgc'),
 (12, 16, 'zipper', 'eraoinltsdgcbpjk'),
 (12, 17, 'tuzzle', 'eaioulbrdcgszmnpt'),
 (13, 16, 'wuzzer', 'eraoiutlnsmdbpgc'),
 (13, 17, 'wuzzle', 'eaioulbrdcgszmnpt')]

Причина в том, что это сложно, потому что после того, как вы догадались -UZZLE, у вас все еще осталось семь возможностей:

>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle')))
'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'

6. Выбор словарного списка

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

Например, среди 1700 шестибуквенных слов в 10 000 наиболее распространенных слов в Project Gutenberg по состоянию на 2006 год, самая сложная из десяти следующие:

[(6, 10, 'losing', 'eaoignvwch'),
 (6, 10, 'monkey', 'erdstaoync'),
 (6, 10, 'pulled', 'erdaioupfh'),
 (6, 10, 'slaves', 'erdsacthkl'),
 (6, 10, 'supper', 'eriaoubsfm'),
 (6, 11, 'hunter', 'eriaoubshng'),
 (6, 11, 'nought', 'eaoiustghbf'),
 (6, 11, 'wounds', 'eaoiusdnhpr'),
 (6, 11, 'wright', 'eaoithglrbf'),
 (7, 10, 'soames', 'erdsacthkl')]

(Сомс Форсайт - символ в Форсайт Сага Джона Голсуорти, список слов был преобразован в нижний регистр, так что это не было" возможно, чтобы я быстро удалил собственные имена.)

Ответ 2

Очень простой способ - вычислить оценку, основанную на отсутствии гласных в слове, количестве уникальных букв и общности каждой буквы:

letters = 'etaoinshrdlcumwfgypbvkjxqz'
vowels = set('aeiou')

def difficulty(word):
    unique = set(word)
    positions = sum(letters.index(c) for c in word)

    return len(word) * len(unique) * (7 - len(unique & vowels)) * positions

words = ['the', 'potato', 'school', 'egypt', 'floccinaucinihilipilification']

for word in words:
    print difficulty(word), word

И вывод:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Затем вы можете забить слова:

        score < 2000   # Easy
 2000 < score < 10000  # Medium
10000 < score          # Hard

Ответ 3

Вы можете использовать метод Монте-Карло, чтобы оценить сложность слова:

• Имитировать игру, угадывая случайную букву каждый раз, взвешенный по частоте письма на вашем целевом языке, и подсчитывайте, сколько догадок потребовало, чтобы ваш рандомизированный игрок пришел к решению. Обратите внимание: поскольку каждая догадка исключает букву, этот процесс конечен и возвращает число от 1 до 26 включительно.
• Повторите этот процесс 2*N раз, где N - количество уникальных букв в вашем слове,
• Вычислить оценку путем усреднения результатов 2*N run,
• Определите уровень сложности: баллы менее десяти указывают на легкое слово, а оценки выше шестнадцати указывают на трудное слово; все остальное является средним.

Ответ 4

Предыдущая аналогичная дискуссия по той же теме: Определите сложность английского слова

Мне нравится ответ в конце ссылки ^. Для игры в детский палач просто применяйте подход, подобный scrabble.

Назначьте значение точки каждой букве, затем просто добавьте буквы.

Ответ 5

Просто сделай это! Играйте в палатку против слова. Подсчитайте, сколько неудобств (т.е. Неправильных догадок) требуется, чтобы победить.

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

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

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

Ответ 6

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

Алгоритм не так прост, как это, так как часто имеется несколько букв, каждое из которых имеет одинаковое количество слов в словаре. В этом случае выбор буквы может существенно повлиять на то, сколько догадок требуется для слова. Мы выбираем максимумы, в которых полученная информация о размещении этой буквы (если это действительно слово) дает максимальную информацию о системе (буква с максимальным информационная энтропия). например если два оставшихся возможных слова являются "энциклопедией" и "энциклопедией", то буква "c" имеет ту же вероятность появления как e, n, y, l, o, p, e, d, я (т.е. гарантируется быть в слове), но мы должны сначала спросить о "c", так как он имеет ненулевую информационную энтропию.

Источник (С++, GPL) здесь

Результатом всего этого является список слов с количеством догадок, необходимых для каждого из них: difficulty.txt (630KB). Самое сложное слово для этого алгоритма - "воля" (с 14 неудачными догадками); я и double l догадаются довольно быстро, но тогда варианты включают в себя счет, укроп, заполнение, жабер, холм, убить, мельницу, таблетку, рилл, до, воля, и с этого момента единственным вариантом является угадать каждую букву в очередь. Несколько противоречиво, более длинные слова гораздо догадываются гораздо быстрее (их просто нет на выбор).

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

Ответ 7

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

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

Ответ 8

Вы получаете downvoted, потому что вы просите нас построить для вас очень сложный алгоритм.

Почему бы вам просто не создать три массива (простые, средние и жесткие) и заполнить каждый сотнями слов? Это займет около 20 минут.

Я обещаю, что вашим детям будет скучно вешать человека задолго до того, как они сгорят несколько сотен игр...: D

Ответ 9

Ну, возможно, может быть много чего:

• Как говорили все, частота отдельных букв;
• Длина слова определенно должна рассчитываться, но не линейно - длинное слово может сделать случайные догадки, попадающие в буквы, в то время как короткий может быть трудно получить;
• Кроме того, следует учитывать сами слова - "двупартийный" может быть словом для людей на SO, но, возможно, не для нетехнического населения.

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

Ответ 10

Начните с списка слов и запустите поиск Google для каждого. Пусть число хитов служит (грубым) прокси термина сложности.

В уточненной версии вы должны группировать слова по синониму "Отношение" на основе тезауруса и определять самое сложное слово категории, подсчитывая результаты поиска Google.

Взятие понятия n-граммов Еще один шаг, трудность Слова может быть оценена по частоте его слогов в прозе. Разумеется, зависит от качества статистики слога. Вам, вероятно, придется различать слова Lexemes и Function (определители, союзы и т.д.) И нормализовать по количеству слогов в Word (это похоже на Overkill as я Write...).

Ответ 11

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

Ответ 12

Вычислить значение каждой буквы слова в точках Scrabble: E = 1, D = 2, V = 4, X = 8 и т.д. Добавьте их и разделите на число букв, чтобы получить среднее значение букв, и используйте это, чтобы забить слово. Вычислить среднее значение для каждого слова в большом словаре и определить точки останова между квартилями. Вызовите слова в нижнем квартиле "легкие", слова в двух средних квартилях "средний", а слова в самом высоком квартиле "трудны".