Su tarea es escribir un programa o función que pueda llenar un rectángulo dado con números primos. El width
y height
del rectángulo será la entrada. La salida debe ser una lista de height
cadenas que consta de width
dígitos y espacios. Cada secuencia de dígitos horizontal (de izquierda a derecha) y vertical (de arriba a abajo) (delimitada por espacios o bordes de rectángulo) de longitud 2 o mayor debe ser un número primo. Cada número primo se puede usar solo una vez. Los ceros iniciales no están permitidos. Una nueva línea final es opcional en la salida.
Ejemplo:
With input (5, 3) a valid output would be:
11 13
7 0
173
which scores 11, 13, 173, 17, 103 for a total of 5 points.
Puntuación:
El tamaño del rectángulo para la puntuación será 80, 60
. Cada número primo horizontal o vertical de longitud 2 o más en el rectángulo obtiene un punto. La respuesta con más puntos gana. En caso de empate, la primera respuesta ganará.
Reglas:
- Las lagunas estándar están prohibidas.
- Su programa no debe estar diseñado para el
80, 60
tamaño. Si sospecho que una respuesta está optimizada para este tamaño, me reservo el derecho de cambiar el tamaño del rectángulo hasta100, 100
. - Los números primos utilizados deben ser números primos reales (no probabilísticos o pseudoprimos). Su programa puede calcular o verificar números en tiempo de ejecución, o tenerlos codificados. El método para encontrar los números primos no es una parte importante del desafío.
- Su respuesta debe incluir el texto de salida y su código. Si su programa es demasiado grande, puede incluir un código de algoritmo central, con una pequeña explicación.
Editar: se aclaró que se necesitaban números primos reales. Tamaño máximo de rectángulo agregado.
Edición 2: se aclaró qué código debe publicarse.
fuente
Respuestas:
Clingo con Python,
160016891740 primosEnfoque
Genero un problema de satisfacción de restricciones gigantes y lo resuelvo utilizando un solucionador de satisfacción de la fuerza industrial. Se ha invertido mucha magia en hacer que los solucionadores de satisfacción sean relativamente rápidos (aunque el problema es NP-complete en general), pero afortunadamente no tengo que preocuparme por esa parte.
Específicamente, arreglo las posiciones de los dígitos en un patrón diseñado para el empaquetado cercano de números de 4 y 5 dígitos, con números ocasionales de 2 y 3 dígitos en el límite, y agrego restricciones que dicen que cada número es un primo distinto. El empaque actual utiliza una gran fracción de todos los primos de 4 dígitos (854 de 1061).
Código
Uso
Advertencia: a 80 × 60, esto toma alrededor de 8 minutos y usa 3 GB de memoria. Es posible que desee comenzar con tamaños más pequeños si solo desea verlo en ejecución.
Salida (80 × 60, 1740 primos):
fuente
Smalltalk, 1098 primos
En primer lugar, una buena pregunta difícil, como lo demuestra la falta de respuestas no triviales hasta ahora.
Tenía una solución para cocinar en el trabajo, pero tuve que esperar el fin de semana largo para tener tiempo de limpiarlo un poco. Aun así, es bastante "pesado", así que disculpe la longitud de esta respuesta; afortunadamente, esta no es una pregunta de código de golf. Hubo muchas pequeñas trampas en el camino, pero estoy bastante seguro de que ahora está libre de errores, aunque hay mucho espacio para mejoras y ajustes.
Idioma
Mi lenguaje de elección para este tipo de cosas es Smalltalk : la depuración superior y la capacidad de probar como código supera cualquier otra cosa que conozco. Además, incluso los no codificadores pueden leerlo y comprender los conceptos básicos de lo que está sucediendo. Limité el código a continuación a la parte interesante, porque pensé que el enfoque y los resultados serían más interesantes que el código repetitivo, pero aquí se pega un archivo del código completo si alguien quiere probarlo (solo guarde como
*.st
y archívelo desde un explorador de archivos en Pharo). Utilicé Pharo 4.0, que es FOSS y se puede descargar de pharo.org para Win / Mac / Linux. También me complace pegar el código completo aquí, pero tomé el "debería incluir el texto de salida y su código" como una sugerencia: avíseme si me equivoco.Enfoque
Entonces, pensé, ¿qué pasaría si pudieras comenzar en el medio, meter tantos números primos largos como puedas en la caja y avanzar desde allí? Comencemos con un
Box
objeto, que contenga unamatrix
de caracteres, y luego usemos unStuffer
objeto para tratar de llenarlo encontrando el mejorInsertion
(otro objeto) para cada punto de la matriz y para cada primo (comenzando con los largos). Pharo tiene clases agradablesMatrix
yPoint
con un montón de métodos útiles (aunque la forma matricial de usar la notación de fila mayor en comparación con el uso de coordenadas xy de puntos puede ser un poco confuso si no tienes cuidado).Los pasos básicos de mi algoritmo son:
Stuffer
instancia para dimensiones dadas.Configurable
Para la matriz a continuación, utilicé 80x60, números primos por debajo de 20,000 (ya que la longitud combinada de esos es apenas inferior a 10,000 caracteres, es decir, el máximo para una caja rellena, aunque no válida, 100x100) y, después de algunos experimentos, la siguiente clasificación para la
each
inserción :donde
accidentalPrimes
se crean los primos perpendiculares "accidentalmente" cuando se inserta entre primos vecinos, ynumberOfOverlaps
es cuántos caracteres se sobrescriben (por ejemplo, al agregar un3
al final de11
insertar113
). Inicialmente lo pesé másaccidentalPrimes
, pero obtuve algunos primos más en la caja al hacerlo de esta manera, no estoy completamente seguro de por qué (no dude en probar / ajustar).Resultado
Esta matriz contiene 1098 primos, que es una "carga" de aproximadamente el 70%.
Estos son los primos (
box primesUsed asSortedCollection printString
):Como puede ver, algunos de los primos "accidentales" se alargan bastante ... 20 dígitos para el más largo. :-)
Detalles
Para comprender cómo funciona, aquí está la salida de los primeros pasos: insertar
19997
primero (si mira en el medio de la matriz grande, verá19997
allí también), luego hacia abajo en la lista donde hay espacio en el 5x5 box (>
significa que la inserción va hacia la derecha,v
significa que va hacia abajo; cualquier cosa que{}
esté adentro se agrega primos accidentalmente:En la inserción inmediatamente anterior, el cuadro se convierte en un 7x7 y se llena con el contenido de 5x5 antes de que ocurra la siguiente inserción. También vuelvo a calcular los números primos utilizados en este punto, porque algunos se "liberan" debido a la sobrescritura (
11
se insertó, pero luego se sobrescribió113
).Código
Estas son las partes más relevantes del código:
Clase Stuffer
Lado de la clase
Lado de la instancia
Clase de caja
Lado de la instancia
Colección
Ah, y agregué un método al lado de la instancia
Collection
, solo por conveniencia:Corriendo
Para ejecutar mi código, todo lo que necesito hacer es seleccionar el siguiente código en un espacio de trabajo ("área de juegos" en Pharo) o en cualquier panel de texto, y "hacerlo" en el menú contextual:
El resto del código es relativamente aburrido.
Como dije, hay margen de mejora, pero a 80x60, cada ejecución lleva más de 3 minutos en mi máquina. Claramente, el rendimiento no ha sido mi preocupación, pero hay MUCHOS primos volando. Este seguro ha sido un desafío interesante. :-)
fuente
Javascript, puntaje 659
Casi ciertamente subóptima.
Resultados para 30x30:
Y para el caso 60x60:
fuente