El objetivo de este desafío es escribir un programa capaz de adivinar una palabra en el menor número posible de intentos. Se basa en el concepto del programa de televisión Lingo ( http://en.wikipedia.org/wiki/Lingo_(US_game_show) ).
Reglas
Dada una longitud de palabra aprobada como primer argumento en su línea de comando, el programa del jugador dispone de cinco intentos de adivinar la palabra escribiendo una suposición en su salida estándar seguida de un solo \n
carácter.
Después de hacer una suposición, el programa recibe una cadena en su entrada estándar, también seguida de un solo \n
carácter.
La cadena tiene la misma longitud que la palabra para adivinar y se compone de una secuencia de los siguientes caracteres:
X
: lo que significa que la letra dada no está presente en la palabra para adivinar?
: lo que significa que la letra dada está presente en la palabra para adivinar, pero en otra ubicaciónO
: lo que significa que la letra en esta ubicación se ha adivinado correctamente
Por ejemplo, si la palabra que se debe adivinar es dents
, y el programa envía la palabra dozes
, recibirá OXX?O
porque d
y s
es correcta, e
está fuera de lugar o
y z
no está presente.
Tenga cuidado de que si una letra está presente más veces en el intento de adivinar que en la palabra para adivinar, no se marcará como ?
y O
más veces que el número de ocurrencias de la letra en la palabra para adivinar. Por ejemplo, si la palabra para adivinar es cozies
y el programa envía tosses
, la recibirá XOXXOO
porque solo hay una s
para localizar.
Las palabras se eligen de una lista de palabras en inglés. Si la palabra enviada por el programa no es una palabra válida de la longitud correcta, el intento se considera una falla automática y solo X
se devuelven.
El programa del reproductor debe asumir que un archivo llamado wordlist.txt
y que contiene una palabra por línea está presente en el directorio de trabajo actual, y puede leerse según sea necesario.
Las conjeturas solo deben estar compuestas de caracteres alfabéticos en minúsculas ( [a-z]
).
No se permiten otras operaciones de red o archivo para el programa.
El juego termina cuando una cadena solo se compone de O
se devuelve o después de que el programa haya realizado 5 intentos y no haya podido adivinar la palabra.
Puntuación
La puntuación de un juego viene dada por la fórmula dada:
score = 100 * (6 - number_of_attempts)
Entonces, si la palabra se adivina correctamente en el primer intento, se otorgan 500 puntos. El último intento vale 100 puntos.
No adivinar la palabra otorga cero puntos.
El hoyo
Los programas de los jugadores serán evaluados intentando que adivinen 100 palabras al azar para cada longitud de palabra entre 4 y 13 caracteres inclusive.
La selección aleatoria de palabras se realizará por adelantado, por lo que todas las entradas tendrán que adivinar las mismas palabras.
El programa ganador y la respuesta aceptada serán los que alcancen el puntaje más alto.
Los programas se ejecutarán en una máquina virtual Ubuntu, utilizando el código en https://github.com/noirotm/lingo . Se aceptan implementaciones en cualquier idioma siempre que se proporcionen instrucciones razonables para compilarlas o ejecutarlas.
Proporciono algunas implementaciones de prueba en ruby en el repositorio de git, no dude en inspirarse en ellas.
Esta pregunta se actualizará periódicamente con clasificaciones para las respuestas publicadas para que los retadores puedan mejorar sus entradas.
La evaluación final oficial tendrá lugar el 1 de julio .
Actualizar
Las entradas ahora pueden asumir la presencia de wordlistN.txt
archivos para acelerar la lectura de la lista de palabras para la longitud de palabra actual para N entre 4 y 13 inclusive.
Por ejemplo, hay un wordlist4.txt
archivo que contiene las palabras de cuatro letras, y wordlist10.txt
contiene las palabras de diez letras, y así sucesivamente.
Resultados de la primera ronda
A la fecha de 2014-07-01, se han presentado tres entradas, con los siguientes resultados:
4 5 6 7 8 9 10 11 12 13 Total
./chinese-perl-goth.pl 8100 12400 15700 19100 22100 25800 27900 30600 31300 33600 226600
java Lingo 10600 14600 19500 22200 25500 28100 29000 31600 32700 33500 247300
./edc65 10900 15800 22300 24300 27200 29600 31300 33900 33400 33900 262600
** Rankings **
1: ./edc65 (262600)
2: java Lingo (247300)
3: ./chinese-perl-goth.pl (226600)
Todas las entradas se realizaron consistentemente, con un claro ganador, siendo la entrada de C ++ de @ edc65.
Todos los concursantes son bastante impresionantes. Hasta ahora no he podido vencer a @ chinese-perl-goth.
Si se envían más entradas, se realizará otra evaluación. Las entradas actuales también se pueden mejorar si cree que puede hacerlo mejor.
fuente
Respuestas:
C ++ 267700 puntos
Un portado de un viejo motor MasterMind.
Diferencias de MasterMind:
La idea básica es elegir la palabra que minimice el espacio de la solución. El algoritmo es realmente lento para la primera suposición (quiero decir 'días'), pero la mejor primera suposición depende solo de la palabra len, por lo que está codificado en la fuente. Las otras conjeturas se realizan en cuestión de segundos.
El código
(Compilar con g ++ -O3)
Mis puntuaciones
Evaluación con jerga, 100 rondas:
Total 265'100
Puntajes autoevaluados
Aquí están mis puntos promedio, anotados en toda la lista de palabras. No es completamente confiable porque algunos detalles del algoritmo han cambiado durante las pruebas.
Según estos números, mi puntaje promedio debería estar cerca de 257'800
PUNTUACIÓN
Finalmente instalé Ruby, así que ahora tengo un puntaje 'oficial':
fuente
Java, 249700 puntos (supera al chino Perl Goth en mi prueba)
Lista de clasificación actualizada:
Aquí está la antigua lista de clasificación usando
pit.rb
:En comparación con @chineseperlgoth, pierdo en palabras más cortas (<6 caracteres) pero gano en palabras más largas (> = 6 caracteres).La idea es similar a @chineseperlgoth, es solo que mi idea principal es encontrar la conjetura (puede ser cualquier palabra de la misma longitud, no necesariamente una de las posibilidades restantes) que brinda la mayor cantidad de información para la próxima suposición.
Actualmente todavía estoy jugando con la fórmula, pero para el marcador anterior, elijo la palabra que producirá el mínimo para:La última versión utiliza una puntuación diferente para encontrar la siguiente mejor suposición, que es maximizar el número de "posibilidad única" después de la suposición actual. Esto se hace probando todas las palabras en la lista de palabras podadas (para ahorrar tiempo) en todos los posibles candidatos, y ver qué suposición es más probable que produzca una "posibilidad única" (es decir, después de esta suposición, solo habrá una respuesta posible) para el siguiente conjetura
Entonces, por ejemplo, esta ejecución:
De las primeras tres conjeturas, ya obtuvimos "* oo * s" con una "n" en alguna parte y todavía tenemos que encontrar una letra más. Ahora, la belleza de este algoritmo es que, en lugar de adivinar palabras que son similares a esa forma, adivina la palabra que no tiene ninguna relación con las conjeturas anteriores, tratando de dar más letras, con suerte revelando la letra que falta. En este caso, sucede que también obtiene la posición de la "b" faltante correctamente, y concluye con la suposición final correcta "bendiciones".
Aquí está el código:
fuente
Perl
Todavía hay margen de mejora, pero al menos supera a los jugadores de ejemplo incluidos :)
Asume el acceso de escritura al directorio actual para almacenar en caché las listas de palabras (para que se ejecute un poco más rápido); creará
wordlist.lenN.stor
archivos usandoStorable
. Si esto es un problema, elimineread_cached_wordlist
y cambie el código para usar soloread_wordlist
.Explicación
Primero, construyo un histograma de frecuencias de letras en todas las palabras en la lista de palabras actual (
build_histogram
). Entonces necesito elegir mi siguiente suposición, que se realiza porfind_best_word
. El algoritmo de puntuación solo agrega los valores del histograma, omitiendo las letras ya vistas. Esto me da una palabra que contiene las letras más frecuentes en la lista de palabras. Si hay más de una palabra con una puntuación dada, elijo una al azar. Después de encontrar una palabra, la envío al motor del juego, leo la respuesta y luego trato de hacer algo útil con ella :)Mantengo un conjunto de condiciones, es decir, letras que pueden aparecer en una posición determinada de una palabra. Al inicio, esto es simple
(['a'..'z'] x $len)
, pero se actualiza basándose en las sugerencias dadas en la respuesta (verupdate_conds
). Construyo una expresión regular a partir de esas condiciones y luego filtro la lista de palabras a través de ella.Durante las pruebas descubrí que el filtrado mencionado anteriormente no maneja
?
demasiado bien, de ahí el segundo filtro (filter_wordlist_by_reply
). Esto aprovecha el hecho de que una letra marcada como?
aparece en la palabra en una posición diferente y filtra la lista de palabras en consecuencia.Estos pasos se repiten para cada iteración del bucle principal, a menos que se encuentre la solución (o ya no sea posible leer desde stdin, lo que significa una falla).
Código
fuente