Historia
Mi empresa envía un boletín semanal a todos los miembros de la empresa. En estos boletines se incluye un acertijo, junto con un saludo a quien en la empresa fue el primero en enviar un correo electrónico / proporcionar una solución al enigma de la semana pasada. La mayoría de estos acertijos son bastante triviales, y honestamente bastante aburridos para una empresa de tecnología, pero hubo uno, varios meses atrás, que me llamó la atención.
El acertijo original:
Dada la forma a continuación:
Tiene los números naturales del 1 al 16. Ajústelos a todos en esta forma, de modo que todas las filas y columnas contiguas sumen 29.
Por ejemplo, una de esas soluciones a este rompecabezas (que fue la solución "canónica" que envié al boletín) fue la siguiente:
Sin embargo, en el curso de resolverlo, encontré información bastante interesante:
- Hay significativamente más soluciones que solo esa; de hecho, hay 9.368 soluciones.
- Si expande el conjunto de reglas para requerir solo que las filas y columnas sean iguales entre sí, no necesariamente 29, obtendrá 33,608 soluciones:
- 4.440 soluciones por una suma de 27.
- 7.400 soluciones por una suma de 28.
- 9.368 soluciones por una suma de 29.
- 6.096 soluciones por una suma de 30.
- 5.104 Soluciones por un total de 31.
- 1.200 soluciones por una suma de 32.
Así que yo y mis compañeros de trabajo (aunque principalmente solo mi gerente, ya que él era la única persona que no era yo con habilidades de programación de "Propósito general") nos embarcamos en un desafío que duró la mayor parte del mes: tuvimos otro trabajo real. obligaciones relacionadas a las que teníamos que atender, para tratar de escribir un programa que encontrara todas las soluciones de la manera más rápida posible.
Estadísticas originales
El primer programa que escribí para resolver el problema simplemente verificó soluciones aleatorias una y otra vez, y se detuvo cuando encontró una solución. Si ha realizado un análisis matemático sobre este problema, probablemente ya sepa que esto no debería haber funcionado; pero de alguna manera tuve suerte, y el programa tardó solo un minuto en encontrar una solución única (la que publiqué anteriormente). Las ejecuciones repetidas del programa a menudo tomaron tanto como 10 o 20 minutos, por lo que obviamente esta no era una solución rigurosa para el problema.
Me cambié a una Solución Recursiva que iteraba a través de cada permutación posible del rompecabezas, y descarté muchas soluciones a la vez al eliminar sumas que no estaban sumando. Es decir, si la primera fila / columna que estaba comparando ya no fuera igual, podría dejar de verificar esa rama inmediatamente, sabiendo que nada más permutado en el rompecabezas cambiaría eso.
Usando este algoritmo, obtuve el primer éxito "adecuado": el programa podía generar y escupir todas las 33,608 soluciones en aproximadamente 5 minutos.
Mi gerente tenía un enfoque diferente: sabiendo en base a mi trabajo que las únicas soluciones posibles tenían sumas de 27, 28, 29, 30, 31 o 32, escribió una solución multiproceso que verificaba las sumas posibles solo para esos valores específicos. Logró ejecutar su programa en solo 2 minutos. Entonces volví a repetir; Calculé todas las sumas posibles de 3/4 dígitos (al inicio del programa; se cuenta en el tiempo de ejecución total) y utilicé la "suma parcial" de una fila para buscar el valor restante en función de una fila completada previamente, en lugar de probando todos los valores restantes, y redujo el tiempo a 72 segundos. Luego, con un poco de lógica de subprocesos múltiples, lo reduje a 40 segundos. Mi gerente se llevó el programa a casa, realizó algunas optimizaciones sobre cómo se ejecutó el programa y lo redujo a 12 segundos. Reordené la evaluación de las filas y columnas,
Lo más rápido que obtuvimos nuestros programas después de un mes fue de 0,15 segundos para mi gerente y de 0,33 segundos para mí. Sin embargo, terminé afirmando que mi programa era más rápido, ya que el programa de mi gerente, aunque encontró todas las soluciones, no las imprimió en un archivo de texto. Si agregaba esa lógica a su código, a menudo tomaba más de 0.4-0.5 segundos.
Desde entonces hemos permitido que nuestro desafío intrapersonal subsista, pero, por supuesto, la pregunta sigue siendo: ¿se puede hacer este programa más rápido?
Ese es el desafío que les voy a plantear.
Su desafío
Los parámetros con los que trabajamos relajaron la regla de "suma de 29" para ser "todas las sumas de filas / columnas iguales", y voy a establecer esa regla para ustedes también. El desafío, por lo tanto, es: escribir un programa que encuentre (¡e imprima!) Todas las soluciones a este acertijo en el menor tiempo posible. Voy a establecer un límite en las soluciones enviadas: si el programa tarda más de 10 segundos en una computadora relativamente decente (<8 años), probablemente sea demasiado lento para contarlo.
Además, tengo algunas bonificaciones para el rompecabezas:
- ¿Puede generalizar la solución para que funcione para cualquier conjunto de 16 números, no solo
int[1,16]
? La puntuación de tiempo se evaluaría en función del conjunto de números de solicitud original, pero se pasaría por esta ruta de código. (-10%) - ¿Puedes escribir el código de una manera que maneje y resuelva con gracia con números duplicados? ¡Esto no es tan sencillo como parece! Las soluciones que son "visualmente idénticas" deberían ser únicas en el conjunto de resultados. (-5%)
- ¿Puedes manejar números negativos? (-5%)
También puede intentar generar una solución que maneje los números de coma flotante, pero, por supuesto, no se sorprenda si eso falla por completo. Sin embargo, si encuentra una solución sólida, ¡podría valer una gran ventaja!
Para todos los efectos, las "rotaciones" se consideran soluciones únicas. Entonces, una solución que es solo una rotación de una solución diferente cuenta como su propia solución.
Los IDEs que tengo trabajando en mi computadora son Java y C ++. Puedo aceptar respuestas de otros idiomas, pero es posible que también deba proporcionar un enlace para obtener un entorno de tiempo de ejecución fácil de configurar para su código.
fuente
Respuestas:
C - cerca de 0.5 segundos
Este programa muy ingenuo da todas las soluciones en medio segundo en mi computadora portátil de 4 años. Sin subprocesos múltiples, sin hashing.
Windows 10, Visual Studio 2010, CPU core I7 64 bit
Probar en línea en ideone
fuente
int inuse[16];
por soloint inuse;
y luego usar operadores bit a bit para manipularlo. No parece aumentar la velocidad que es mucho, pero ayuda un poco.dumbbench --precision=.01 -vvv --initial=500 ./solve
C ++ - 300 milisegundos
Por solicitud, agregué mi propio código para resolver este rompecabezas. En mi computadora, registra un promedio de 0.310 segundos (310 milisegundos) pero, dependiendo de la variación, puede ejecutarse tan rápido como 287 milisegundos. Muy rara vez veo que se eleve por encima de 350 milisegundos, generalmente solo si mi sistema está bloqueado con una tarea diferente.
Estos tiempos se basan en el autoinforme utilizado en el programa, pero también probé usando un temporizador externo y obtuve resultados similares. Los gastos generales en el programa parecen agregar unos 10 milisegundos.
Además, mi código no bastante manejar duplicados correctamente. Puede resolver su uso, pero no elimina las soluciones "visualmente idénticas" del conjunto de soluciones.
fuente
0.1038s +/- 0.0002
Y este es el momento de su código con salida simplificada:0.0850s +/- 0.0001
Entonces, puede guardar ~ 18 ms, al menos en mi máquina. EjecutéProlog - 3 minutos
Este tipo de rompecabezas parece un caso de uso perfecto para Prolog. Entonces, codifiqué una solución en Prolog! Aquí está:
Lamentablemente, no es tan rápido como esperaba. Quizás alguien más versado en programación declarativa (o Prolog específicamente) pueda ofrecer algunos consejos de optimización. Puede invocar la regla
puzzle
con el siguiente comando:Pruébelo en línea aquí . Puede sustituir cualquier número en lugar de
29
s en el código para generar todas las soluciones. Tal como está, las 29 soluciones se encuentran en aproximadamente 30 segundos, por lo que encontrar todas las soluciones posibles debe ser de aproximadamente 3 minutos.fuente