Vous devez écrire un solveur du pendu. En testant cette liste de mots anglais [1] , le solveur qui résout le plus grand nombre de mots gagne, le nombre total de suppositions incorrectes étant le bris d'égalité. Tous les mots de la liste de mots seront testés dans un ordre aléatoire.
[1]: Cette liste de mots est extraite d' ici , puis les nombres sont supprimés, puis les mots de longueur 1 ou avec des caractères non alphabétiques sont supprimés, puis les 4096 mots uniques les plus fréquents sont choisis comme cette liste de mots.
Les détails:
Votre programme interagira avec le programme de jeu, qui vous donnera à travers stdin les caractères de soulignement et les lettres correctement devinées. Votre programme vous donnera une idée de vos suppositions, et il doit déduire de l'entrée si la supposition précédente était bonne ou mauvaise. Après s'être trompé 6 fois, votre programme perd. Votre programme doit être prêt pour le prochain match après la fin de chaque match (après une victoire ou une perte).
La longueur de votre code doit être strictement inférieure à 2048 octets et votre programme ne doit utiliser aucune ressource externe (y compris, mais sans s'y limiter, l'accès à la liste de mots sur le stockage local ou à partir d'Internet).
Exemple : (L'entrée est précédée >ici uniquement à des fins de clarification - elle n'est pas réellement présente dans l'entrée)
>_______ // 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
Supposons que vous vous trompiez 6 fois, vous recevrez une entrée finale qui implique que votre supposition est fausse, et votre programme doit être prêt à commencer un nouveau cycle (c'est-à-dire prendre une autre entrée).
Si tu gagnes,
>_angman
h
>hangman
>_____ // new round
Après avoir su que vous avez gagné (parce que l'entrée n'a pas de soulignement), vous devez être prêt à accepter le tour suivant.
Votre programme doit se terminer lorsqu'il reçoit une entrée END.
Si votre programme n'est pas déterministe (dépend de l'aléatoire, de la pseudo-aléatoire, de l'heure du système, de la température ambiante, de mon humeur, etc.), vous devez déclarer explicitement que dans votre soumission, et votre score sera pris 10 fois (par moi, sauf instruction contraire) et moyenne.
Remarque : si vous utilisez des langages comme python, veuillez vider explicitement votre stdout après chaque instruction print.
Le programme du jeu est le suivant (crédit à 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')
Usage: python ./game.py [yoursolverprogram]
Exemple: python ./game.py ruby ./solver.rb
Cela devrait fonctionner comme l'ancien programme de notation, mais ne dépend pas des canaux nommés, il peut donc fonctionner sur d'autres plates-formes. Reportez-vous à l'historique des révisions si vous êtes intéressé par l'ancien.
la source
subprocessau lieu d'une fifo externe pour piloter le jeu? De cette façon, le code fonctionnera pour d'autres systèmes d'exploitation (par exemple, Cygwin sous Windows). Voici unegame.pymodification à utilisersubprocesspour démarrer le programme nommé sur la ligne de commande: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Utilisez-le commepython game.py <program> [args], par exemplepython game.py python hangman.py.Réponses:
Python 2, score = 2111
Courez avec
python -u. (Pour les tests avec le contrôleur donné,.python ./game.py python -u ./solver.py) Il s'agit de 2044 octets de code + 1 pour-u= 2045 octets.Résultat
Comment ça marche
Le programme remplace tous les
_s par1s dans l'état actuel, traite le résultat comme un entier en base 36 et le prend modulo 1879, nous donnant une fonction de hachage brute. Il choisit une lettre à deviner en indexant cette valeur de hachage dans la longue chaîne de lettres. S'il a déjà deviné cette lettre auparavant, il diminue le module de 6 (il reste donc toujours premier à 36) et choisit une lettre différente, répétant jusqu'à ce qu'il trouve une lettre qu'il n'a pas encore devinée.J'ai conçu cette stratégie pour avoir de nombreuses variables ajustables (les lettres individuelles de la longue chaîne), dont la plupart affecteront indépendamment le score final d'une petite quantité. Cela le rend bien adapté à l'optimisation de style d'escalade - j'ai utilisé la recherche d'acceptation tardive diversifiée .
Python 2, score = 2854
Avec l'utilisation généreuse d'octets non imprimables et la compression intégrée, nous pouvons insérer beaucoup plus d'informations.
Décodez avec
xxd -ret exécutez avecpython -u. (Pour les tests avec le contrôleur donné,.python ./game.py python -u ./solver.py) Il s'agit de 2047 octets de code + 1 pour-u= 2048 octets.Résultat
la source
Python: 2006 octets, score = 1501
1885 octets, score = 13371961 octets, score = 1207Voici ma soumission:
Sortie de score:
Ce programme est entièrement déterministe. Le blob géant (qui est un bloc de
zlibdonnées compressées codé en base 64 ) est une liste d'arbres de décision (un arbre par longueur de mot). Chaque arbre de décision code un arbre binaire complet avec une profondeur entre 2 et 5. Chaque nœud interne est un caractère unique, et la décision se déroule selon que le caractère est présent ou non dans le mot bourreau.Chaque nœud feuille de l'arbre binaire contient une table de fréquences optimisée spécifique à cette branche de la recherche d'arbre. Le tableau est spécifiquement optimisé pour favoriser l'achèvement de certains mots, tout en ignorant complètement les autres (qu'il ne peut pas atteindre en raison du budget limité "d'échec"). Le tableau n'est pas optimisé pour minimiser les erreurs, et donc le nombre total d'erreurs du programme est élevé malgré son score (relativement) bon.
L'optimiseur, qui n'est pas illustré, utilise un optimiseur non linéaire non déterministe utilisant une stratégie de descente de gradient aléatoire pour produire les tables de fréquences.
la source
range(4)jouer au golf, il peut être remplacé par à[1]*4condition que vous n'ayez pas réellement besoin d'utiliser la valeur dei.decode('zip')au lieu dedecode('zlib')Rubis
Une soumission conjointe de l'utilisateur PragTob et de moi-même.
Résultat:
Cela a 1672 caractères et n'est pas encore joué, nous avons donc amplement de place pour l'amélioration algorithmique.
D'abord, nous stockons un hachage de fréquences de caractères (calculées à partir de la liste de mots) regroupées par longueur de mot.
Ensuite, à chaque tour, nous trions simplement tous les caractères selon les fréquences pour la longueur actuelle et les essayons du plus commun au moins commun. En utilisant cette approche, nous échouons évidemment à chaque mot qui n'a même qu'un caractère commun moyen.
la source
score is 625, totalerr is 23196toujours à jour avec votre algorithme mis à jour? J'en ai essayé un similaire et je n'en ai obtenu qu'un maximum de 300.Mise à jour En utilisant une méthode similaire à @nneonneo, j'arrive à ce code, exactement 2047 caractères .
But:
Code:
Ancienne entrée
Résultat:
Ce n'est pas une moyenne car cet algorithme est déterministe, c'est-à-dire qu'il donne toujours le même score pour toute liste de mots mélangés.
Voici mon entrée en Python 2.7; golfé (717 caractères)
Cela utilise une idée similaire à @ m.buettner, stockant une liste ordonnée de lettres à la suite de laquelle les suppositions seront faites. Mais, cela n'utilise pas directement les données de fréquence, il essaie simplement presque toutes les permutations de lettres possibles et simule le jeu, et finalement prend la permutation qui donne le meilleur score.
Cette version est optimisée en utilisant les 9 premières lettres, donc pour les mots à 2 et 3 lettres, la permutation est déjà optimale, dans la classe d'algorithme où les informations de l'entrée précédente sont ignorées. J'exécute actuellement le code pour les 10 premières lettres, optimisant les mots de 4 lettres (et trouvant également une meilleure solution pour les mots plus longs).
entrée invalide
Pour mon analyse comparative, voici le code qui utilise l'arbre de décision complet, 11092 caractères.
But:
Code:
la source
Perl, 1461 octets, score = 1412, totalerr = 21050
(Remarque, il fait 1461 octets après avoir supprimé pas mal d'espaces blancs en option. Comme imprimé, il est environ cent plus lourd, mais toujours bien en dessous de 2000.)
J'ai essayé un tas d'approches plus "subtiles", mais celle-ci a fini par les battre toutes. Les deux chaînes de données sont simplement des listes classées des caractères les plus susceptibles de suivre chaque caractère et les caractères les plus susceptibles de précéder chaque caractère (avec des digraphes qui n'apparaissent pas dans la liste de mots non représentés du tout).
<et>sont utilisés pour représenter le début et la fin du mot. À titre d'exemple,"w[aiehonrlsdtkfy]"signifie que « wa » est plus commun que « wi » est plus fréquente que « nous » , etc.%d, la mise en correspondance vers l' avant, comprend un classement mondial, stocké sous forme$d{''}. Il est utilisé pour les endroits où il y a deux inconnues d'affilée, ou où tous les digraphes de la liste de mots sont épuisés (nous devons donc avoir affaire à un mot autre que la liste de mots).Pour chaque position inconnue dans le mot, il examine le caractère précédent, attribue à chaque caractère suivant possible un score, commençant à 180 pour le premier, et diminuant à 80 à la fin de la liste; alors la même chose se fait pour le personnage suivant. Tous les scores de tous les personnages sont additionnés et celui avec le score le plus élevé est sélectionné.
Une fois qu'une lettre est devinée, elle est supprimée directement des tableaux de classement, de sorte qu'elle ne peut pas être devinée à nouveau (jusqu'à ce que nous commencions un nouveau mot et réinitialisions les tableaux).
Mise à jour: gagné un tas de points en corrigeant un bug (nous ne supprimions pas les lettres du tableau inversé) et en changeant la façon dont les points tombent au fur et à mesure que nous descendons dans la liste.
la source
Python: 2046 octets, score = 1365
le score est de 1365, le total est de 21343
Une grande partie du code emprunte à la soumission de python de nneonneo (sans laquelle je n'aurais pas eu cela sous la limite de 2048 octets). À l'origine, je pensais que cela devrait marquer environ 200 de plus, mais j'ai découvert une erreur dans mon outil de création de chaîne de données. Maintenant que c'est fixé, mon score est un 1365 beaucoup plus raisonnable.
Plutôt que de créer des arbres binaires en fonction de la longueur, j'ai créé un seul arbre binaire pour contenir les informations de fréquence. L'arbre n'est pas de profondeur uniforme, car il est inutile de stocker des informations de fréquence pour quelque chose de plus profond que six suppositions incorrectes (mais les suppositions correctes pourraient en théorie être de douze profond pour "considérablement" et "inconfortable"). Cet arbre aux formes maladroites est parcouru par le code factoriel (utilisant en fait la fonction de combinaison ). Afin de rendre la chaîne de données plus compressible, j'ai rempli tous les index inutilisés avec 's'.
J'ai utilisé un script pour calculer les bonnes chaînes à stocker en tant que d, et si quelqu'un peut jouer au golf quelques caractères supplémentaires du reste du script, alors voici quelques remplacements qui devraient entraîner de meilleurs scores. La ligne du haut est la chaîne encodée dans le programme ci-dessus.
Le script que j'ai utilisé pour générer les chaînes de données est ici , au cas où il serait utile à n'importe qui!
la source
distinct, la sortie de votre programme était, dans l'ordreeitanogsuc, ce qui signifie qu'il arrête en quelque sorte de donner la sortie même s'il ne devine que 5 fois de manière incorrecte.Le langage de programmation D est mon outil de choix pour ce défi.
Juste en deçà de la limite de 2 048 octets, bien qu'il soit légèrement joué au golf dans certaines parties pour obtenir le décompte des octets, tous les efforts lourds restent parfaitement lisibles. Ce solveur n'est pas très bon dans son travail, et je m'attends à ce qu'il soit facilement battu, mais c'est juste pour faire rouler la balle. Coup d'envoi, pour ainsi dire.
EDIT # 1 :
Comme il a été souligné, le code d'origine est susceptible de mourir d'une mort horrible lorsqu'il épuise toutes les voyelles. Comme cela ne fonctionne pas correctement, je l'ai remplacé par une approche un peu plus brutale de la devinette aléatoire.EDIT # 2 : Le code d'origine a été corrigé et se trouve maintenant.
Score :
25.7; totalerr: 24,529.9 (average of 10 tests).Comment ça marche
Ce solveur est complètement aléatoire. Même le hasard est aléatoire, des moments amusants!
Lorsque le programme reçoit une entrée, il devine un caractère aléatoire qu'il n'a pas déjà deviné et l'envoie à STDOUT.
L'algorithme de devinettes fonctionne ainsi:
la source
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. J'ai réussi à résoudre ce problèmecast(int). Après 10 exécutions, votre score moyen est de 22,4 mots avec 24529,1 suppositions incorrectes. Je vais tester à nouveau si vousSolution JAVASCRIPT + HTML
la source