Sie müssen einen Hangman-Löser schreiben. Bei der Prüfung anhand dieser englischen Wortliste [1] gewinnt der Löser, der die meisten Wörter löst, wobei die Anzahl der insgesamt falschen Vermutungen der entscheidende Faktor ist. Alle Wörter in der Wortliste werden in zufälliger Reihenfolge getestet.
[1]: Diese Wortliste stammt von hier , dann werden die Zahlen entfernt, dann werden Wörter mit der Länge 1 oder mit nicht alphabetischen Zeichen entfernt, und dann werden die häufigsten 4096 eindeutigen Wörter als diese Wortliste ausgewählt.
Die Details:
Ihr Programm interagiert mit dem Spielprogramm, das Sie durch die Unterstriche und richtig erratenen Buchstaben führt. Ihr Programm wird geben, um Ihre Vermutungen auszudrücken, und es muss aus der Eingabe abgeleitet werden, ob die vorherige Vermutung richtig oder falsch war. Nach 6 Fehlversuchen verliert Ihr Programm. Ihr Programm muss nach jedem Spielende (nach Gewinn oder Verlust) für das nächste Spiel bereit sein.
Ihre Codelänge muss streng unter 2048 Byte liegen, und Ihr Programm darf keine externen Ressourcen verwenden (einschließlich, aber nicht beschränkt auf den Zugriff auf die Wortliste im lokalen Speicher oder über das Internet).
Beispiel : (Die Eingabe wird >hier nur zur Verdeutlichung vorangestellt - sie ist tatsächlich nicht in der Eingabe vorhanden.)
>_______ // 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
Angenommen, Sie liegen sechsmal falsch, dann erhalten Sie eine letzte Eingabe, die impliziert, dass Ihre Vermutung falsch ist, und Ihr Programm muss bereit sein, eine neue Runde zu beginnen (dh eine weitere Eingabe vorzunehmen).
Wenn du gewinnst,
>_angman
h
>hangman
>_____ // new round
Nachdem Sie wissen, dass Sie gewonnen haben (da die Eingabe keine Unterstriche enthält), müssen Sie bereit sein, die nächste Runde anzunehmen.
Ihr Programm muss beendet werden, wenn es eine Eingabe erhält END.
Wenn Ihr Programm nicht deterministisch ist (abhängig von Zufälligkeit, Pseudozufälligkeit, Systemzeit, Umgebungstemperatur, meiner Stimmung usw.), müssen Sie dies in Ihrer Einreichung ausdrücklich angeben, und Ihre Punktzahl wird zehnmal (von mir, sofern nicht anders angegeben) vergeben. und gemittelt.
Hinweis : Wenn Sie Sprachen wie Python verwenden, müssen Sie Ihre stdout nach jeder print-Anweisung explizit löschen.
Das Spielprogramm sieht wie folgt aus ( Dank an 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')Verwendung: python ./game.py [yoursolverprogram]
Beispiel: python ./game.py ruby ./solver.rb
Dies sollte wie das alte Scoring-Programm funktionieren, ist jedoch nicht von Named Pipes abhängig, sodass es auch auf anderen Plattformen funktioniert. Lesen Sie den Revisionsverlauf, wenn Sie an der alten interessiert sind.
quelle
subprocessanstelle eines externen Fifo das Spiel zu steuern? Auf diese Weise funktioniert der Code auch für andere Betriebssysteme (z. B. Cygwin unter Windows). Hier wurde einegame.pyÄnderung vorgenommen,subprocessum das in der Befehlszeile angegebene Programm zu starten: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Verwenden Sie es alspython game.py <program> [args]zBpython game.py python hangman.py.Antworten:
Python 2, Score = 2111
Laufen Sie mit
python -u. (Zum Testen mit dem angegebenen Controllerpython ./game.py python -u ./solver.py.) Dies sind 2044 Codebytes + 1 für-u= 2045 Bytes.Ergebnis
Wie es funktioniert
Das Programm ersetzt alle
_s durch1s im aktuellen Zustand, behandelt das Ergebnis als Ganzzahl zur Basis 36 und nimmt es als Modulo 1879, was uns eine grobe Hash-Funktion gibt. Es wählt einen zu erratenden Buchstaben aus, indem es diesen Hash-Wert in die lange Buchstabenfolge indiziert. Wenn es diesen Buchstaben bereits vorher erraten hat, verringert es den Modul um 6 (so bleibt es immer relativ prim bis 36) und wählt einen anderen Buchstaben aus und wiederholt ihn, bis es einen Buchstaben findet, den es noch nicht erraten hat.Ich habe diese Strategie so entworfen, dass sie viele optimierbare Variablen (die einzelnen Buchstaben der langen Zeichenfolge) enthält, von denen die meisten die endgültige Punktzahl unabhängig voneinander geringfügig beeinflussen. Damit eignet es sich gut für die Optimierung von Bergsteigerstilen - ich habe die diversifizierte Spätakzeptanzsuche verwendet .
Python 2, Score = 2854
Mit der großzügigen Verwendung nicht druckbarer Bytes und der integrierten Komprimierung können wir viel mehr Informationen einlesen.
Dekodiere mit
xxd -rund starte mitpython -u. (Zum Testen mit dem angegebenen Controllerpython ./game.py python -u ./solver.py.) Dies sind 2047 Codebytes + 1 für-u= 2048 Bytes.Ergebnis
quelle
Python: 2006 Bytes, Score = 1501
1885 Bytes, Score = 13371961 Bytes, Score = 1207Hier ist mein Beitrag:
Ergebnisausgabe:
Dieses Programm ist vollständig deterministisch. Der Riesen-Blob (ein mit der Basis 64 codierter Block
zlibkomprimierter Daten) ist eine Liste von Entscheidungsbäumen (ein Baum pro Wortlänge). Jeder Entscheidungsbaum codiert einen vollständigen Binärbaum mit einer Tiefe zwischen 2 und 5. Jeder interne Knoten ist ein einzelnes Zeichen, und die Entscheidung erfolgt basierend darauf, ob das Zeichen im Henkerwort vorhanden ist oder nicht.Jeder Blattknoten des Binärbaums enthält eine optimierte Häufigkeitstabelle, die für diesen Zweig der Baumsuche spezifisch ist. Die Tabelle wurde speziell optimiert, um die Vervollständigung bestimmter Wörter zu fördern, während andere Wörter vollständig ignoriert werden (was aufgrund des begrenzten "Fehler" -Budgets nicht möglich ist). Die Tabelle ist nicht für die Minimierung von Fehlern optimiert, und daher ist die Gesamtanzahl der Fehler des Programms trotz seiner (relativ) guten Punktzahl hoch.
Der Optimierer, der nicht gezeigt ist, verwendet einen nichtdeterministischen nichtlinearen Optimierer, der eine randomisierte Gradientenabstiegsstrategie verwendet, um die Häufigkeitstabellen zu erzeugen.
quelle
range(4)können Sie diese durch ersetzen,[1]*4sofern Sie den Wert von nicht wirklich verwenden müsseni.decode('zip')anstelle vondecode('zlib')Rubin
Eine gemeinsame Einreichung von Benutzer PragTob und mir.
Ergebnis:
Dies hat 1672 Zeichen und ist noch nicht golfen, so dass wir reichlich Raum für algorithmische Verbesserungen haben.
Zuerst speichern wir einen Hash von Zeichenhäufigkeiten (berechnet aus der Wortliste), gruppiert nach Wortlänge.
Dann sortieren wir in jeder Runde einfach alle Zeichen nach den Frequenzen für die aktuelle Länge und probieren sie von den häufigsten bis zu den am wenigsten verbreiteten aus. Mit diesem Ansatz scheitern wir offensichtlich an jedem einzelnen Wort, das auch nur einen mittleren gemeinsamen Charakter hat.
quelle
score is 625, totalerr is 23196mit deinem aktualisierten Algorithmus noch auf dem neuesten Stand? Ich habe es mit einer ähnlichenAktualisieren Mit einer @ nneonneo-ähnlichen Methode erreiche ich diesen Code mit genau 2047 Zeichen .
Ergebnis:
Code:
Alter Eintrag
Ergebnis:
Es ist kein Durchschnitt, da dieser Algorithmus deterministisch ist, dh, er gibt für jede gemischte Liste von Wörtern immer die gleiche Punktzahl an.
Hier ist mein Eintrag in Python 2.7; Golf (717 Zeichen)
Dies verwendet eine ähnliche Idee wie @ m.buettner und speichert eine geordnete Liste von Buchstaben, nach denen die Vermutungen angestellt werden. Dabei werden die Frequenzdaten jedoch nicht direkt verwendet, sondern es werden nur fast alle möglichen Buchstabenpermutationen versucht, das Spiel simuliert und schließlich die Permutation verwendet, die die beste Punktzahl ergibt.
Diese Version wurde unter Verwendung der Top-9-Buchstaben optimiert, sodass für Wörter mit 2 und 3 Buchstaben die Permutation in der Klasse der Algorithmen, in der die Informationen aus der vorherigen Eingabe ignoriert werden, bereits die optimale ist. Ich führe derzeit noch den Code für Top-10-Buchstaben aus, optimiere die 4-Buchstaben-Wörter (und finde auch eine bessere Lösung für längere Wörter).
Ungültiger Eintrag
Für mein Benchmarking ist hier der Code, der den vollständigen Entscheidungsbaum (11092 Zeichen) verwendet.
Ergebnis:
Code:
quelle
Perl, 1461 Bytes, Score = 1412, Totalerr = 21050
(Beachten Sie, dass es 1461 Bytes sind, nachdem einiges an optionalem Leerzeichen entfernt wurde. Wie gedruckt, ist es ungefähr hundert schwerer, aber immer noch deutlich unter 2000.)
Ich habe ein paar "subtilere" Ansätze ausprobiert, aber dieser hat sie alle geschlagen. Bei den beiden Datenfolgen handelt es sich einfach um Ranglisten der Zeichen, die am wahrscheinlichsten auf jedes Zeichen folgen, und der Zeichen, die am wahrscheinlichsten vor jedem Zeichen stehen (mit Digraphen, die in der überhaupt nicht dargestellten Wortliste nicht vorkommen).
<und>werden verwendet, um den Anfang und das Ende des Wortes darzustellen. Bedeutet beispielsweise,"w[aiehonrlsdtkfy]"dass "wa" häufiger ist als "wi" häufiger als "wir" usw.%d, enthält die Vorwärtsabbildung eine globale Rangfolge, gespeichert als$d{''}. Es wird für Orte verwendet, an denen sich zwei Unbekannte in einer Reihe befinden oder an denen alle Digraphen in der Wortliste erschöpft sind (es muss sich also um ein Wort handeln, das keine Wortliste ist).Für jede unbekannte Position im Wort wird das vorangegangene Zeichen angezeigt. Jedes mögliche nachfolgende Zeichen erhält eine Punktzahl, beginnend bei 180 für das bestplatzierte Zeichen und absteigend auf 80 am Ende der Liste. dann wird dasselbe für das folgende Zeichen gemacht. Alle Punktzahlen für alle Charaktere werden addiert und die mit der höchsten Punktzahl wird ausgewählt.
Nachdem ein Buchstabe erraten wurde, wird er direkt aus den Ranglistentabellen entfernt, sodass er nicht mehr erraten werden kann (bis wir ein neues Wort beginnen und die Tabellen neu initialisieren).
Update: Wir haben eine Reihe von Punkten gesammelt, indem wir einen Fehler behoben haben (wir haben keine Buchstaben aus der umgekehrten Tabelle entfernt) und die Art und Weise geändert, in der die Punkte in der Liste abfallen.
quelle
Python: 2046 Bytes, Score = 1365
Score ist 1365, totalerr ist 21343
Ein Großteil des Codes stammt von Nneonneos Python-Einreichung (ohne die ich das 2048-Byte-Limit nicht erreicht hätte). Ursprünglich dachte ich, dass dies ungefähr 200 Punkte mehr bringen sollte, aber ich entdeckte einen Fehler in meinem Tool zum Erstellen von Datenstrings. Nun, das ist behoben, meine Punktzahl ist ein viel vernünftigeres 1365.
Anstatt Binärbäume basierend auf der Länge zu erstellen, habe ich einen einzelnen Binärbaum erstellt, der die Frequenzinformationen enthält. Der Baum hat keine einheitliche Tiefe, da es keinen Grund gibt, Frequenzinformationen für etwas tieferes als sechs falsche Vermutungen zu speichern (aber die richtigen Vermutungen könnten theoretisch für "erheblich" und "unangenehm" zwölf tief sein). Dieser unbeholfen geformte Baum wird durch den Fakultätscode navigiert (tatsächlich unter Verwendung der Kombinationsfunktion ). Um den Datenstring komprimierbarer zu machen, habe ich alle nicht verwendeten Indizes mit 's' aufgefüllt.
Ich habe ein Skript verwendet, um gute Zeichenfolgen zu berechnen, die als d gespeichert werden sollen. Wenn jemand ein paar Zeichen mehr aus dem Rest des Skripts herausholen kann, sind hier einige Ersetzungen aufgeführt, die zu besseren Ergebnissen führen sollten. Die oberste Zeile ist die im obigen Programm codierte Zeichenfolge.
Das Skript, mit dem ich die Datenzeichenfolgen generiert habe, ist hier , falls es für jemanden nützlich ist!
quelle
distinctUm Ihnen das Debuggen zu erleichtern, fügen Sie einige zusätzliche Informationen hinzu: Wenn das Wort angegeben wurde , war die Ausgabe Ihres Programms in Ordnungeitanogsuc, was bedeutet, dass es die Ausgabe nicht mehr gibt, selbst wenn es nur fünf Mal falsch geraten hat.Die Programmiersprache D ist das Werkzeug meiner Wahl für diese Herausforderung.
Nur knapp unter dem Limit von 2.048 Bytes, obwohl es in einigen Bereichen leicht abgenutzt ist, um die Anzahl der Bytes zu verringern, bleibt all das schwere Heben perfekt lesbar. Dieser Löser ist nicht sehr gut in seiner Arbeit, und ich gehe davon aus, dass er leicht zu schlagen ist, aber dies dient nur dazu, den Ball ins Rollen zu bringen. Starte die Dinge sozusagen.
EDIT # 1 :
Wie bereits erwähnt, kann der ursprüngliche Code einen schrecklichen Tod erleiden, wenn alle Vokale erschöpft sind. Da es nicht richtig funktioniert, habe ich es durch eine etwas brutalere Herangehensweise an Zufallsraten ersetzt.EDIT # 2 : Originalcode wurde behoben und steht jetzt.
Punktzahl :
25.7; totalerr: 24,529.9 (average of 10 tests).Wie es funktioniert
Dieser Löser ist völlig zufällig. Sogar die Zufälligkeit ist zufällig, lustige Zeiten!
Wenn das Programm Eingaben empfängt, errät es ein zufälliges Zeichen, das es noch nicht erraten hat, und sendet es an STDOUT.
Der Schätzalgorithmus funktioniert folgendermaßen:
quelle
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Ich habe es geschafft, dies zu behebencast(int). Nach 10 Läufen beträgt Ihre durchschnittliche Punktzahl 22,4 Wörter mit 24529,1 falschen Vermutungen. Ich werde es erneut testen, wenn Sie die fortgeschrittenere Version reparieren :) Viel SpaßJAVASCRIPT + HTML-Lösung
quelle