Una secuencia mágica es una secuencia de enteros no negativos, de x[0..n-1]
modo que hay x[i]
casos exactos dei
Por ejemplo, 6,2,1,0,0,0,1,0,0,0 es una secuencia mágica ya que hay 6 0's, 2 1's, etc.
Escriba una función que cuando se le da n, emite todas las secuencias mágicas de longitud n
El programa que puede producir la salida correcta para el valor más alto de n en 10 segundos gana. (Sin embargo, todos los programas son bienvenidos)
Por ejemplo, el programa de Alice puede manejar hasta n = 15 en 10 segundos, mientras que el de Bob puede manejar hasta n = 20 en el mismo tiempo. Bob gana.
Plataforma: Linux 2.7GHz @ 4 CPU
number
fastest-code
sequence
Agnishom Chattopadhyay
fuente
fuente
n>5
con una solución no de la forma[n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]
? He admiradon=20
y no he encontrado uno, y me pregunto si estoy cometiendo un error.Respuestas:
Python, n≈10 8
Esto utiliza el hecho, que demostraré, de que las únicas secuencias de longitud de Magic
n
son:[1, 2, 1, 0]
y[2, 0, 2, 0]
paran=4
[2, 1, 2, 0, 0]
paran=5
[n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0]
paran>=7
Entonces, para
n>=7
, uno solo necesita devolver una gran tupla. Puedo hacer esto hasta aproximadamenten=10^8
en mi computadora portátil, que probablemente esté limitada por la memoria; más y se congela. (Gracias a trichoplax por la idea de usar tuplas en lugar de listas). O, si uno puede imprimir un diccionario de entradas distintas de cero{0:n-4, 1:2, 2:1, (n-4):1}
, puede hacerlo por descomunaln
.Pruebo la unicidad para
n>=7
; los otros pueden ser verificados por fuerza bruta o trabajo de casos.La suma de las entradas de
l
es el recuento total de todos los números de la lista, que es su longitudn
. La lista tienel[0]
ceros y, por lo tanto,n-l[0]
entradas distintas de cero. Pero, por definición,l[0]
debe ser distinto de cero o tenemos una contradicción, y cada una de las otras entradas distintas de cero es al menos 1. Esto ya representa una sumal[0] + (n-l[0]-1)*1 = n-1
de la suma total den
. Entonces, sin contarl[0]
, puede haber a lo sumo un 2 y ninguna entrada mayor que 2.Pero eso significa que las únicas entradas distintas de cero son
l[0], l[1], l[2], and l[l[0]]
, cuyos valores son como máximol[0]
y una permutación de1,1,2
, lo que da una suma máxima del[0]+4
. Como esta suma esn
, que es al menos 7, tenemosl[0]>=3
, y asíl[l[0]]=1
. Ahora, hay al menos uno1
, lo que significal[1]>=1
, pero sil[1]==1
ese es otro1
, entoncesl[1]>=2
, lo que implical[1]
es el solitario2
. Esto dal[2]=1
, y todas las entradas restantes son0
, porl[0]=n-4
lo tanto , lo que completa la solución.fuente
Python 3, n≈40
Realiza una búsqueda amplia de listas posibles, completa las entradas de derecha a izquierda, detiene la búsqueda en un sufijo si no es plausible, lo que puede suceder si:
n
(la suma de toda la lista debe sern
)i*l[i]
en el sufijo exceden
(la suma de toda la lista debe sern
)Tenía los prefijos probados originales de izquierda a derecha, pero eso fue más lento.
Las salidas hasta
n=30
son:Excepto por las primeras tres listas
[1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0]
, hay exactamente una lista de cada longitudn>6
, y tiene la forma[n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]
. Este patrón persiste al menos hastan=50
. Sospecho que se mantiene para siempre, en cuyo caso es trivial generar una gran cantidad de estos. Incluso si no, una comprensión matemática de las posibles soluciones aceleraría en gran medida una búsqueda.fuente
n=0
. Extrañaba que devolviéramos el resultado para un sencillon
, sin contar los de arriban
. Esto me lleva hastan=40
.Pyth - 15 bytes
Utiliza la fuerza bruta por todas las secuencias posibles de len
n
y luego los filtros.Explicación completa próximamente.
Pruébalo aquí en línea .
fuente
K, 26 bytes
Como el enfoque de Maltysen, fuerza bruta. El corazón del programa es un predicado que prueba si un vector dado es "mágico":
Construya un vector iota siempre que el vector de entrada (
!#x
), cuente las ocurrencias de cada dígito ((+/x=)'
) y compare el resultado con el vector de entrada (x~
). Si hay una coincidencia, tienes una secuencia mágica.Desafortunadamente, esta primera puñalada parece ser bastante lenta. Las pruebas con Kona en mi computadora portátil tardan unos 12 segundos en manejar n = 7. Necesito pensar esto un poco más.
fuente