Você precisa escrever um solucionador de forca. Testando contra esta lista de palavras em inglês [1] , vence o solucionador que resolve o maior número de palavras, com o número total de palpites incorretos sendo o desempate. Todas as palavras da lista de palavras serão testadas em ordem aleatória.
[1]: esta lista de palavras é retirada daqui , os números são removidos, as palavras com comprimento 1 ou com caracteres não alfabéticos são removidas e as 4096 palavras únicas mais frequentes são escolhidas como esta lista de palavras.
Os detalhes:
Seu programa irá interagir com o programa do jogo, que fornecerá a você os caracteres sublinhados e as letras adivinhadas corretamente. Seu programa dará a entender seus palpites e deve inferir a partir da entrada se o palpite anterior estava certo ou errado. Depois de estar errado por 6 vezes, seu programa perde. Seu programa deve estar pronto para o próximo jogo após o término de cada jogo (após vitória ou derrota).
O tamanho do seu código deve ser estritamente menor que 2048 bytes, e seu programa não deve usar recursos externos (incluindo, entre outros, o acesso à lista de palavras no armazenamento local ou na Internet).
Exemplo : (a entrada é precedida por >aqui apenas para esclarecimento - ela não está realmente presente na entrada)
>_______ // 7 underscores
a // Now you wait for input again
>_a___a_
e
>_a___a_ // Implies that your guess is wrong
>_____ // new round, this will be given ONLY IF you already have 6 losses
Suponha que você esteja errado por 6 vezes, você receberá uma entrada final, o que implica que seu palpite está errado, e seu programa deve estar pronto para iniciar uma nova rodada (por exemplo, faça outra entrada).
Se você ganhar,
>_angman
h
>hangman
>_____ // new round
Depois de saber que você ganhou (porque a entrada não possui sublinhados), você deve estar pronto para aceitar a próxima rodada.
Seu programa deve terminar quando receber uma entrada END.
Se o seu programa não for determinístico (depende de aleatoriedade, pseudo-aleatoriedade, hora do sistema, temperatura ambiente, meu humor etc.), você deve declarar explicitamente isso na sua inscrição e sua pontuação será obtida 10 vezes (por mim, a menos que seja instruído de outra forma) e média.
Nota : se você usa idiomas como python, libere explicitamente seu stdout após cada declaração de impressão.
O programa do jogo é o seguinte (crédito para nneonneo ):
import sys, random, subprocess
proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
def p(x):
proc.stdin.write(x+'\n')
proc.stdin.flush()
wordlist=[]
f=open('wordlist.txt', 'r')
for i in f:
wordlist.append(i[:-1] if i[-1]=='\n' else i)
# wordlist=[i[:-1] for i in f]
random.shuffle(wordlist)
score=0
totalerr=0
for s in wordlist:
s2=[]
for i in s:
s2.append('_')
err=0
p(''.join(s2))
while err<6 and '_' in s2:
c=proc.stdout.readline().strip()
nomatch=True
for i in range(0, len(s)):
if s[i]==c:
s2[i]=c
nomatch=False
if nomatch:
err+=1
totalerr+=1
p(''.join(s2))
if err<6:
score+=1
p('END')
sys.stderr.write('score is '+str(score)+', totalerr is '+str(totalerr)+'\n')Uso: python ./game.py [yoursolverprogram]
Exemplo: python ./game.py ruby ./solver.rb
Isso deve funcionar como o antigo programa de pontuação, mas não depende de pipes nomeados, para que possa funcionar em outras plataformas. Consulte o histórico de revisões se você estiver interessado no antigo.
fonte
subprocessde um fifo externo para dirigir o jogo? Dessa forma, o código funcionará para outros sistemas operacionais (por exemplo, Cygwin no Windows). Aqui estágame.pymodificado para usarsubprocesspara iniciar o programa nomeado na linha de comando: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Use-o comopython game.py <program> [args], por exemplopython game.py python hangman.py.Respostas:
Python 2, pontuação = 2111
Corra com
python -u. (Para testar com o controlador fornecidopython ./game.py python -u ./solver.py.) São 2044 bytes de código + 1 para-u= 2045 bytes.Resultado
Como funciona
O programa substitui todos os
_s por1s no estado atual, trata o resultado como um número inteiro de base 36 e aceita o módulo 1879, fornecendo uma função de hash bruto. Ele escolhe uma letra para adivinhar, indexando esse valor de hash na longa sequência de letras. Se ele já adivinhou essa letra antes, diminui o módulo em 6 (portanto, sempre permanece relativamente primo para 36) e escolhe uma letra diferente, repetindo até encontrar uma carta que ainda não havia adivinhado.Eu projetei essa estratégia para ter muitas variáveis ajustáveis (as letras individuais da cadeia longa), a maioria das quais afetará independentemente a pontuação final em uma pequena quantidade. Isso o torna adequado para a otimização do estilo de escalada - usei a Diversified Late Acceptance Search .
Python 2, pontuação = 2854
Com o uso liberal de bytes não imprimíveis e compactação incorporada, podemos extrair muito mais informações.
Decodifique com
xxd -re execute compython -u. (Para testar com o controlador fornecidopython ./game.py python -u ./solver.py.) São 2047 bytes de código + 1 para-u= 2048 bytes.Resultado
fonte
Python: 2006 bytes, pontuação = 1501
1885 bytes, pontuação = 13371961 bytes, pontuação = 1207Aqui está o meu envio:
Resultado da pontuação:
Este programa é totalmente determinístico. O blob gigante (que é um pedaço de
zlibdados compactados com base em 64 bits ) é uma lista de árvores de decisão (uma árvore por comprimento de palavra). Cada árvore de decisão codifica uma árvore binária completa com uma profundidade entre 2 e 5. Cada nó interno é um único caractere, e a decisão prossegue com base no fato de o caracter estar presente ou não na palavra da forca.Cada nó folha da árvore binária contém uma tabela de frequência otimizada específica para esse ramo da pesquisa em árvore. A tabela é otimizada especificamente para favorecer a conclusão de determinadas palavras, ignorando completamente outras (que não podem ser alcançadas devido ao orçamento limitado de "falha"). A tabela não é otimizada para minimizar erros e, portanto, a contagem total de erros do programa é alta, apesar de sua pontuação (relativamente) boa.
O otimizador, que não é mostrado, usa um otimizador não linear não determinístico, utilizando uma estratégia de descida aleatória em gradiente para produzir as tabelas de frequência.
fonte
range(4)pode ser substituído por,[1]*4desde que você não precise realmente usar o valor dei.decode('zip')vez dedecode('zlib')Rubi
Um envio conjunto do usuário PragTob e de mim.
Resultado:
Isso tem 1672 caracteres e ainda não é um jogo de golfe, por isso temos amplo espaço para aprimoramentos algorítmicos.
Primeiro, armazenamos um hash de frequências de caracteres (calculado a partir da lista de palavras) agrupados por tamanho de palavra.
Em cada rodada, simplesmente classificamos todos os caracteres pelas frequências para o comprimento atual e os experimentamos do mais comum ao menos comum. Usando essa abordagem, obviamente falhamos em todas as palavras que possuem apenas um caractere médio comum.
fonte
score is 625, totalerr is 23196ainda up-to-date com o seu algoritmo atualizado? Eu tentei um semelhante e eu tenho apenas 300 no máximo.Atualizar Usando um método semelhante ao @nneonneo, chego a esse código, exatamente 2047 caracteres .
Ponto:
Código:
Entrada antiga
Resultado:
Não é uma média, pois esse algoritmo é determinístico, ou seja, sempre fornece a mesma pontuação para qualquer lista de palavras embaralhadas.
Aqui está minha entrada no Python 2.7; golfe (717 caracteres)
Isso usa uma idéia semelhante à @ m.buettner, armazenando uma lista ordenada de letras após a qual as suposições serão feitas. Mas, isso não usa dados de frequência diretamente, apenas tenta quase todas as permutações de letras possíveis e simula o jogo e, finalmente, obtém a permutação que dá a melhor pontuação.
Esta versão é otimizada usando as 9 primeiras letras, portanto, para palavras de 2 e 3 letras, a permutação já é a ideal, na classe do algoritmo em que as informações da entrada anterior são ignoradas. No momento, ainda estou executando o código das 10 melhores letras, otimizando as palavras de 4 letras (e também encontrando uma solução melhor para palavras mais longas).
entrada inválida
Para meus benchmarking, aqui está o código que usa a árvore de decisão completa, 11092 caracteres.
Ponto:
Código:
fonte
Perl, 1461 bytes, pontuação = 1412, totalerr = 21050
(Observe que são 1461 bytes depois de remover um pouco do espaço em branco opcional. Conforme impresso, é cem ou mais pesado, mas ainda bem abaixo de 2000.)
Tentei várias abordagens mais "sutis", mas essa acabou superando todas elas. As duas cadeias de dados são simplesmente listas de classificação dos caracteres com maior probabilidade de seguir cada caractere e os caracteres com maior probabilidade de preceder cada caractere (com os dígitos que não ocorrem na lista de palavras não estão representados).
<e>são usados para representar o início e o fim da palavra. Como exemplo,"w[aiehonrlsdtkfy]"significa que "wa" é mais comum que "wi" é mais comum que "nós" etc.%d, o mapeamento direto inclui uma classificação global, armazenada como$d{''}. É usado para lugares onde existem duas incógnitas seguidas ou onde todos os dígitos na lista de palavras estão esgotados (portanto, devemos lidar com uma palavra que não seja da lista de palavras).Para cada posição desconhecida na palavra, ele examina o caractere anterior, atribui uma pontuação a cada caractere possível, começando em 180 para o melhor classificado e diminuindo para 80 no final da lista; então o mesmo é feito para o seguinte caractere. Todas as pontuações de todos os personagens são somadas e a que tiver a maior pontuação é selecionada.
Depois que uma letra é adivinhada, ela é removida diretamente das tabelas de classificação, para que não possa ser adivinhada novamente (até que iniciemos uma nova palavra e reinicialize as tabelas).
Atualização: ganhou vários pontos corrigindo um erro (não removíamos as letras da tabela reversa) e alterando a maneira como os pontos caem à medida que descemos na lista.
fonte
Python: 2046 bytes, score = 1365
pontuação é 1365, totalerr é 21343
Grande parte do código empresta da submissão python do nneonneo (sem a qual eu não teria isso abaixo do limite de 2048 bytes). Originalmente, achei que isso deveria ter cerca de 200 a mais, mas descobri um erro na minha ferramenta de criação de cadeias de dados. Agora que está corrigido, minha pontuação é 1365 muito mais razoável.
Em vez de criar árvores binárias com base no comprimento, criei uma única árvore binária para armazenar as informações de frequência. A árvore não tem profundidade uniforme, pois não adianta armazenar informações de frequência para algo mais profundo do que seis palpites incorretos (mas, em teoria, os palpites corretos poderiam ter doze profundidade para "consideravelmente" e "desconfortável"). Essa árvore de formato desajeitado é navegada pelo código fatorial (na verdade, usando a função de combinação ). Para tornar a sequência de dados mais compressível, preenchi todos os índices não utilizados com 's'.
Usei um script para calcular boas seqüências de caracteres para armazenar como d, e se alguém puder jogar mais alguns caracteres no restante do script, aqui estão algumas substituições que devem resultar em melhores pontuações. A linha superior é a string codificada no programa acima.
O script que eu usei para gerar as seqüências de dados está aqui , caso seja útil para qualquer pessoa!
fonte
distinct, a saída do seu programa era, em ordemeitanogsuc, o que significa que de alguma forma deixa de fornecer saída, mesmo que apenas adivinhe incorretamente por 5 vezes.A linguagem de programação D é minha ferramenta de escolha para este desafio.
A poucos metros do limite de 2.048 bytes, embora em algumas partes seja um pouco de golfe para diminuir a contagem de bytes, todo o trabalho pesado permanece perfeitamente legível. Esse solucionador não é muito bom em seu trabalho, e espero que seja derrotado facilmente, mas isso é apenas para fazer a bola rolar. Comece as coisas, por assim dizer.
EDIT # 1 :
Como foi apontado, o código original é propenso a sofrer uma morte horrível quando esgota todas as vogais. Como ele não funciona corretamente, substituí-lo por uma abordagem um pouco mais brutal à adivinhação aleatória.EDIT # 2 : o código original foi corrigido e agora permanece.
Pontuação :
25.7; totalerr: 24,529.9 (average of 10 tests).Como funciona
Este solucionador é completamente aleatório. Até a aleatoriedade é aleatória, momentos divertidos!
Quando o programa recebe entrada, ele adivinha um caractere aleatório que ainda não adivinhou e o envia para STDOUT.
O algoritmo de adivinhação funciona assim:
fonte
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Eu consegui consertar issocast(int). Após 10 execuções, sua pontuação média é de 22,4 palavras, com 24529,1 palpites incorretos. I vai voltar a testar se você fixar a versão mais avançada :) divertimento têmSolução JAVASCRIPT + HTML
fonte