Scralphabet
Una bolsa normal de fichas Scrabble contiene las siguientes letras ( ?
es una ficha en blanco, que puede representar cualquier otra letra):
AAAAAAAAABBCCDDDDEEEEEEEEEEEEFFGGGHHIIIIIIIIIJKLLLLMMNNNNNNOOOOOOOOPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ??
Las letras tienen el siguiente valor:
{"A": 1,"B": 3,"C": 3,"D": 2,"E": 1,"F": 4,"G": 2,"H": 4,"I": 1,"J": 8,"K": 5,"L": 1,"M": 3,"N": 1,"O": 1,"P": 3,"Q": 10,"R": 1,"S": 1,"T": 1,"U": 1,"V": 4,"W": 4,"X": 8,"Y": 4,"Z": 10,"?": 0}
Dada una bolsa normal de mosaicos Scrabble, construya el conjunto de palabras que no se crucen con mayor puntuación (es decir, palabras individuales, no en un tablero de Scrabble) dadas las siguientes condiciones:
- La puntuación para cada palabra es
sum(letter_values) * length(word)
. - Solo puede incluir un máximo de una palabra que comience con cada letra del alfabeto (por lo tanto, un máximo de 26 palabras).
- Solo se pueden incluir palabras válidas de Scrabble (de este diccionario ). Puede leer el diccionario de un archivo, codificarlo (ugh) o eliminarlo del sitio web.
- No necesita usar todas las fichas, pero todas las fichas no utilizadas forman una sola palabra, calificada de la misma manera, lo que resta de su puntaje.
Si lo desea, su código puede aceptar dos entradas: el contenido de la bolsa como una cadena y los valores de las letras en algún formato similar a una pitón dict
(como arriba); alternativamente, puede codificar el contenido de la bolsa y los valores de las letras. Debería mostrar las palabras en su conjunto, sus puntajes respectivos y su puntaje total, en algún formato razonable.
El conjunto de palabras con la puntuación más alta gana, y los lazos se publican primero.
fuente
print"FOO18\nBAR15\nBAZ42\n...\n1523"
?Respuestas:
C, 2765 (óptimo)
Editar
Ahora todo en un solo archivo C. Esto solo encuentra todas las soluciones óptimas. Todos deben tener 6 palabras de 15 letras y una palabra de 10 letras que consta de 8 letras de valor 1 y dos espacios en blanco. Para eso solo necesito cargar una fracción del diccionario y no tengo que buscar palabras de 15 letras con espacios en blanco. El código es una simple búsqueda exhaustiva de profundidad primero.
Uso:
Tenga en cuenta que cada solución se imprime dos veces porque al agregar una palabra 'W' de 15 letras se crean 2 pedidos porque hay 2 mosaicos 'W'.
La primera solución encontrada con el desglose de puntos:
Editar: explicación
¿Qué hace posible buscar en todo el espacio? Al agregar una nueva palabra, solo tengo en cuenta las palabras que tienen la letra restante más rara. Esta letra debe estar en alguna palabra de todos modos (y una palabra de 15 letras, ya que será una letra que no sea de valor 1, aunque no verifico eso). Así que empiezo con palabras
J, Q, W, W, X, Z
que contienen las que cuentan50, 100, 100, 100, 200, 500
. En los niveles más bajos obtengo más límite porque algunas palabras se eliminan por la falta de letras. Amplitud del árbol de búsqueda en cada nivel:Por supuesto, se obtiene mucho límite al no verificar las soluciones no óptimas (espacios en blanco en palabras de 15 letras o palabras más cortas). Por lo tanto, es una suerte que se pueda lograr la solución 2765 con este diccionario (pero estaba cerca, solo 2 combinaciones de palabras de 15 letras dan un sobrante razonable). Por otro lado, es fácil modificar el código para encontrar combinaciones de puntuación más bajas donde no todas las 10 letras restantes tienen un valor 1, aunque sería más difícil demostrar que esta sería una solución óptima.
También el código muestra el caso clásico de optimización prematura. Esta versión de la
matches
función hace que el código sea solo un 30% más lento:Incluso descubrí cómo hacer que la comparación paralela mágica de bits sea aún más corta que en mi código original (en este caso no se puede usar el mordisco más alto, pero esto no es un problema, ya que solo necesito 26 de los 32 mordiscos):
Pero da cero ventaja.
Editar
Al escribir la explicación anterior, me di cuenta de que la mayor parte del tiempo se dedica a escanear la lista de palabras para aquellas que contienen una letra específica que no está en la
matches
función. Calcular las listas por adelantado dio 10x de aceleración.fuente
Python 2, puntuación:
18402162Este programa primero encuentra la mejor palabra de puntuación disponible con los mosaicos dados (sin usar comodines), luego hace 10000 intentos de incluir palabras aleatorias que cumplan las restricciones de un primer carácter único y tener mosaicos disponibles. Con las constantes actuales, el programa tarda 27 segundos en ejecutarse en mi máquina. El uso de constantes más grandes probablemente encontraría una combinación de palabras con una puntuación más alta.
ACTUALIZACIÓN: ahora utiliza un algoritmo de selección de 2 etapas, por lo que encuentra la mejor de 50 palabras en cada etapa de selección. El puntaje de penalización ahora también se usa en el algoritmo de evaluación.
Incluyo aquí la mejor de algunas carreras:
Tenga en cuenta que no uso los comodines y pago una penalización mayor (debido a la longitud de la palabra). Una mejora futura puede incluir el uso de comodines.
fuente
Recocido simulado (puntaje 2246)
Lamentablemente esto no es determinista. Trataré de arreglar eso y encontrar una semilla determinista que ofrezca un mejor valor.
fuente
Python, puntaje
263826752676268926992717Resultado:
Código:
Explicación:
Búsqueda de profundidad primero que busca en todo el árbol, escogiendo entre las
picks
mejores palabras principales en cada etapa.Ordeno toda la lista de palabras una vez por puntaje al principio. Después de elegir cada palabra, para la siguiente iteración, filtro todas las palabras que ya no son posibles, preservando el orden, por lo que no tengo que ordenar la lista en cada paso. Para tratar con comodines, si existe la posibilidad de que se necesite un comodín, elijo los 10000 candidatos principales, reemplazo las letras que faltan con comodines si es necesario y vuelvo a clasificar según los nuevos puntajes (más bajos).
Este resultado es para
picks=5
y se8m01s
ejecutó en mi máquina de 8 núcleos.fuente
Java 8, puntuación
26412681El programa comienza tomando las 40 mejores palabras. Para cada palabra, encuentra las 40 mejores palabras para acompañar. De las 1600 combinaciones, el programa toma las mejores 40. Para cada combinación, se encuentran las 40 mejores palabras y el ciclo se repite.
Cuando solo quedan unas pocas fichas, las letras restantes se combinan con los dos espacios en blanco para la palabra final.
Actualizar
Aumenté el umbral a las 50 mejores palabras. Además, cada combinación solo agrega palabras que son menos que las que ya están presentes. Esto evita múltiples permutaciones del mismo grupo.
El programa:
fuente
Perl, puntuación: 2655
2630Utilizar:
El uso de espacios en blanco en realidad no da tanto, mientras que ralentiza significativamente la ejecución:
Después de agregar algunas heurísticas:
fuente
Python 3, puntaje 2735
( Nutki logró el puntaje óptimo de 2765, "6 palabras de 15 letras y una palabra de 10 letras que consta de 8 letras de valor 1 y dos espacios en blanco" ).
Utilicé un enfoque codicioso similar al de los demás:
Comienzo con listas de un elemento que contienen las palabras de mayor puntuación que contienen Q's.
En cada paso para cada elemento de la lista, creo
k = 800
nuevas listas con las mejores palabras legales para la lista. De la lista agregada de listas mantengo lask
listas de puntaje más altas y repito el proceso 10 veces.Tenga en cuenta que puede obtener los
k
elementos principales de unan
lista larga en O (n + k * log n) que es O (n) si,k<<n
como en nuestro caso (k = 800, n ~= 250000
), con una cola de montón. Supongo que este método no se usa en otras presentaciones, por lo tanto, losk
valores más pequeños .Uso comodines en el camino si es necesario para las palabras.
El tiempo de ejecución es un par de minutos para
k = 800
. Mayores valores y otras optimizaciones aún no han dado mejores resultados.Resultado:
Experimenté con el producto Descartes de las mejores palabras que contienen Q, J y X ya que estas letras apenas comparten palabras. Mi mejor puntaje con esta estrategia fue 2723 (
DEMISEMIQUAVERS OXYPHENBUTAZONE INTERSUBJECTIVE FLASHFORWARDING KNOWLEDGABILITY RADIOPROTECTION ANALOGUE EA
).El innecesario código de espagueti complicado (con rastros de experimentación con otros métodos):
fuente