Esta es la secuencia A054261
El ésimo número de contención prime es el número más bajo que contiene los primeros números primos como subcadenas. Por ejemplo, el número es el número más bajo que contiene los primeros 3 primos como subcadenas, lo que lo convierte en el tercer número de contención de primos.
Es trivial descubrir que los primeros cuatro números de contención primos son , , y , pero luego se vuelve más interesante. Como el próximo número primo es 11, el siguiente número de contención primo no es , pero es ya que se define como el número más pequeño con la propiedad.
Sin embargo, el verdadero desafío viene cuando vas más allá de 11. El siguiente número de contención principal es . Tenga en cuenta que en este número, las subcadenas 11
y 13
se superponen. El número 3
también se superpone con el número 13
.
Es fácil demostrar que esta secuencia está aumentando, ya que el siguiente número debe cumplir con todos los criterios del número anterior y tener una subcadena más. Sin embargo, la secuencia no está aumentando estrictamente, como lo demuestran los resultados para n=10
y n=11
.
Reto
Su objetivo es encontrar tantos números de contención primos como sea posible. Su programa debería generarlos de manera ordenada, comenzando con 2 y subiendo.
Reglas
- Se le permite codificar números primos.
- No está permitido codificar números de contención primos (
2
es la única excepción), o cualquier número mágico que haga que el desafío sea trivial. Por favor, ser amable. - Puede usar cualquier idioma que desee. Incluya una lista de comandos para preparar el entorno para ejecutar el código.
- Puede usar tanto la CPU como la GPU, y puede usar subprocesos múltiples.
Tanteo
La puntuación oficial será de mi computadora portátil (Dell XPS 9560). Su objetivo es generar tantos números de contención primarios como sea posible en 5 minutos.
Especificaciones
- Intel Core i7-7700HQ de 2,8 GHz (aumento de 3,8 GHz) 4 núcleos, 8 hilos.
- 16 GB de RAM DDR4 a 2400 MHz
- NVIDIA GTX 1050
- Linux Mint 18.3 de 64 bits
Los números encontrados hasta ahora, junto con el último primo agregado al número:
1 => 2 ( 2)
2 => 23 ( 3)
3 => 235 ( 5)
4 => 2357 ( 7)
5 => 112357 ( 11)
6 => 113257 ( 13)
7 => 1131725 ( 17)
8 => 113171925 ( 19)
9 => 1131719235 ( 23)
10 => 113171923295 ( 29)
11 => 113171923295 ( 31)
12 => 1131719237295 ( 37)
13 => 11317237294195 ( 41)
14 => 1131723294194375 ( 43)
15 => 113172329419437475 ( 47)
16 => 1131723294194347537 ( 53)
17 => 113172329419434753759 ( 59)
18 => 2311329417434753759619 ( 61)
19 => 231132941743475375961967 ( 67)
20 => 2311294134347175375961967 ( 71)
21 => 23112941343471735375961967 ( 73)
22 => 231129413434717353759619679 ( 79)
23 => 23112941343471735359619678379 ( 83)
24 => 2311294134347173535961967837989 ( 89)
25 => 23112941343471735359619678378979 ( 97)
26 => 2310112941343471735359619678378979 (101)
27 => 231010329411343471735359619678378979 (103)
28 => 101031071132329417343475359619678378979 (107)
29 => 101031071091132329417343475359619678378979 (109)
30 => 101031071091132329417343475359619678378979 (113)
31 => 101031071091131272329417343475359619678378979 (127)
32 => 101031071091131272329417343475359619678378979 (131)
33 => 10103107109113127137232941734347535961967838979 (137)
34 => 10103107109113127137139232941734347535961967838979 (139)
35 => 10103107109113127137139149232941734347535961967838979 (149)
36 => 1010310710911312713713914923294151734347535961967838979 (151)
Gracias a Ardnauld, Ourous y japh por ampliar esta lista.
Tenga en cuenta que n = 10
y n = 11
son el mismo número, ya que es el número más bajo que contiene todos los números , pero también contiene .
Como referencia, puede usar el hecho de que el script original de Python que escribí para generar esta lista anterior calcula los primeros 12 términos en aproximadamente 6 minutos.
Reglas adicionales
Después de que llegaron los primeros resultados, me di cuenta de que hay una buena posibilidad de que los mejores resultados terminen teniendo el mismo puntaje. En caso de empate, el ganador será el que tenga el menor tiempo para generar su resultado. Si dos o más respuestas producen sus resultados igualmente rápido, simplemente será una victoria empatada.
Nota final
El tiempo de ejecución de 5 minutos solo se pone para garantizar una puntuación justa. Me interesaría mucho ver si podemos impulsar aún más la secuencia OEIS (en este momento contiene 17 números). Con el código de Ourous, he generado todos los números hasta n = 26
, pero planeo dejar que el código se ejecute por un período de tiempo más largo.
Marcador
- Python 3 + Herramientas OR de Google : 169
- Scala : 137 (no oficial)
- Solucionador Concorde TSP : 84 (no oficial)
- Conjunto C ++ (GCC) + x86 : 62
- Limpio : 25
- JavaScript (Node.js) : 24
fuente
n=11
trivial, ya que solo tiene que verificar quen=10
también satisfaga la nueva condición. También argumentaría que la codificación dura solo ayuda hastan=17
, ya que no se conocen números más allá de ese punto por lo que he podido averiguar.[1,22,234,2356,112356,113256,1131724,113171924,1131719234,113171923294,113171923294,1131719237294]
e iniciar una búsqueda de cada unoRespuestas:
Python 3 + Google OR-Tools , puntaje 169 en 295 segundos (puntaje oficial)
Cómo funciona
Después de descartar los primos redundantes contenidos en otros primos, dibuje un gráfico dirigido con una arista desde cada primo a cada uno de sus sufijos, con distancia cero, y una arista a cada primo desde cada uno de sus prefijos, con la distancia definida por el número de dígitos agregados . Buscamos el primer camino más corto lexicográficamente a través del gráfico comenzando en el prefijo vacío, pasando por cada primo (pero no necesariamente a través de cada prefijo o sufijo), y terminando en el sufijo vacío.
Por ejemplo, aquí están los bordes de la ruta óptima ε → 11 → 1 → 13 → 3 → 31 → 1 → 17 → ε → 19 → ε → 23 → ε → 29 → ε → 5 → ε para n = 11, correspondiente a la cadena de salida 113171923295.
En comparación con la reducción directa al problema del vendedor ambulante , tenga en cuenta que al conectar los números primos indirectamente a través de estos nodos de sufijo / prefijo adicionales, en lugar de directamente entre sí, hemos reducido drásticamente la cantidad de bordes que debemos tener en cuenta. Pero dado que los nodos adicionales no necesitan atravesarse exactamente una vez, esto ya no es una instancia de TSP.
Utilizamos el solucionador de restricciones incremental CP-SAT de Google OR-Tools, primero para minimizar la longitud total de la ruta, luego para minimizar cada grupo de dígitos agregados en orden. Inicializamos el modelo solo con restricciones locales: cada primo precede a un sufijo y tiene éxito un prefijo, mientras que cada sufijo / prefijo precede y tiene éxito el mismo número de primos. El modelo resultante podría contener ciclos desconectados; Si es así, agregamos restricciones de conectividad adicionales dinámicamente y volvemos a ejecutar el solucionador.
Código
Resultados
Aquí están los primeros 1000 números de contención primos , calculados en 1½ días en un sistema de 8 núcleos / 16 hilos.
fuente
Conjunto C ++ (GCC) + x86, puntaje
323662 en 259 segundos (oficial)Resultados calculados hasta ahora. Mi computadora se queda sin memoria después
65
.Todos estos están de acuerdo con la salida del solucionador basado en Concorde , por lo que tienen una buena posibilidad de ser correctos.
Registro de cambios:
Cálculo incorrecto para la longitud de contexto necesaria. La versión anterior era 1 demasiado grande y también tenía un error. Puntuación:
3234Se agregó optimización de grupo de contexto igual. Puntuación:
3436Revisó el algoritmo para usar cadenas libres de contexto correctamente, además de algunas otras optimizaciones. Puntuación:
3662Se agregó una reseña adecuada.
Se agregó la variante de números primos.
Cómo funciona
Advertencia: esto es un tugurio cerebral. Desplácese hasta el final si solo desea el código.
Abreviaturas
Este programa básicamente utiliza el algoritmo de programación dinámica de libros de texto para el TSP.
Eso es un montón de posibles errores. Después de jugar con la entrada de anselm y no lograr obtener resultados incorrectos, al menos debería demostrar que mi enfoque general es correcto.
Aunque la solución basada en Concorde es (mucho, mucho) más rápida, se basa en la misma reducción, por lo que esta explicación se aplica a ambos. Además, esta solución se puede adaptar para OEIS A054260 , la secuencia de primos que contiene primos; No sé cómo resolver eso de manera eficiente en el marco de TSP. Entonces todavía es algo relevante.
Reducción de TSP
Comencemos demostrando que reducir a TSP es correcto. Tenemos un conjunto de cuerdas, digamos
y queremos encontrar la supercadena más pequeña que contenga estos elementos.
Saber la longitud es suficiente
Para el PCN, si hay varias cadenas más cortas, tenemos que devolver la lexicografía más pequeña. Pero veremos un problema diferente (y más fácil).
Si podemos resolver SCS-Length, podemos reconstruir la solución más pequeña y obtener el PCN. Si sabemos que la solución más pequeña comienza con nuestro prefijo, intentamos extenderlo agregando cada elemento, en orden lexicográfico, y resolviendo la longitud nuevamente. Cuando encontramos el elemento más pequeño para el que la longitud de la solución es la misma, sabemos que este debe ser el siguiente elemento en la solución más pequeña (¿por qué?), Así que agréguelo y repita en los elementos restantes. Este método para llegar a la solución se llama auto reducción .
Recorriendo el gráfico de superposición máxima
Supongamos que comenzamos a resolver SCS para el ejemplo anterior a mano. Probablemente:
13
y37
porque ya son subcadenas de los otros elementos. Cualquier solución que contenga137
, por ejemplo, también debe contener13
y37
.113,137 → 1137
,211,113 → 2113
etc.De hecho, esto es lo correcto, pero demostrémoslo por completo. Tome cualquier solución SCS; por ejemplo, una más corta supercuerdas para
A
ISy se puede descomponer en una concatenación de todos los elementos en
A
:(Ignoramos los elementos redundantes
13, 37
). Observe que:Mostraremos que cada supercadena más corta se puede descomponer de esta manera:
Por cada par de artículos adyacentes
x,y
,y
comienza y termina en posiciones posteriores ax
. Si esto no es cierto, entoncesx
es una subcadena dey
o viceversa. Pero ya eliminamos todos los elementos que son subcadenas, por lo que eso no puede suceder.Suponga que los elementos adyacentes en la secuencia tienen una superposición menor que la máxima, por ejemplo, en
21113
lugar de2113
. Pero eso haría que el extra sea1
redundante. Ningún elemento posterior necesita la inicial1
(como en 2 1 113), porque ocurre antes de113
, y todos los elementos que aparecen después113
no pueden comenzar con un dígito anterior113
(ver punto 1). Un argumento similar evita que el último extra1
(como en 211 1 3) sea utilizado por cualquier elemento anterior211
. Pero nuestra supercadena más corta , por definición, no tendrá dígitos redundantes, por lo que no se producirán superposiciones no máximas.Con estas propiedades, podemos convertir cualquier problema de SCS en un TSP:
x
,y
, añadir un borde dex
ay
cuyo peso es el número de símbolos adicionales agregados añadiendoy
ax
con superposición máxima. Por ejemplo, agregaríamos un borde de211
a113
con peso 1, porque2113
agrega un dígito más211
. Repita para el borde dey
ax
.Cualquier ruta en este gráfico, desde el prefijo inicial, corresponde a una concatenación de solapamiento máximo de todos los elementos en esa ruta, y el peso total de la ruta es igual a la longitud de la cadena concatenada. Por lo tanto, cada recorrido de menor peso, que visita todos los elementos al menos una vez, corresponde a una supercadena más corta.
Y esa es la reducción de SCS (y SCS-Length) a TSP.
Algoritmo de programación dinámica
Este es un algoritmo clásico, pero lo modificaremos bastante, así que aquí hay un recordatorio rápido.
(He escrito esto como un algoritmo para SCS-Length en lugar de TSP. Son esencialmente equivalentes, pero el vocabulario de SCS ayuda cuando llegamos a las optimizaciones específicas de SCS).
Llame al conjunto de elementos de entrada
A
y al prefijo dadoP
. Para cadak
subconjuntoS
deA
elementos y cada elementoe
deS
, calculamos la longitud de la cadena más corta que comienza conP
, contiene todoS
y termina cone
. Esto implica almacenar una tabla de valores de(S, e)
a sus SCS-Longitudes.Cuando llegamos a cada subconjunto
S
, las necesidades de mesa a que ya contienen los resultados paraS - {e}
para todose
enS
. Como la tabla puede ser bastante grande, calculo los resultados para todos losk
subconjuntos de elementos, luegok+1
, etc. Para esto, solo necesitamos almacenar los resultados parak
yk+1
en cualquier momento. Esto reduce el uso de memoria en un factor aproximadosqrt(|A|)
.Un detalle más: en lugar de calcular la longitud mínima de SCS, en realidad calculo la superposición total máxima entre los elementos. (Para obtener la longitud SCS, solo resta la superposición total de la suma de las longitudes de los elementos). El uso de superposiciones ayuda a algunas de las siguientes optimizaciones.
[2.] Contextos de ítems
Un contexto es el sufijo más largo de un elemento que puede superponerse con los siguientes elementos. Si nuestros artículos son
113,211,311
, entonces11
es el contexto para211
y311
. (También es el contexto de prefijo para113
, que veremos en la parte [4.])En el algoritmo DP anterior, realizamos un seguimiento de las soluciones SCS que terminan con cada elemento, pero en realidad no nos importa en qué elemento termina un SCS. Todo lo que necesitamos saber es el contexto. Así, por ejemplo, si dos SCS para el mismo conjunto terminan en
23
y43
, cualquier SCS que continúe desde uno también funcionará para el otro.Esta es una optimización significativa, porque los primos no triviales terminan solo en los dígitos
1 3 7 9
. De hecho, los cuatro contextos de un solo dígito1,3,7,9
(más el contexto vacío) son suficientes para calcular los PCN para primos hasta131
.[3.] Elementos sin contexto
Otros ya han señalado que muchos números primos comienzan con los dígitos
2,4,5,6,8
, como23,29,41,43...
. Ninguno de estos puede superponerse con un primo anterior (aparte de2
y5
, los primos no pueden terminar en estos dígitos;2
y5
ya se habrán eliminado como redundantes). En el código, estos se denominan cadenas sin contexto .Si nuestra entrada tiene elementos sin contexto, cada solución SCS se puede dividir en bloques
y las superposiciones en cada bloque son independientes de los otros bloques. Podemos barajar los bloques o intercambiar elementos entre bloques que tienen el mismo contexto, sin cambiar la longitud de SCS.
Por lo tanto, solo necesitamos hacer un seguimiento de los posibles conjuntos múltiples de contextos, uno para cada bloque.
Ejemplo completo: para los números primos menores de 100, tenemos 11 elementos sin contexto y sus contextos:
Nuestro contexto inicial de múltiples conjuntos:
El código se refiere a estos como contextos combinados , o ccontexts . Entonces, solo necesitamos considerar subconjuntos de los elementos restantes:
[4.] Fusión de contexto
Una vez que llegamos a números primos con 3 dígitos o más, hay más redundancias:
Estos grupos comparten los mismos contextos de inicio y finalización (generalmente, depende de qué otros números primos estén en la entrada), por lo que no se pueden distinguir cuando se superponen otros elementos. Solo nos importan las superposiciones, por lo que podemos tratar los números primos en estos grupos de contexto igual como indistinguibles. Ahora nuestros subconjuntos DP se condensan en multisubsets
(Esta es también la razón por la cual el solucionador maximiza la longitud de superposición en lugar de minimizar la longitud de SCS: esta optimización conserva la longitud de superposición).
Resumen: las optimizaciones de alto nivel
Ejecutar con
INFO
salida de depuración imprimirá estadísticas comoEsta línea particular es para la longitud SCS de los primeros 62 primos,
2
a293
.1,3,7,11,13,27
más la cadena vacía.43,47,53,59,61,89,211,223,227,229,241,251,257,263,269,281,283
. Estos y el prefijo dado (en este caso, cadena vacía) forman la base del contexto combinado inicial .N_search
), hay 16 grupos de contexto igual no triviales .Al explotar estas estructuras, el cálculo de la longitud SCS solo necesita verificar 8498336
(multiset, ccontext)
combinaciones. La programación dinámica directa tomaría43×2^43 > 3×10^14
pasos, y la fuerza bruta de las permutaciones tomaría6×10^52
pasos. El programa aún necesita ejecutar SCS-Length varias veces más para reconstruir la solución PCN, pero eso no lleva mucho más tiempo.[5., 6.] Las optimizaciones de bajo nivel
En lugar de realizar operaciones de cadena, el solucionador SCS-Length funciona con índices de elementos y contextos. También precalculo la cantidad de superposición entre cada contexto y par de elementos.
Inicialmente, el código usaba GCC
unordered_map
, que parece ser una tabla hash con cubos de listas vinculadas y tamaños hash principales (es decir, divisiones costosas). Así que escribí mi propia tabla hash con sondeo lineal y potencia de dos tamaños. Esto genera una aceleración de 3 × y una reducción de 3 × en la memoria.Cada estado de la tabla consta de un conjunto múltiple de elementos, un contexto combinado y un recuento de superposición. Estos se empaquetan en entradas de 128 bits: 8 para el recuento de superposición, 56 para el conjunto múltiple (como un conjunto de bits con codificación de longitud de ejecución) y 64 para el ccontext (RLE delimitado por 1). Codificar y decodificar el ccontext fue la parte más complicada y terminé usando la nueva
PDEP
instrucción (es tan nueva que GCC todavía no tiene un intrínseco).Finalmente, acceder a una tabla hash es realmente lento cuando se
N
hace grande, porque la tabla ya no cabe en la memoria caché. Pero la única razón por la que escribimos en la tabla hash es para actualizar el recuento de superposición más conocido para cada estado. El programa divide este paso en una cola de captación previa, y el bucle interno capta previamente cada búsqueda de la tabla unas pocas iteraciones antes de actualizar esa ranura. Otra aceleración 2 × en mi computadora.Bonus: mejoras adicionales
AKA ¿Cómo es Concorde tan rápido?
No sé mucho acerca de los algoritmos TSP, así que aquí hay una suposición aproximada.
Concorde utiliza el método de ramificación y corte para resolver TSP.
Ideas obvias que podríamos probar:
Sin embargo, la combinación de ramificación y corte es muy poderosa, por lo que es posible que no podamos vencer a un solucionador de última generación como Concorde, por grandes valores de
N
.Bonus bonus: los primos de contención principales
A diferencia de la solución basada en Concorde, este programa se puede modificar para encontrar los primos que contienen más pequeños ( OEIS A054260 ). Esto implica tres cambios:
Modifique el código del solucionador SCS-Length para clasificar las soluciones en función de si sus sumas de dígitos son divisibles por 3. Esto implica agregar otra entrada, la suma de dígitos mod 3, a cada estado DP. Esto reduce en gran medida las posibilidades de que el solucionador principal se atasque con permutaciones no principales. Este es el cambio que no pude resolver cómo traducir a TSP. Se puede codificar con ILP, pero luego tendría que aprender sobre esta cosa llamada "desigualdad de subtour" y cómo generarlos.
Puede ser que todos los PCN más cortos sean divisibles por 3. En ese caso, el primo de contención de primo más pequeño debe ser al menos un dígito más largo que el PCN. Si nuestro solucionador SCS-Length detecta esto, el código de reconstrucción de la solución tiene la opción de agregar un dígito adicional en cualquier punto del proceso. Intenta agregar cada dígito posible
0..9
y cada elemento restante al prefijo de solución actual, en orden lexicográfico como antes.Con estos cambios, puedo obtener las soluciones hasta
N=62
. Excepto47
cuando el código de reconstrucción se atasca y se da por vencido después de 1 millón de pasos (todavía no sé por qué). Los primos de contención principales son:Código
Compilar con
Para la versión de número primo, también enlace con GMPlib, por ejemplo
Este programa utiliza la instrucción PDEP, que solo está disponible en procesadores x86 recientes (Haswell +). Tanto mi computadora como la de maxb lo admiten. Si el suyo no lo hace, el programa se compilará en una versión de software lenta. Se imprimirá una advertencia de compilación cuando esto suceda.
Pruébalo en línea!
Y la versión exclusiva en TIO . Lo siento, pero no jugué golf en estos programas y hay un límite de duración de la publicación.
fuente
debug_dummy
, puedes usar#define DEBUG(x) void(0)
.debug_dummy
porque quiero que los argumentos sean verificados y evaluados incluso cuando la depuración está desactivada.N=32
solo necesita unos 500 MB, creo.main
, pero lo encontré en el enlace TIO.JavaScript (Node.js) , puntúa 24 en 241 segundos
Resultados
Algoritmo
Esta es una búsqueda recursiva que intenta todas las formas posibles de fusionar números y, finalmente, ordenar las listas resultantes en orden lexicográfico cuando se alcanza un nodo hoja.
Al comienzo de cada iteración, cualquier entrada que pueda encontrarse en otra entrada se elimina de la lista.
Se logró una aceleración significativa al realizar un seguimiento de los nodos visitados, para que podamos abortar temprano cuando diferentes operaciones conducen a la misma lista.
Se logró una pequeña aceleración actualizando y restaurando la lista cuando sea posible en lugar de generar una copia, como lo sugirió
un usuario anónimoNeil.Ejemplo
Código
Pruébalo en línea!
fuente
Solucionador Concorde TSP , puntúa 84 en 299 segundos
Bueno ... me siento tonto por solo darme cuenta de esto ahora.
Todo esto es esencialmente un problema de vendedor ambulante . Para cada par de números primos
p
yq
, agregue un borde cuyo peso es el número de dígitos agregados porq
(eliminando los dígitos superpuestos). Además, agregue un borde inicial a cada primop
, cuyo peso es la longitud dep
. El camino más corto del vendedor ambulante coincide con la longitud del número de contención principal más pequeño.Entonces, un solucionador de TSP de grado industrial, como Concorde , resolverá este problema.
Esta entrada probablemente debería considerarse no competitiva.
Resultados
El solucionador llega
N=350
en aproximadamente 20 horas de CPU. Los resultados completos son demasiado largos para una publicación SE, y el OEIS no quiere tantos términos de todos modos. Aquí están los primeros 200:Código
Aquí hay un script de Python 3 para llamar al solucionador Concorde una y otra vez hasta que construya las soluciones.
Concorde es gratuito para uso académico. Puede descargar un binario ejecutable de Concorde construido con su propio paquete de programación lineal QSopt, o si de alguna manera tiene una licencia para IBM CPLEX, puede construir Concorde desde la fuente para usar CPLEX.
fuente
Limpio , anota 25 en 231 segundos (puntaje oficial)
Resultados
1 < n <= 23
en4236 segundos en TIOn = 24 (2311294134347173535961967837989)
en3224 segundos localmenten = 25 (23112941343471735359619678378979)
en210160segundos localmenten = 1
quen = 25
se encontró en 231 segundos para el marcador oficial (editado por maxb)Utiliza un enfoque similar a la solución JS de Arnauld basada en el rechazo de permutación recursiva, utilizando un conjunto de árbol especializado para ganar mucha velocidad.
Por cada primo que necesita encajar en el número:
Luego, para cada par de subcadenas que unimos, elimine cualquier subcadena de ese par unido de la lista de subcadenas y repita en él.
Una vez que no se pueden unir más subcadenas a ninguna otra subcadena en ningún brazo de nuestra recursión, usamos el conjunto de árbol ya ordenado para encontrar rápidamente el número más bajo que contiene las subcadenas.
Cosas a mejorar / agregar:
Hubo grandes caídas de rendimiento entre
19 -> 20
y24 -> 25
debido al manejo duplicado por el paso de prueba de fusión y el paso de rechazo del candidato, pero se han solucionado.Optimizaciones:
removeOverlap
está diseñado para dar siempre un conjunto de subcadenas que ya están en el orden óptimouInsertMSpec
reduce check-if-is-member e insert-new-member a un conjunto transversalcontainmentNumbersSt
comprueba si la solución anterior funciona para un nuevo númeroPruébalo en línea!
Guardar
main.icl
y compilar con:clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main
Esto produce un archivo
a.out
que debe ejecutarse comoa.out -h <heap_size>M -s <stack_size>M
, donde<heap_size> + <stack_size>
está la memoria que utilizará el programa en megabytes.(Por lo general, configuro la pila en 50 MB, pero rara vez los programas usan incluso eso)
fuente
Scala , puntaje 137Editar:
El código aquí simplifica demasiado el problema.
Por lo tanto, la solución funciona para muchas entradas, pero no para todas.
Publicación original:
Idea básica
Problema más simple
Primero, generamos el conjunto de números primos y eliminamos todos los que ya son subcadenas de otros. Entonces, podemos aplicar múltiples reglas, es decir, si solo hay una cadena que termina en una secuencia y solo una que comienza con esa misma secuencia, podemos fusionarlas. Otra sería que si una cadena comienza y termina con la misma secuencia (como lo hace 101), podemos agregarla / anteponerla a otra cadena sin cambiar los extremos. (Esas reglas solo rinden bajo ciertas condiciones, así que tenga cuidado cuando las aplique)
El verdadero problema
10103
0
10103
1
Por lo tanto, si las reglas en el algoritmo anterior fueran siempre suficientes, se habría demostrado que el problema no era NP-hard.
findSeq
Probar en línea
Código
Como Anders Kaseorg señaló en los comentarios, este código puede devolver resultados subóptimos (por lo tanto, incorrectos).
Resultados
187
,188
,189
,193
.fuente
1234
,3423
,2345
, se genera123453423
en lugar de la óptima12342345
.457, 571, 757
(todos los números primos).findSeq
volvería7574571
por esto pero la longitud más corta es457571
. Entonces tu enfoque es jugar con fuego. Sin embargo, votaron por pura audacia.