Al trabajar en Boggle Polyglot no palindrómico , me pareció bastante tedioso empacar los códigos de la manera más eficiente posible en el tablero Boggle, incluso con solo dos cadenas. Pero somos programadores, ¿verdad? Sabemos automatizar cosas.
Dada una lista de cadenas, debe generar un tablero de Boggle en el que se pueda encontrar cada una de esas cadenas (independientemente de las demás). El desafío es hacer que el tablero de Boggle sea lo más pequeño posible. Como es (con suerte) una tarea bastante difícil, este es un desafío de código : no hay requisitos para la optimización, el desafío es hacerlo lo mejor que pueda.
Reglas
- El tablero de Boggle será rectangular y contendrá solo letras mayúsculas. Por lo tanto, las cadenas de entrada también contendrán solo letras mayúsculas.
- Se aplican las reglas habituales de Boggle: una cadena es parte del tablero si, comenzando en cualquier lugar, puede encontrar la cadena moviéndose repetidamente a caracteres adyacentes (horizontal, vertical o diagonal). Para formar una sola cadena, no puede usar ninguna celda del tablero más de una vez. Sin embargo, los caracteres pueden reutilizarse entre diferentes cadenas.
- Tiene 30 minutos para procesar los datos de prueba, y su código no debe usar más de 4 GB de memoria. Le daré un poco de margen de maniobra en el límite de memoria, pero si su programa usa constantemente más de 4 GB o picos significativamente por encima, lo descalificaré (temporalmente).
- Probaré todas las presentaciones en mi propia máquina, que está ejecutando Windows 8. Tengo una VM de Ubuntu, pero si tengo que probar eso, no podrá hacer tanto uso de los 30 minutos como no. Incluya un enlace a un intérprete / compilador gratuito para su idioma elegido, así como instrucciones sobre cómo compilar / ejecutar su código.
- Su puntaje será del tamaño del tablero de Boggle para los datos de prueba a continuación (sin contar las nuevas líneas). En el caso de un empate (por ejemplo, porque varias personas lograron producir una solución óptima), el ganador será el envío que produzca esta solución óptima más rápido.
- No debe optimizar su código específicamente para los datos de prueba. Si sospecho que alguien lo está haciendo, me reservo el derecho de generar nuevos datos de prueba.
Ejemplo
Dadas las cuerdas
FOO
BAR
BOOM
Una vez podría ponerlos trivialmente en un tablero Boggle 4x3:
FOOX
BARX
BOOM
Al hacer uso del hecho de que las cadenas no tienen que ser rectas, podemos comprimirlo a 5x2:
BORFO
OMABO
Pero podemos hacerlo aún más pequeño reutilizando caracteres entre diferentes cadenas y ajustando las cadenas en 4x2:
FOOM
BARX
Ahora B
se usa para ambos BOOM
y BAR
, y OO
se usa para ambos BOOM
y FOO
.
Datos de prueba
Su envío será probado en las siguientes 50 cadenas. Para fines de prueba, simplemente puede usar subconjuntos más pequeños de estos datos que luego deberían ejecutarse más rápidamente. Creo que el límite inferior absoluto para estos datos de prueba es una placa con 120 caracteres, aunque esto no es necesariamente posible.
T
WP
GVI
CIHM
EGWIV
QUTYFZ
LWJVPNG
XJMJQWSW
JLPNHFDUW
SWMHBBZWUG
XVDBMDQWDEV
TIUGAVZVUECC
IWDICFWBPSPQR
MMNWFBGMEXMSPY
YIHYXGJXKOUOIZA
BZSANEJNJWWNUJLJ
XTRMGOVPHVZYLLKKG
FLXFVVHNTWLMRRQYFQ
VZKJRAFQIYSBSXORTSH
FNQDIGCPALCHVLHDNZAV
GEAZYFSBSWCETXFKMSWLG
KWIZCEHVBDHEBGDGCJHOID
SKMQPHJAPDQKKHGTIPJCLMH
ZSFQDNYHALSUVWESQVVEUIQC
HXHBESUFCCECHNSTQGDUZPQRB
DSLXVHMOMLUXVHCNOJCBBRPVYB
DVTXKAOYYYRBVAVPSUAOYHIPPWN
PJAIYAWHMTNHTQDZDERPZYQEMLBZ
SYNSHJNOIWESMKWTBIANYUAUNRZOS
WADGUKIHUUFVRVUIBFUXQIOLAWIXAU
LGLXUFIXBEPSOFCKIAHXSHVKZPCXVPI
LIUYFHITTUYKDVQOZPNGZLWOZSRJTCTZ
IZDFTFFPNEBIYGVNTZHINICBXBXLBNBAL
BSKQNTPVUAVBXZGHVZCOUCRGCYISGFGYAS
DPGYYCIKDGCETXQOZGEQQLFQWACMVDTRYAT
RQDNIPGUHRYDRVHIPJLOWKBXMIBFAWCJGFMC
PFKOAGEQLXCMISSVEARWAPVYMRDCLSLPJOMQQ
EQPCNHQPTWABPFBVBXHQTFYELPNMNCWVKDDKGR
RAHTJMGIQJOJVWJBIHVRLJYVCSQJCKMEZRGRJMU
SZBJBPQYVYKDHAJHZMHBEWQEAQQKIEYCFACNLJBC
ANVDUCVXBPIZVRAXEBFEJOHSYKEKBIJELPIWEYXKH
DJUNPRLTISBFMGBEQNXSNUSOGDJNKESVKGAAMTIVXK
TZPUHDSHZFEURBNZTFBKXCDPYRELIAFMUWDIQTYWXGU
FJIKJROQSFSZUCGOOFJIEHBZREEUUSZWOLYFPCYHUSMR
TPMHJEAWVAJOCSDOPMQMHKRESBQSTRBXESYGCDVKLFOVS
ABJCCDJYMYDCYPZSGPGIAIKZQBYTZFDWYUZQBOESDSDGOY
IIHKTVPJNJDBCBOHCIYOPBKOVVKGNAKBDKEEKYIPRPHZOMF
IABGEPCSPNSMLVJBSGLRYNFSSYIALHWWAINTAVZAGJRVMDPW
GFMFVEFYJQJASVRIBLULUEHPMZPEXJMHIEMGJRMBLQLBDGTWT
YPWHLCVHQAVKVGHMLSOMPRERNHVYBECGCUUWTXNQBBTCMVTOVA
Verificador
Puede usar el siguiente fragmento de pila para verificar si un tablero de Boggle contiene todas las cadenas en una lista dada. Porté el código de búsqueda de Boggle de la respuesta de edc65 aquí . Avísame si algo parece defectuoso.
fuente