Introducción
"¡Muhuhuhahahah!" El científico loco se ríe. "¡Estás atrapado en mi propio pequeño juego!"
Delante de ti hay un pozo mortal de serpientes, mientras que detrás de ti hay un abismo sin fondo. ¡No hay salida, estás atrapado!
"Dos pasos frente a ti es el pozo de la serpiente, y dos pasos detrás de ti es el abismo. Pero! Antes de moverte, DEBES escribir una secuencia de pasos, hacia adelante y hacia atrás, y dármelos. ¡Pero! Porque yo Hoy me siento un poco malvado , puedo obligarte a dar, en lugar de cada paso, cada npaso, ¡donde nsea menor que la longitud de tu secuencia!
Elija sabiamente, ahora ".
¿Cuál es el número máximo de pasos que puede tomar antes de su muerte inminente?
Tarea
La introducción anterior es un giro en la conjetura de discrepancia de Erd , que recientemente se demostró que es verdad (si desea comprender más sobre esto, vaya a este video , de James Grime: le "robé" la pregunta del giro).
La respuesta a la introducción son los 11pasos, pero no profundizaré demasiado con una prueba. La respuesta, si la distancia entre usted y los dos "peligros" fueron 3pasos, es 1160pasos, aunque eso aún no se ha validado correctamente.
Su tarea es hacer un programa que genere la secuencia más larga de pasos que puede lograr para un mayor x, donde xes el número de pasos entre usted y los dos "peligros". Su programa debe tomar una entrada xy generar una secuencia válida para eso x.
Para los propósitos de este desafío, +representa un paso adelante y -representa un paso atrás.
Entonces, una salida para una entrada 2es:
+--+-++--++
Lo que funciona, no importa lo nque elija el científico loco. Para nuestro desafío, x = 5.
NOTA: Este desafío no es un engaño de este desafío o este desafío , ya que mi desafío se enfoca en la salida, a diferencia del código en sí mismo; en otras palabras, no es un desafío de golf de código. Además de eso, estos desafíos se basan en x = 3, que ya tiene un límite superior establecido.
Reglas:
- Todo su programa debe encajar en su respuesta. Sin embargo, si no encaja, proporcione un repositorio adicional de Github o algo similar.
- Puede actualizar tanto su respuesta como su programa, si puede obtener una mejor puntuación al optimizar su código, pero al hacerlo, debe actualizar todo en la lista a continuación.
- En su respuesta, debe tener:
- Su programa, en su totalidad, o un enlace a un repositorio de GH que aloja su código
- La cantidad de pasos generados: este será su puntaje final .
- También debe proporcionar una versión en línea de la secuencia en un Pastebin, o algo similar. Esto es para que podamos verificar su respuesta.
- La hora en que se actualizó por última vez su puntaje final, por lo que no tengo que verificar su historial
- NO puede codificar secuencias de antemano.
- Su programa debe funcionar para todos
x(dondexestá el número de pasos entre usted y el pozo y el abismo), pero solo necesita proporcionar el puntaje correspondientex = 5.
¡La respuesta con la mayor puntuación gana!
fuente
nlos pasos, dondenhay cualquier número por debajo de su tamaño de secuencia.x=5requeriría un avance importante que sería digno de publicación. Tenga en cuenta que el máximo de 1160 parax=3fue probado y publicado en 2014 y no se conocen más valores. .Respuestas:
Óxido, puntaje = 4997216, tiempo = 2017-07-12 00:18 UTC
Esto mejora el mejor resultado que pude encontrar en la literatura, que fue 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, Sobre el problema de discrepancia de Erd , 2014), por un factor de 4.3.
Secuencia de salida de longitud 4997216
Código fuente en GitHub
Corriendo
El programa acepta la máxima discrepancia como argumento (esto es x - 1 en el lenguaje del desafío, para alinearse con la convención matemática más común). Produce salidas incrementales en un formato ligeramente comprimido que se ve así para x = 3:
donde
addsignifica agregar una secuencia de signos al final de la secuencia actual,deletesignifica eliminar cierto número de signos del final de la secuencia actual ylengthafirma la longitud de la secuencia actual. Este esquema evita la producción de muchos gigabytes de resultados intermedios a medida que se descubren secuencias cada vez más largas. Puede extraer el mejor resultado hasta ahora con el siguiente programa Python:Cómo funciona
Aquí hay alrededor de mil líneas de código, por lo que esto solo será una descripción general aproximada.
Limitamos la búsqueda a secuencias completamente multiplicativas (aquellas con f ( a · b ) = f ( a ) · f ( b )), porque eso significa que solo debemos ocuparnos de limitar las sumas parciales para n = 1, y las parciales las sumas para n ≥ 2 satisfarán el mismo límite automáticamente.
Para cualquier subcadena f ( i + 1), ..., f ( j ) de una secuencia de signos parcialmente asignada (por lo que cada elemento es '+', '-' o desconocido), defina peligro + ( i , j ) como dos veces el número de '+' s menos la longitud j - i (por conveniencia, permitimos que i sea tan pequeño como - x + 2 y supongamos que f (- x + 3) = ⋯ = f (0) = '+' para este propósito). Definir peligro - ( i , j ) de manera similar. Entonces el límite de sumas parciales para n= 1 es equivalente a la condición de que siempre que i ≡ j ≡ x (mod 2), peligro + ( i , j ) ≤ x - 2 y peligro - ( i , j ) ≤ x - 2.
Creamos una estructura de datos incremental que admite consultas de tiempo constante para la subcadena con mayor peligro, con actualizaciones de tiempo logarítmicas. Funciona asociando cuatro valores:
con cada cadena de longitud 2, cualquier otra cadena de longitud 4, cada cuarta cadena de longitud 8, y así sucesivamente. Los valores asociados con una cadena más larga se pueden calcular en tiempo constante a partir de los valores asociados con sus dos mitades.
Esta estructura, aumentada con cierta información auxiliar, nos permite realizar propagación de restricciones y detección de conflictos en secuencias parciales muy rápidamente. Lo usamos para hacer una búsqueda similar a CDCL , con propagación de unidades, niveles de decisión y retroceso no cronológico (pero sin aprendizaje de cláusulas, por ahora), para secuencias completas de longitudes cada vez más largas.
En cada paso de búsqueda, hacemos una conjetura para el primer signo sin asignar. La heurística utilizada para hacer esta suposición es muy importante para evitar muchos retrocesos; usamos f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Resultados
Las búsquedas de discrepancia 0, 1 y 2 encuentran de inmediato las secuencias óptimas completamente multiplicativas de longitud 0, 9 y 246.
La búsqueda de discrepancia 3 se atasca en segundos en 41319, que está bastante lejos de la secuencia óptima multiplicativa óptima conocida de longitud 127645 encontrada por Le Bras et al., 2014 (y una extensión no multiplicativa muy ligeramente más larga de longitud 130000 encontrada poco después) ), pero mucho mejor que la secuencia más conocida antes de la longitud 17000 .
La búsqueda de discrepancia 4 mejora la secuencia más larga de manera más o menos continua durante aproximadamente cinco minutos hasta que se atasca en 4997216. La secuencia mejor conocida previamente de longitud 1148805 = 9 · 127645 se amplió de la secuencia de discrepancia 3 reemplazando cada signo s con + - - + - ++ - s . Por lo que puedo decir, las secuencias de este tiempo son demasiado difíciles para que un solucionador general de SAT mejore razonablemente directamente (¡pero tal vez usted, querido lector, pueda demostrar que estoy equivocado!).
Espero que necesite agregar algún tipo de cláusula de aprendizaje a mi programa para superar estas barreras.
La secuencia como un mapa de bits de 2187 × 2285
(Haga clic para ver en resolución completa).
fuente
Haskell , puntaje = 9020, tiempo = 2017-06-09 00:52 UTC
Pruébalo en línea!
Este puntaje (9 n - 1 - 1) ⋅11 / 8 para todos los n . Aquí están las primeras salidas:
fuente