pronunciation - types of algorithms




Algoritmo para classificar palavras para os níveis de dificuldade do carrasco como “Fácil”, “Médio” ou “Difícil” (8)

O que é um bom algoritmo para determinar a "dificuldade" de uma palavra para um jogo de carrasco, para que o jogo possa selecionar palavras para corresponder a um nível de dificuldade especificado?

A dificuldade parece estar relacionada ao número de tentativas necessárias, a frequência relativa de uso de letras (por exemplo, palavras com muitas letras incomuns pode ser mais difícil de adivinhar) e, potencialmente, o comprimento da palavra.

Existem também alguns fatores subjetivos para (tentar) compensar, como a probabilidade de que uma palavra esteja no vocabulário do jogador, e que possa ser reconhecida, permitindo passar de uma estratégia de adivinhação baseada apenas em freqüências de letras para adivinhar com base na lista de palavras de correspondência conhecidas.

Minha tentativa por enquanto está abaixo em rubi. Alguma sugestão sobre como melhorar a categorização?

def classify_word(w)
  n = w.chars.to_a.uniq.length # Num. unique chars in w
  if n < 5 and w.length > 4
    return WordDifficulty::Easy
  end
  if n > w.length / 2
    return WordDifficulty::Hard
  else
    return WordDifficulty::Medium
  end
end

Estou escrevendo um jogo de forca que gostaria que meus filhos jogassem; Eu estou um pouco velho demais para tentar "lição de casa", o que pode ser o motivo pelo qual a pergunta está recebendo tantos votos para baixo ... Palavras são tiradas aleatoriamente de grandes bancos de dados de palavras, que incluem muitas palavras obscuras e estão sendo filtradas pelo nível de dificuldade determinado para a palavra.


1. Introdução

Aqui está uma maneira de abordar esse problema sistematicamente: se você tem um algoritmo que desempenha bem a forca, então você pode considerar a dificuldade de cada palavra como o número de suposições erradas que seu programa levaria se adivinhando essa palavra.

2. Além da estratégia do carrasco

Há uma ideia que está implícita em algumas das outras respostas e comentários, de que a estratégia ideal para o solucionador seria basear suas decisões na frequência das letras em inglês ou na frequência das palavras em algum corpus. Esta é uma ideia sedutora, mas não está bem. O solucionador faz o melhor se modela com precisão a distribuição das palavras escolhidas pelo setter , e um setter humano pode muito bem estar escolhendo palavras com base em sua raridade ou evitando letras usadas com frequência. Por exemplo, embora E seja a letra mais usada em inglês, se o pesquisador escolher sempre entre as palavras JUGFUL , RHYTHM , SYZYGY e ZYTHUM , então um solver perfeito não começa adivinhando E !

A melhor abordagem para modelar o setter depende do contexto, mas eu acho que algum tipo de inferência indutiva Bayesiana funcionaria bem em um contexto onde o solver jogaria muitos jogos contra o mesmo setter, ou contra um grupo de setters similares.

3. Algoritmo Hangman

Aqui vou esboçar um solucionador que é muito bom (mas longe de ser perfeito). Modela o setter como escolhendo palavras uniformemente de um dicionário fixo. É um algoritmo guloso : em cada estágio adivinha a letra que minimiza o número de erros, ou seja, palavras que não contêm o palpite. Por exemplo, se nenhum palpite foi feito até agora, e as possíveis palavras são DEED , DEAD e DARE , então:

  • se você acha que D ou E , não há erros;
  • se você adivinha A , há uma falta ( DEED );
  • se você acha que R , há duas falhas ( DEED e DEAD );
  • se você adivinha qualquer outra letra, há três erros.

Então, D ou E é um bom palpite nessa situação.

(Agradecimentos ao Coronel Panic em comentários por apontar que palpites corretos são gratuitos em carrasco - eu esqueci completamente isso em minha primeira tentativa!)

4. Implementação

Aqui está uma implementação desse algoritmo em 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. Exemplo de resultados

Usando essa estratégia, é possível avaliar a dificuldade de adivinhar cada palavra em uma coleção. Aqui eu considero as palavras de seis letras no dicionário do meu sistema:

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

As palavras mais fáceis de adivinhar neste dicionário (juntamente com a sequência de estimativas necessárias para o solucionador adivinhá-las) são as seguintes:

>>> 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')]

e as palavras mais difíceis são estas:

>>> 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')]

A razão que estes são difíceis é porque depois que você adivinhou -UZZLE , você ainda tem sete possibilidades:

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

6. Escolha da lista de palavras

É claro que ao preparar listas de palavras para seus filhos que você não iniciaria com o dicionário do sistema do seu computador, você começaria com uma lista de palavras que você acha que provavelmente conheceriam. Por exemplo, você pode dar uma olhada nas listas do Wikcionário das palavras mais usadas em vários corpora em inglês.

Por exemplo, entre as 1.700 palavras de seis letras nas 10.000 palavras mais comuns no Project Gutenberg até 2006 , as dez mais difíceis são as seguintes:

[(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')]

(Soames Forsyte é um personagem da Forsyte Saga de John Galsworthy ; a lista de palavras foi convertida para minúsculas, por isso não foi possível remover rapidamente nomes próprios.)


Apenas faça! Jogue carrasco contra a palavra. Conte quantas desistências (ou seja, palpites incorretos) é preciso para vencer.

Você precisará de uma estratégia para jogar. Aqui está uma estratégia humana (ish). Do dicionário, risque todas as palavras que não se encaixam nas revelações até agora. Adivinha a letra mais frequente entre as palavras restantes.

Se sua estratégia for aleatória, você pode definir sua medida como o número esperado de perdidos e estimar isso empiricamente.

Outra estratégia determinista, de um bot hangman que escrevi há alguns anos atrás. Acho que a letra que minimiza o número de palavras restantes no caso do palpite é incorreta (ou seja, otimizar o pior caso). Hoje eu não gosto dessa estratégia por ser mecânica demais, prefiro a acima.


Calcule o valor de cada letra de uma palavra em pontos de Scrabble: E = 1, D = 2, V = 4, X = 8 e assim por diante. Some-os e divida pelo número de letras para obter um valor médio de letras e use-o para pontuar a palavra. Calcule a média de cada palavra em um dicionário grande e determine os pontos de quebra entre os quartis. Chame palavras no quartil mais baixo "fácil", palavras nos dois quartis médios "médio" e palavras no quartil mais alto "duro".


Comece com uma lista de palavras e inicie uma pesquisa no google para cada um. Deixe o número de hits servir como um proxy (grosseiro) da dificuldade do termo.

Em uma versão refinada, você agruparia as palavras por um sinônimo Relation Based em um Thesaurus e determinaria a palavra mais difícil de uma categoria, contando os resultados das pesquisas do Google.

Tomando a noção de n-Gramas Um passo adiante, a dificuldade de uma palavra poderia ser avaliada pela freqüência de suas sílabas em prosa. Depende da qualidade das estatísticas de sílabas, é claro. Você provavelmente teria que diferenciar entre lexemes e palavras de função (determinantes, conjunções etc.) e normalizar pelo número de sílabas no Word (parece exagero como eu escrevo ...).


Eu gosto da ideia de construir um algoritmo que aprenda e mude dependendo dos usuários. No início, você pode implementar qualquer um dos algoritmos sugeridos para criar a lista, então, à medida que mais pessoas jogarem, você atribui um peso a cada uma das palavras, dependendo do número de tentativas (que também é continuamente rastreado e calculado). ). Isso evita a emissão de palavras complexas, mas populares, com avaliações difíceis, mas são bem conhecidas das pessoas.


Primeiro, claro, você geraria uma lista de cartas únicas. Em seguida, classifique por frequência (em inglês ou em qualquer outro idioma - há listas para isso ), com letras menos frequentes com maior dificuldade.

Então você precisa decidir se combina as pontuações adicionando, multiplicando ou usando algum outro esquema.


Uma maneira realmente simples seria calcular uma pontuação com base na falta de vogais na palavra, no número de letras únicas e no caráter comum de cada letra:

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

E a saída:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Você poderia então marcar as palavras com:

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

Você está recebendo downvoted porque você está nos pedindo para construir um algoritmo muito complexo para você.

Por que você não cria apenas três matrizes (fácil, médio e difícil) e preenche cada uma com cem ou mais palavras? Isso levaria cerca de 20 minutos.

Eu prometo aos seus filhos que ficarão entediados de enforcar o homem muito antes de queimarem algumas centenas de jogos ...: D