Estaba interesado en ver las respuestas a esta pregunta (ahora desaparecida) , pero nunca se ha corregido / mejorado.
Dado un conjunto de dados Boggle de 6 lados (configuración robada de esta pregunta ), determine en dos minutos de tiempo de procesamiento qué configuración del tablero permitirá el puntaje más alto posible. (es decir, ¿qué dado en qué ubicación con qué lado hacia arriba permite el mayor grupo de palabras de puntuación?)
OBJETIVO
Su código no debe ejecutarse por más de 2 minutos (120 segundos). En ese momento, debería dejar de ejecutarse automáticamente e imprimir los resultados.
El puntaje final del desafío será el puntaje promedio de Boggle de 5 carreras del programa.
- En caso de empate, el ganador será el algoritmo que encuentre más palabras.
- En caso de que aún haya un empate, el ganador será el algoritmo que encuentre palabras más largas (8+) .
NORMAS / RESTRICCIONES
Este es un desafío de código; la longitud del código es irrelevante.
Consulte este enlace para obtener una lista de palabras (use la
ISPELL "english.0"
lista: a la lista SCOWL le faltan algunas palabras bastante comunes).- Se puede hacer referencia / importar / leer este listado en su código de la forma que desee.
- Solo
^([a-pr-z]|qu){3,16}$
se contarán las palabras que coincidan con la expresión regular . (Solo letras minúsculas, 3-16 caracteres, qu deben usarse como una unidad).
Las palabras se forman uniendo letras adyacentes (horizontal, vertical y diagonal) para deletrear las palabras en el orden correcto, sin usar un solo dado más de una vez en una sola palabra.
- Las palabras deben tener 3 letras o más; palabras más cortas no ganarán puntos.
- Las letras duplicadas son aceptables, simplemente no dados.
- No se permiten palabras que abarquen los bordes / se crucen de un lado del tablero al otro.
El puntaje final de Boggle ( no desafío ) es el total de los valores de puntos para todas las palabras que se encuentran.
- El valor del punto asignado para cada palabra se basa en la longitud de la palabra. (vea abajo)
- Las reglas normales de Boggle deducirían / descontarían las palabras encontradas por otro jugador. Suponga que aquí no hay otros jugadores involucrados y que todas las palabras encontradas cuentan para la puntuación total.
- Sin embargo, las palabras que se encuentran más de una vez en la misma cuadrícula solo deben contarse una vez.
Su función / programa debe ENCONTRAR la disposición óptima; simplemente codificar una lista predeterminada no funcionará.
Su salida debe ser una cuadrícula de 4x4 de su tablero de juego ideal, una lista de todas las palabras encontradas para ese tablero y la puntuación de Boggle para que coincida con esas palabras.
CONFIGURACIÓN DE MUERTE
A A E E G N
E L R T T Y
A O O T T W
A B B J O O
E H R T V W
C I M O T U
D I S T T Y
E I O S S T
D E L R V Y
A C H O P S
H I M N Qu U
E E I N S U
E E G H N W
A F F K P S
H L N N R Z
D E I L R X
TABLA DE PUNTUACIÓN DE BOGGLE ESTÁNDAR
Word length => Points
<= 2 - 0 pts
3 - 1
4 - 1
5 - 2
6 - 3
7 - 5
>= 8 - 11 pts
*Words using the "Qu" die will count the full 2 letters for their word, not just the 1 die.
EJEMPLO DE SALIDA
A L O J
V U T S
L C H E
G K R X
CUT
THE
LUCK
HEX
....
140 points
Si necesita más aclaraciones, ¡pregunte!
fuente
4527
(1414
palabras totales), que se encuentra aquí: ai.stanford.edu/~chuongdo/boggle/index.html^([a-pr-z]|qu){3,16}$
(que excluiría incorrectamente las palabras de 3 letras con qu, pero no hay ninguna).Respuestas:
C, promediando
500+15001750 puntosEsta es una mejora relativamente menor con respecto a la versión 2 (ver abajo las notas sobre versiones anteriores). Hay dos partes Primero: en lugar de seleccionar tableros al azar del grupo, el programa ahora itera sobre cada tablero en el grupo, usando cada uno por turno antes de regresar a la parte superior del grupo y repetir. (Dado que el grupo se modifica mientras se produce esta iteración, todavía habrá paneles que se eligen dos veces seguidas, o peor, pero esto no es una preocupación seria). El segundo cambio es que el programa ahora rastrea cuando el grupo cambia , y si el programa dura demasiado tiempo sin mejorar el contenido del grupo, determina que la búsqueda se ha "estancado", vacía el grupo y comienza de nuevo con una nueva búsqueda. Continúa haciendo esto hasta que hayan transcurrido los dos minutos.
Al principio pensé que estaría empleando algún tipo de búsqueda heurística para superar el rango de 1500 puntos. El comentario de @ mellamokb sobre un tablero de 4527 puntos me llevó a suponer que había mucho margen de mejora. Sin embargo, estamos usando una lista de palabras relativamente pequeña. El tablero de 4527 puntos estaba anotando usando YAWL, que es la lista de palabras más inclusiva que existe, es incluso más grande que la lista de palabras oficial de Scrabble de EE. UU. Con esto en mente, volví a examinar los tableros que mi programa había encontrado y noté que parecía haber un conjunto limitado de tableros por encima de 1700 más o menos. Entonces, por ejemplo, tuve varias carreras que descubrieron un tablero con 1726, pero siempre fue el mismo tablero que se encontró (ignorando rotaciones y reflexiones).
Como otra prueba, ejecuté mi programa usando YAWL como diccionario, y encontré el tablero de 4527 puntos después de aproximadamente una docena de carreras. Dado esto, estoy planteando la hipótesis de que mi programa ya está en el límite superior del espacio de búsqueda y, por lo tanto, la reescritura que estaba planeando introduciría una complejidad adicional para muy poca ganancia.
Aquí está mi lista de los cinco tableros de mayor puntaje que mi programa ha encontrado usando la
english.0
lista de palabras:Creo que el "tablero grep" de 1772 (como lo he llamado), con 531 palabras, es el tablero con la puntuación más alta posible con esta lista de palabras. Más del 50% de las ejecuciones de dos minutos de mi programa terminan con esta placa. También dejé mi programa ejecutándose durante la noche sin encontrar nada mejor. Entonces, si hay un tablero con una puntuación más alta, es probable que tenga algún aspecto que derrote la técnica de búsqueda del programa. Un tablero en el que cada pequeño cambio posible en el diseño causa una gran caída en el puntaje total, por ejemplo, nunca podría ser descubierto por mi programa. Mi presentimiento es que es muy poco probable que exista tal tablero.
Notas para la versión 2 (9 de junio)
Aquí hay una forma de usar la versión inicial de mi código como punto de partida. Los cambios a esta versión consisten en menos de 100 líneas, pero triplicaron el puntaje promedio del juego.
En esta versión, el programa mantiene un "grupo" de candidatos, que consta de los N tableros con la puntuación más alta que el programa ha generado hasta ahora. Cada vez que se genera un nuevo tablero, se agrega al grupo y se elimina el tablero con el puntaje más bajo en el grupo (que muy bien podría ser el tablero que se acaba de agregar, si su puntaje es más bajo que el que ya está allí). El grupo se llena inicialmente con paneles generados aleatoriamente, después de lo cual mantiene un tamaño constante durante la ejecución del programa.
El ciclo principal del programa consiste en seleccionar un tablero aleatorio del grupo y modificarlo, determinar el puntaje de este nuevo tablero y luego colocarlo en el grupo (si obtiene un puntaje suficiente). De esta manera, el programa refina continuamente tableros de alto puntaje. La actividad principal es realizar mejoras graduales e incrementales, pero el tamaño de la agrupación también permite que el programa encuentre mejoras de varios pasos que empeoran temporalmente el puntaje de un tablero antes de que pueda mejorarlo.
Por lo general, este programa encuentra un buen máximo local con bastante rapidez, después de lo cual, presumiblemente, cualquier máximo mejor es demasiado distante para ser encontrado. Y así, una vez más, no tiene mucho sentido ejecutar el programa durante más de 10 segundos. Esto podría mejorarse, por ejemplo, haciendo que el programa detecte esta situación y comience una nueva búsqueda con un nuevo grupo de candidatos. Sin embargo, esto generaría solo un aumento marginal. Una técnica de búsqueda heurística adecuada probablemente sería una mejor vía de exploración.
(Nota al margen: vi que esta versión estaba generando alrededor de 5k tableros / seg. Como la primera versión típicamente producía 20k tableros / seg, al principio me preocupé. Sin embargo, al hacer un perfil, descubrí que el tiempo adicional se dedicó a administrar la lista de palabras. En otras palabras, se debió por completo al programa de encontrar muchas más palabras por placa. A la luz de esto, consideré cambiar el código para administrar la lista de palabras, pero dado que este programa solo usa 10 de sus 120 segundos asignados, tal una optimización sería muy prematura).
Notas para la versión 1 (2 de junio)
Esta es una solución muy, muy simple. Todo lo que hace es generar tableros aleatorios, y luego de 10 segundos genera el que tiene la puntuación más alta. (El valor predeterminado fue de 10 segundos porque los 110 segundos adicionales permitidos por la especificación del problema generalmente no mejoran la solución final encontrada lo suficiente como para que valga la pena esperar). Por lo tanto, es extremadamente tonto. Sin embargo, tiene toda la infraestructura para hacer un buen punto de partida para una búsqueda más inteligente, y si alguien desea utilizarla antes de la fecha límite, les animo a que lo hagan.
El programa comienza leyendo el diccionario en una estructura de árbol. (El formulario no está tan optimizado como podría estarlo, pero es más que suficiente para estos fines). Después de alguna otra inicialización básica, comienza a generar tablas y puntuarlas. El programa examina aproximadamente 20k tableros por segundo en mi máquina, y después de aproximadamente 200k tableros, el enfoque aleatorio comienza a funcionar en seco.
Como solo se está evaluando un tablero en un momento dado, los datos de puntuación se almacenan en variables globales. Esto me permite minimizar la cantidad de datos constantes que deben pasarse como argumentos a las funciones recursivas. (Estoy seguro de que esto les dará colmenas a algunas personas, y les pido disculpas). La lista de palabras se almacena como un árbol de búsqueda binario. Cada palabra encontrada debe buscarse en la lista de palabras, para que las palabras duplicadas no se cuenten dos veces. Sin embargo, la lista de palabras solo es necesaria durante el proceso de evacuación, por lo que se descarta después de encontrar el puntaje. Por lo tanto, al final del programa, la tabla elegida debe puntuarse nuevamente para que la lista de palabras se pueda imprimir.
Dato curioso: el puntaje promedio para un tablero Boggle generado aleatoriamente, según la puntuación
english.0
, es 61.7 puntos.fuente
VBA (promedio que actualmente oscila entre 80 y 110 puntos, sin terminar)
Aquí está mi proceso de trabajo, pero está lejos de ser el mejor posible; mi mejor puntaje absoluto encontrado en cualquier tablero después de muchas pruebas es de alrededor de 120. Todavía debe haber una mejor limpieza general y estoy seguro de que se pueden obtener más eficiencias en varios lugares.
Esto probablemente parezca horrible para algunos de ustedes, pero como dije, WIP. ¡Estoy muy abierto a la crítica constructiva ! Perdón por el cuerpo muy largo ...
Módulo de clase de dados :
Módulo de clase de árbol :
Módulo de clase TreeNode :
Módulo principal :
fuente
Vista rápida del tamaño del espacio de búsqueda.
Reducir para excluir la repetición en cada dado.
@breadbox almacena el diccionario como una comprobación Hash Table O (1).
EDITAR
Mejor tablero (que he presenciado hasta ahora)
fuente
Mi entrada está aquí en Dream.In.Code ~ 30ms por búsqueda de placa (en una máquina de 2 núcleos, debería ser más rápida con más núcleos)
fuente
:
enhttp://
. ;-).NET
queVBA
no es demasiado duro.