Debes escribir un solucionador de ahorcado. Probando contra esta lista de palabras en inglés [1] , el solucionador que resuelve la mayor cantidad de palabras gana, siendo el número de conjeturas incorrectas el factor decisivo. Todas las palabras en la lista de palabras serán probadas en orden aleatorio.
[1]: Esta lista de palabras se toma de aquí , luego se eliminan los números, luego se eliminan las palabras con longitud 1 o con caracteres no alfabéticos, luego se eligen las 4096 palabras únicas más frecuentes como esta lista de palabras.
Los detalles:
Su programa interactuará con el programa del juego, que le dará a través de stdin los guiones bajos y las letras correctamente adivinadas. Su programa le dará a stdout sus conjeturas, y tiene que inferir de la entrada si la suposición anterior fue correcta o incorrecta. Después de equivocarse 6 veces, su programa pierde. Su programa debe estar listo para el próximo juego después de que finalice cada juego (después de ganar o perder).
La longitud de su código debe ser estrictamente inferior a 2048 bytes, y su programa no debe utilizar ningún recurso externo (incluido, entre otros, el acceso a la lista de palabras en el almacenamiento local o desde Internet).
Ejemplo : (La entrada está precedida por >aquí solo para aclaración; en realidad no está presente en la 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
Suponga que está equivocado 6 veces, recibirá una entrada final que implica que su suposición es incorrecta, y su programa debe estar listo para comenzar una nueva ronda (es decir, tomar otra entrada).
Si tu ganas,
>_angman
h
>hangman
>_____ // new round
Después de saber que ha ganado (porque la entrada no tiene guiones bajos), debe estar listo para aceptar la próxima ronda.
Su programa debe finalizar cuando recibe una entrada END.
Si su programa no es determinista (depende de la aleatoriedad, la pseudoaleatoriedad, la hora del sistema, la temperatura ambiente, mi estado de ánimo, etc.), debe indicarlo explícitamente en su envío, y su puntaje se tomará 10 veces (por mí, a menos que se indique lo contrario) y promediado.
Nota : si usa idiomas como Python, por favor, elimine explícitamente su stdout después de cada declaración de impresión.
El programa del juego es el siguiente (crédito a 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]
Ejemplo: python ./game.py ruby ./solver.rb
Esto debería funcionar como el antiguo programa de puntuación, pero no depende de canalizaciones con nombre, por lo que puede funcionar en otras plataformas. Consulte el historial de revisiones si está interesado en el anterior.
fuente
subprocesslugar de un fifo externo para conducir el juego? De esta manera, el código funcionará para otros sistemas operativos (por ejemplo, Cygwin en Windows). Aquí segame.pymodifica para usarsubprocesspara iniciar el programa nombrado en la línea de comandos: gist.github.com/nneonneo/d173f8888e1ea0c6fe37 . Úselo comopython game.py <program> [args], por ejemplopython game.py python hangman.py.Respuestas:
Python 2, puntaje = 2111
Corre con
python -u. (Para probar con el controlador dado,.python ./game.py python -u ./solver.py) Esto es 2044 bytes de código + 1 para-u= 2045 bytes.Resultado
Cómo funciona
El programa reemplaza todos los
_s con1s en el estado actual, trata el resultado como un entero de base 36 y lo toma el módulo 1879, dándonos una función hash cruda. Elige una letra para adivinar indexando este valor hash en la larga cadena de letras. Si ya adivinó esa letra antes, disminuye el módulo en 6 (por lo que siempre permanece relativamente primo a 36) y elige una letra diferente, repitiendo hasta encontrar una letra que aún no adivinó.Diseñé esta estrategia para tener muchas variables ajustables (las letras individuales de la cadena larga), la mayoría de las cuales afectarán de manera independiente el puntaje final en una pequeña cantidad. Eso lo hace muy adecuado para la optimización del estilo de escalada: utilicé la búsqueda diversificada de aceptación tardía .
Python 2, puntuación = 2854
Con el uso liberal de bytes no imprimibles y la compresión incorporada, podemos obtener mucha más información.
Decodifica con
xxd -ry corre conpython -u. (Para probar con el controlador dado,.python ./game.py python -u ./solver.py) Esto es 2047 bytes de código + 1 para-u= 2048 bytes.Resultado
fuente
Python: 2006 bytes, puntaje = 1501
1885 bytes, puntuación = 13371961 bytes, puntuación = 1207Aquí está mi presentación:
Resultado de puntuación:
Este programa es totalmente determinista. El blob gigante (que es un fragmento de
zlibdatos comprimidos codificado en base 64 ) es una lista de árboles de decisión (un árbol por longitud de palabra). Cada árbol de decisión codifica un árbol binario completo con una profundidad entre 2 y 5. Cada nodo interno es un solo carácter, y la decisión procede en función de si el carácter está presente o no en la palabra del verdugo.Cada nodo hoja del árbol binario contiene una tabla de frecuencia optimizada específica para esa rama de la búsqueda del árbol. La tabla está optimizada específicamente para favorecer la finalización de ciertas palabras, mientras que ignora completamente otras (que no puede alcanzar debido al limitado presupuesto de "falla"). La tabla no está optimizada para minimizar los errores y, por lo tanto, el recuento total del programa es alto a pesar de su (relativamente) buena puntuación.
El optimizador, que no se muestra, utiliza un optimizador no lineal no determinista que utiliza una estrategia aleatoria de descenso de gradiente para producir las tablas de frecuencias.
fuente
range(4)puede reemplazarlo[1]*4siempre que no necesite usar el valor dei.decode('zip')lugar dedecode('zlib')Rubí
Una presentación conjunta del usuario PragTob y yo.
Resultado:
Esto tiene 1672 caracteres y aún no se juega al golf, por lo que tenemos un amplio margen para la mejora algorítmica.
Primero almacenamos un hash de frecuencias de caracteres (calculadas a partir de la lista de palabras) agrupadas por longitud de palabra.
Luego, en cada ronda, simplemente ordenamos todos los caracteres por las frecuencias para la longitud actual y los probamos del más común al menos común. Al usar este enfoque, obviamente fallamos en cada palabra que tiene incluso un carácter común medio.
fuente
score is 625, totalerr is 23196todavía actualizado con su algoritmo actualizado? Intenté uno similar y obtuve solo un máximo de 300.Actualización Usando un método similar a @nneonneo, llego a este código, exactamente 2047 caracteres .
Puntuación:
Código:
Entrada antigua
Resultado:
No es un promedio ya que este algoritmo es determinista, es decir, siempre da la misma puntuación para cualquier lista de palabras barajada.
Aquí está mi entrada en Python 2.7; Golfizado (717 caracteres)
Esto utiliza una idea similar a @ m.buettner, almacenando una lista ordenada de letras después de las cuales se harán las conjeturas. Pero, esto no usa datos de frecuencia directamente, sino que simplemente intenta casi todas las permutación de letras posibles y simula el juego, y finalmente toma la permutación que da la mejor puntuación.
Esta versión está optimizada usando las letras de las 9 mejores, por lo que para las palabras de 2 y 3 letras, la permutación ya es la óptima, en la clase de algoritmo donde se ignora la información de la entrada anterior. Actualmente sigo ejecutando el código para las 10 letras principales, optimizando las palabras de 4 letras (y también buscando una mejor solución para las palabras más largas).
entrada invalida
Para mi evaluación comparativa, aquí está el código que usa el árbol de decisión completo, 11092 caracteres.
Puntuación:
Código:
fuente
Perl, 1461 bytes, puntaje = 1412, totalerr = 21050
(Tenga en cuenta que son 1461 bytes después de eliminar un poco de espacio en blanco opcional. Tal como se imprimió, es cien veces más pesado, pero aún está por debajo de 2000).
Intenté un montón de enfoques más "sutiles", pero este terminó superando a todos. Las dos cadenas de datos son simplemente listas clasificadas de los caracteres con más probabilidades de seguir a cada carácter, y los caracteres con mayor probabilidad de preceder a cada carácter (con los dígrafos que no aparecen en la lista de palabras no están representados).
<y>se usan para representar el principio y el final de la palabra. Como ejemplo,"w[aiehonrlsdtkfy]"significa que "wa" es más común que "wi" es más común que "nosotros"%d, etc. , la asignación directa incluye una clasificación global, almacenada como$d{''}. Se usa para lugares donde hay dos incógnitas seguidas, o donde todos los dígrafos en la lista de palabras están agotados (por lo que debemos tratar con una palabra que no sea de la lista de palabras).Por cada posición desconocida en la palabra, mira el carácter anterior, le da una puntuación a cada personaje siguiente posible, comenzando en 180 para el mejor clasificado y disminuyendo a 80 al final de la lista; entonces se hace lo mismo para el siguiente personaje. Se suman todos los puntajes para todos los personajes y se selecciona el que tiene el puntaje más alto.
Después de adivinar una letra, se elimina directamente de las tablas de clasificación, por lo que no se puede volver a adivinar (hasta que comencemos una nueva palabra y reinicialicemos las tablas).
Actualización: gané un montón de puntos solucionando un error (no estábamos eliminando letras de la tabla inversa) y cambiando la forma en que los puntos disminuyen a medida que avanzamos en la lista.
fuente
Python: 2046 bytes, puntaje = 1365
el puntaje es 1365, el totalizador es 21343
Gran parte del código se toma prestado del envío de Python de nneonneo (sin el cual no habría obtenido esto por debajo del límite de 2048 bytes). Originalmente pensé que esto debería sumar unos 200 más, pero descubrí un error en mi herramienta de creación de cadenas de datos. Ahora que está arreglado, mi puntaje es un 1365 mucho más razonable.
En lugar de crear árboles binarios basados en la longitud, creé un solo árbol binario para contener la información de frecuencia. El árbol no tiene una profundidad uniforme, ya que no tiene sentido almacenar información de frecuencia para algo más profundo que seis conjeturas incorrectas (pero las conjeturas correctas podrían ser en teoría doce de profundidad para "considerablemente" e "incómodo"). Este árbol de forma incómoda es navegado por el código factorial (en realidad usando la función de combinación ). Para hacer que la cadena de datos sea más compresible, rellené todos los índices no utilizados con 's'.
Utilicé un script para calcular buenas cadenas para almacenar como d, y si alguien puede jugar unos pocos caracteres más del resto del script, entonces aquí hay algunos reemplazos que deberían dar lugar a mejores puntajes. La fila superior es la cadena codificada en el programa anterior.
El script que usé para generar las cadenas de datos está aquí , ¡en caso de que sea útil para alguien!
fuente
distinct, la salida de su programa fue, en ordeneitanogsuc, lo que significa que de alguna manera deja de dar salida incluso si solo adivina incorrectamente 5 veces.El lenguaje de programación D es mi herramienta de elección para este desafío.
Apenas por debajo del límite de 2,048 bytes, aunque en algunas partes se juega un poco de golf para que la cuenta regresiva de bytes, todo el trabajo pesado sigue siendo perfectamente legible. Este solucionador no es muy bueno en su trabajo, y espero que sea fácil de superar, pero esto es solo para que la pelota ruede. Patea las cosas, por así decirlo.
EDITAR # 1 :
Como se ha señalado, el código original es propenso a morir de una muerte horrible cuando agota todas las vocales. Como no funciona correctamente, lo he reemplazado con un enfoque algo más brutal para adivinar al azar.EDITAR # 2 : El código original se ha corregido y ahora se mantiene.
Puntuación :
25.7; totalerr: 24,529.9 (average of 10 tests).Cómo funciona
Este solucionador es completamente al azar. ¡Incluso la aleatoriedad es aleatoria, momentos divertidos!
Cuando el programa recibe una entrada, adivinará un carácter aleatorio que aún no ha adivinado y lo enviará a STDOUT.
El algoritmo de adivinanzas funciona así:
fuente
./test.d(44): Error: cannot implicitly convert expression (uniform(0, Letters.length, rng)) of type ulong to int. Me las arreglé para arreglar estocast(int). Después de 10 carreras, su puntaje promedio es de 22.4 palabras con 24529.1 conjeturas incorrectas. Volveré a probar si arreglas la versión más avanzada :) DiviérteteJAVASCRIPT + Solución HTML
fuente