Johnny está tratando de crear crucigramas, pero tiene dificultades para hacer que las palabras coincidan entre sí.
Se le han ocurrido varios rectángulos de palabras simples: es decir, grupos de palabras que forman un rectángulo donde todas las rutas horizontales y verticales forman una palabra.
//2x2
PA
AM
//2x3
GOB
ORE
//3x3
BAG
AGO
RED
//3x4
MACE
AGES
WEES
Sin embargo, para hacer un buen rompecabezas, necesita algunos rectángulos de palabras que sean algo más grandes que 3x4. En lugar de agonizar por las cartas de arreglo durante horas, Johnny preferiría tener un programa que haga esto por él, y en la menor cantidad de caracteres posible, porque los bloques largos de código son extremadamente intimidantes para programadores casuales como Johnny.
Dado
- un diccionario de archivos de texto donde las palabras están separadas por nuevas líneas en orden alfabético,
- entrada que especifica el número de filas y columnas en el rectángulo de palabras (que se puede proporcionar, sin embargo, es más conveniente en el lenguaje de programación que elija)
generar al menos una palabra rectángulo. Si no es posible generar un rectángulo de palabras con el léxico y las dimensiones dadas, el programa no necesita tener un comportamiento definido. No es necesario que el programa pueda generar rectángulos que contengan más de 64 letras o que tengan dimensiones superiores a 8 en cualquier dirección. El programa debería poder completarse en un tiempo razonable, digamos, en treinta minutos o menos.
EDITAR: Si está haciendo un rectángulo NxN, puede usar un archivo de diccionario más pequeño que solo contiene palabras que tienen una longitud de N letras.
Respuestas:
Haskell, 586 caracteres
Se invoca proporcionando 3 argumentos: número de filas, número de columnas, número de soluciones; y la lista de palabras se acepta en
stdin
:Como puede ver, 7 × 7 corre relativamente rápido. Todavía cronometraje 8 × 8 y 7 × 6 ...
Sería 9 caracteres más cortos para eliminar el argumento de la cantidad de soluciones y solo producir todas las soluciones, pero luego se hace imposible el tiempo.
Map String a
es más lento que un árbol deMap Char a
...Vector
es mucho más rápida que el uso de un simpleMap
. ¿Por qué hacer esto? Porque creo que una solución más cercana al objetivo de 8x8 en menos de ½ hora es preferible a una solución más corta.fuente
--make
después de ghc) con la lista de palabras publicada en la pregunta, obtengo palabras que no están en la lista, como "zymesz" y "youthy".Python, 232 caracteres
Sin embargo, solo puede manejar hasta 6x6 en el límite de 1/2 hora.
fuente
3,3
pero sus palabras de retorno3x4
+2
s por+1
s.\r
dew
, y en Linux tengo archivo convertido a formato Unix, por lo tanto no funcionaba.Java (1065 bytes)
Lejos de ser el más corto, pero creo que es lo más cercano a cumplir con las limitaciones de tiempo. Ahorré 14 bytes asumiendo que el archivo de entrada se ha filtrado a palabras de la longitud correcta; en mi netbook, si alimentas todo,
words.txt
entonces pasa el primer minuto preprocesándolo, descartando la mayor parte de lo que produce, y luego toma solo unos 20 segundos para resolver 7x7. En mi escritorio, hace todo en menos de 15 segundos, dando:Lo dejé funcionar durante más de 50 horas sin encontrar una solución para 8x7 u 8x8. Las palabras de 8 letras parecen ser un límite crítico para este problema: simplemente se cierne a la mitad sin avanzar mucho.
El enfoque utilizado es de pivote completo y una heurística basada en el número de posibles compleciones horizontales multiplicado por el número de posibles compleciones verticales. Por ejemplo, si tenemos cuadrícula intermedia
entonces le damos a la esquina superior izquierda un valor heurístico de
count(aean*)count(aa***) + count(bean*)count(ba***) + ... + count(zean*)count(za***)
. De todas las celdas, elegimos la que tiene el valor heurístico más pequeño (es decir, la más difícil de satisfacer), y luego trabajamos a través de las letras en orden descendente de la cantidad que contribuyeron al valor heurístico de esa celda (es decir, comenzando con la más probable de tener éxito )fuente
F#
Solución de retroceso, pero voy a optimizar el espacio de búsqueda más tarde.
fuente
awk, 283
(puede que sea necesario agregar 14 para las banderas de entrada de parámetros)
Llame con, por ejemplo,
awk -v x=2 -v y=2
...Encuentre la primera coincidencia e imprímala (283 caracteres):
Encuentra el número de partidos (245 caracteres, mucho más lento):
Para ambos programas (por supuesto, más para el recuento de soluciones), el tiempo de ejecución supera con creces los 30 minutos para algunos valores de x e y.
Solo como una cuestión de interés, aquí está el conteo de palabras para cada longitud de palabra:
fuente