Dado un entero positivo N , su tarea es devolver el número de pasos requeridos por el siguiente algoritmo para llegar a N :
Encontrar el número más pequeño triangular T i tal que T i ≥ N . Construya la lista correspondiente L = [1, 2, ..., i] .
Si bien la suma de los términos de L es mayor que N , elimine el primer término de la lista.
Si la suma de los términos de L ahora es menor que N , incremente i y añádalo a la lista. Continúa con el paso 2.
Nos detenemos tan pronto como se alcanza N. Solo el primer paso se ejecuta sistemáticamente. Los pasos 2 y 3 pueden no procesarse en absoluto.
Ejemplos
A continuación se muestra un ejemplo para N = 11 :
Entonces, la salida esperada para N = 11 es 4 .
Otros ejemplos:
- N = 5 - Comenzamos con T 3 = 1 + 2 + 3 = 6 , seguido de 2 + 3 = 5 . Resultado esperado: 2 .
- N = 10 : solo se requiere el primer paso porque 10 es un número triangular: T 4 = 1 + 2 + 3 + 4 = 10 . Salida esperada: 1 .
Primeros 100 valores
A continuación se muestran los resultados para 1 ≤ N ≤ 100 :
1, 2, 1, 4, 2, 1, 2, 10, 2, 1, 4, 2, 6, 2, 1, 22, 8, 2, 10, 2,
1, 2, 12, 6, 2, 4, 2, 1, 16, 2, 18, 50, 2, 6, 2, 1, 22, 6, 2, 4,
26, 2, 28, 2, 1, 8, 30, 16, 2, 6, 4, 2, 36, 2, 1, 2, 4, 12, 40, 2,
42, 14, 2,108, 2, 1, 46, 2, 6, 4, 50, 2, 52, 18, 2, 4, 2, 1, 56, 12,
2, 20, 60, 4, 2, 22, 10, 2, 66, 2, 1, 4, 10, 24, 2, 40, 72, 8, 2, 6
Reglas
- Puede escribir un programa completo o una función que imprima o devuelva el resultado.
- Usted está obligado a procesar cualquier N ≤ 65.536 en menos de un minuto en el hardware de gama media.
- Con suficiente tiempo, su programa / función debería funcionar teóricamente para cualquier valor de N que sea compatible de forma nativa con su idioma. Si no es así, explique por qué en su respuesta.
- Este es el código de golf, por lo que gana la respuesta más corta en bytes.
fuente
Respuestas:
Jalea ,
2931 bytesUn enlace monádico que devuelve el resultado (N = 65536 tarda menos de dos segundos).
Pruébalo en línea!
¿Cómo?
Para una explicación detallada del algoritmo, vea la fantástica publicación de Martin Ender .
La implementación del programa completo de 29 bytes que creé del algoritmo descrito toma 4 min 30 para N = 65536 en mi computadora portátil, por lo que supongo que no cuenta.
Usar un ciclo while para cada paso 3 y reutilizarlo como paso 1 es igual en longitud a lo que puedo manejar al inicializar la lista, ya que no verificar en el paso 3 significa construir una lista hasta que no quede nada y luego encontrar el primer índice del valor:
fuente
Mathematica, 79 bytes
Explicación
No podía molestarme en implementar el algoritmo en el desafío, por lo que quería buscar un acceso directo a la solución. Si bien encontré uno, desafortunadamente no supera la respuesta de Mathematica que implementa el algoritmo. Dicho esto, estoy seguro de que esto aún no está optimizado, y puede haber otros idiomas que puedan beneficiarse de este enfoque o de algunas de las ideas obtenidas en el proceso.
Entonces afirmo que la secuencia que se supone que debemos calcular es:
f (n) = 2 * ( A212652 (n) - A002024 (n)) + 1 + A023532 (n-1)
Alternativamente, es f (n) = 1 si n es un número triangular yf (n) = 2 * ( A212652 (n) - A002024 (n) + 1) de lo contrario.
En la primera expresión, A023532 simplemente codifica estos dos casos diferentes. Las otras dos secuencias (más 1) son la diferencia entre el el mayor entero k en la descomposición más larga de n en enteros consecutivos (k-i + 1) + (k-i + 2) + ... + k = n y el entero más grande j para que 1 + 2 + ... + j <n .
En palabras algo más simples, así es como encontramos la respuesta para números no triangulares: primero, encuentre el número triangular más grande T j que sea menor que n . Entonces j es el penúltimo entero que se agrega durante el paso 1 (porque después de agregar j + 1 habremos excedido n ). Luego descomponga n en tantos (o tan pequeños) enteros consecutivos como sea posible y llame al máximo entre estos números k . El resultado es simplemente 2 * (kj) . La razón intuitiva para esto es que el máximo en la descomposición crece en 1 cada dos pasos y nos detenemos cuando alcanzamosk .
Necesitamos mostrar cuatro cosas para demostrar que esto funciona:
Ya hemos demostrado por qué (1) es cierto. A continuación, demostramos que no podemos terminar en un paso de inserción excepto el inicial (que no ocurre con números no triangulares).
Supongamos que terminamos en un paso de inserción, alcanzando n después de agregar un valor p a la suma. Eso significa que antes de este paso de inserción, el valor era np ( o menos si agregamos múltiples valores a la vez). Pero este paso de inserción fue precedido por un paso de eliminación (ya que no podríamos haber presionado n durante el paso 1). El último valor q que eliminamos durante este paso de eliminación fue necesariamente menor que p debido a la forma en que funciona el algoritmo. Pero eso significa que antes de eliminar q teníamos n-p + q ( o menos ) que es menor que n. Pero eso es una contradicción, porque habríamos tenido que dejar de eliminar enteros cuando golpeamos n-p + q en lugar de eliminar otro q . Esto prueba el punto (2) anterior. Así que ahora sabemos que siempre terminamos en un paso de eliminación y que, por lo tanto, todos los números no triangulares tienen salidas pares.
A continuación, demostramos (3) que cada paso de inserción solo puede insertar un valor. Esto es esencialmente un corolario de (2). Hemos demostrado que después de agregar un valor no podemos golpear n exactamente y dado que la prueba estaba usando una desigualdad, tampoco podemos terminar debajo de n (ya que entonces n-p + q aún sería menor que n y no deberíamos haber eliminado que muchos valores en primer lugar). Entonces, cada vez que agreguemos un valor único, se nos garantiza que excedemos n porque bajamos de n eliminando un valor más pequeño. Por lo tanto, sabemos que el extremo superior de la suma crece en 1 cada dos pasos. Conocemos el valor inicial de este extremo superior (es el m más pequeño tal queT m > n ). Ahora solo tenemos que descubrir este extremo superior una vez que hayamos alcanzado la suma final. Entonces el número de pasos es simplemente el doble de la diferencia (más 1).
Para hacer esto, demostramos (4), que la suma final es siempre la descomposición de n en tantos números enteros como sea posible, o la descomposición donde el máximo en esa descomposición es mínimo (es decir, es la descomposición más temprana posible). Nuevamente haremos esto por contradicción (la redacción en esta parte podría ser un poco más rigurosa, pero ya he pasado demasiado tiempo en esto ...).
Digamos que la descomposición más temprana / más larga posible de n es alguna a + (a + 1) + ... (b-1) + b , a ≤ b , y digamos que el algoritmo lo omite. Eso significa que en el momento en que se agrega b , a ya no debe ser parte de la suma. Si a fuera parte de la suma s , entonces tendríamos n ≤ s en ese momento. Entonces, o la suma solo contiene los valores de a a b , que es igual a ny nos detenemos (por lo tanto, no omitimos esta descomposición), o hay al menos un valor menor que a en la suma, gana en cuyo caso n <sy ese valor se eliminaría hasta llegar a la suma exacta (nuevamente, no se omitió la descomposición). Entonces tendríamos que deshacernos de a antes de agregar b . Pero eso significa que tendríamos que llegar a una situación en la que a es el componente más pequeño de la suma, y el más grande aún no es b . Sin embargo, en ese punto no podemos eliminar a , porque la suma es claramente menor que n (ya que falta b ), por lo que debemos agregar valores primero hasta que agreguemos b y presionemos n exactamente. Esto prueba (4).
Tomando estas cosas juntas: sabemos que el primer par de pasos nos da un valor máximo de A002024 (n) . Sabemos que el valor máximo de la descomposición final es A212652 (n) . Y sabemos que este máximo se incrementa una vez en cada par de pasos. Por lo tanto, la expresión final es 2 * ( A212652 (n) - A002024 (n) + 1) . Esta fórmula casi funciona para números triangulares, excepto que para aquellos solo necesitamos 1 paso en lugar de 2, por lo que corregimos el resultado con la función indicadora de los números triangulares (o su inverso, lo que sea más conveniente).
Finalmente, en cuanto a la implementación. Para la primera secuencia, estoy usando la fórmula MIN (impar d | n; n / d + (d-1) / 2) de OEIS. Resulta guardar algunos bytes si tomamos el factor 2 en esta expresión para obtener MIN (impar d | n; 2n / d + d-1) , porque ese -1 se cancela con el +1 en mi primera versión de f (n) que codifica directamente los dos casos para números triangulares y no triangulares. En el código, esto es:
Para la última secuencia (
1, 2, 2, 3, 3, 3, ...
), podemos usar una forma cerrada simple:Y finalmente, la función del indicador inverso de los números triangulares es 0 siempre que 8n + 1 sea un cuadrado perfecto. Esto se puede expresar en Mathematica como
Hay muchas maneras de expresar estas dos últimas secuencias y cambiar un desplazamiento constante entre ellas, por lo que estoy seguro de que aún no es una implementación óptima, pero espero que esto pueda dar a otros un punto de partida para buscar nuevos enfoques en sus propios idiomas
Desde que me metí en todos estos problemas, aquí hay una gráfica de la secuencia hasta n = 1000 (también podría calcular 100k en un par de segundos, pero realmente no muestra ninguna información adicional):
Puede ser interesante analizar las variaciones sobre esas líneas muy rectas, pero se lo dejaré a otra persona ...
fuente
Mathematica, 72 bytes
Función pura tomando un argumento entero.
Cómo funciona
Un
For
bucleInicialización; establecer
l
(inferior),u
(superior),c
(contador) yk
(suma) a 0.Condición; repetir mientras
k
no es igual a la entrada.Incremento; Incrementar el contador
c
.Cuerpo
Si la entrada es mayor que
k
:Mientras la entrada es mayor que
k
, incrementeu
e incrementek
enu
.Si la entrada no es mayor que
k
:Mientras que la entrada es menor que
k
, decrementok
porl
e incrementol
.Regresa
c
después del bucle.fuente
For[,...]
lateWhile[...]
.Python 2 , 104 bytes
Pruébalo en línea!
Alterna entre agregar términos al final de la lista y eliminar términos desde el principio.
fuente
Haskell ,
70 63 6864 bytesEDITAR:
a
. Se corrigieron errores fuera de uno en la explicación.a
yb
linealmente para obtener términos en la fórmula de suma para cancelar.1#1
es una función anónima que toma y devuelve un entero.Usar como
(1#1) 100
.Pruébalo en línea!
Cómo funciona
(a#b)n
representa el paso actual de cálculo.a, b
son números1, 3, 5, ..
, mientras quen
pueden ser positivos o negativos dependiendo del paso.[(a+1)/2,(a+3)/2..(b-1)/2]
y el número de objetivo-n
.[(b+1)/2,(b+3)/2..(a-1)/2]
y el número de objetivon
.a, b
y las listas es para poder hacer un resumen con la expresión cortas=a*a-b*b
.s= -8*sum[(a+1)/2..(b-1)/2]
.s=8*sum[(b+1)/2..(a-1)/2]
.s>8*n
, entoncesb
se incrementa en 2 antes de recurrir.s<8*n
, a continuación, la recursión cambia el paso mediante el canjea
yb
, y negandon
, y se añade 1 al resultado.s==8*n
, entonces ninguna de las dos comprensiones de la lista da ningún elemento, entonces la suma es0
.(1#1) n
representa una "etapa 2" ficticia antes de comenzar, que se cambia inmediatamente al paso 1, desde donde se crea la lista[1..0]=[]
.fuente
PHP> = 7.0, 74 bytes
usa el operador de la nave espacial
Pruébalo en línea!
Expandido
fuente
$argn
?-R
mucho menosargv
oargi
. Sabía de argc y argv, por supuesto. Muy interesante, gracias.DO,
9491 bytesProbar en línea
fuente
return
), pero para los que sí lo hacen, siéntete libre de incorporarlos en tu respuesta.JavaScript (ES6), 82 bytes
Fragmento de prueba
Mostrar fragmento de código
fuente
dc , 61 bytes
Pruébalo en línea!
Explicación
Macro recursiva principal:
Esta macro:
S
representa el número actual exactamente. Sale si lo hace.S+N
(sobre-aproximación) oS-N
(sub-aproximación), la elección alterna entre iteraciones.Cuando sale, el rastro dejado en la pila le dice al programa principal cuántas iteraciones tomó.
fuente
Python 3,
150138 bytesRegistro de cambios:
fuente
else
es necesario? Creo que siempre seelse
ejecuta, porque el ciclo siempre termina normalmente (sinbreak
), y parece funcionar bien sin él .A=l.append
parte y usarlal+=[x]
en su lugar.Lote, 126 bytes
Explicación:
l
es cero si el paso 2 nunca se ejecutó. Esto permiten
realizar un seguimiento del número de iteraciones del paso 3. Dado que el algoritmo nunca se detiene en el paso 3, por lo tanto, debe haber ejecutado el paso 1 una vez y el paso 2n+1
veces para un total den+n+2
pasos. Sin embargo, si el parámetro es un número triangular, el paso 2 nunca se ejecuta, por lo que debemos restar un paso.fuente
Python 2,
8681 bytesPruébalo en línea!
Calcula el caso de prueba 65536
0.183s
en TIO.Esta versión recursiva a 84 bytes no puede calcular todos los valores hasta 65536:
Pruébalo en línea!
fuente
Mathematica, 92 bytes
Función pura que toma un argumento entero y devuelve un entero.
Las variables
a
yb
representan los números iniciales y finales (que cambian constantemente) en la suma considerada, mientras queq
representan el total acumulado (de los números dea+1
ab
);t
realiza un seguimiento de todos los valoresq
encontrados hasta ahora. Después de inicializar estas variables, elFor
bucle sigue ejecutándoseIf[q<#,q+=++b,q-=++a]
, lo que agrega un nuevo número al final o resta el número en el frente como lo indica la especificación, hastaq
igual a la entrada.Ahora solo tenemos que extraer el número de pasos de
t
la lista deq
valores encontrados en el camino. Por ejemplo, cuando la entrada es11
, elFor
ciclo sale cont
igual{0,1,3,6,10,15,14,12,9,15,11}
. La mejor manera que encontré para calcular el número de pasos a partir de esto es contar cuántas veces cambian las diferencias de arriba a abajo; eso es lo que hace el comando detalladoLength@Split@Sign@Differences@t
, pero sospecho que se puede mejorar.fuente
C (tcc), 71 bytes (61 + 10)
Argumentos de línea de comando (incluido un espacio):
Fuente:
Cómo funciona:
c
cuenta la cantidad de pasos.m
yM
almacenar el mínimo y el máximo del rango,s
la suma. Inicialmente, todos son cero.Continuamente,
c
se incrementa ys
se compara conn
. Mientras sean desiguales:Si
c
es impar, entonces, siempre y cuandos<n
, agregue un número entero al final del rango: aumenteM
en uno ys
enM
.Si
c
es par, entonces, siempre y cuandos>n
, eliminar un número entero desde el inicio de la gama: disminucións
porm
, e incrementarm
por uno.Cuando el ciclo sale,
c
se ha incrementado demasiadas veces. Disminuirlo produce el resultado correcto, y se calcula en el registro correcto para que actúe como valor de retorno.De manera divertida, usa exactamente los mismos nombres de variables que la respuesta C de Khaled.K . No se copian.
fuente
Perl 6 , 114 bytes
(inspirado en una implementación anterior de Haskell )
Pruébelo
Se ejecuta con una entrada de 65536 en menos de 45 segundos en mi computadora, pero no he podido ejecutarlo en menos de 60 segundos con TIO.run.
Tengo Rakudo v2017.04 +, donde tiene v2017.01 .
Rakudo / NQP / MoarVM obtiene optimizaciones casi a diario, por lo que podría haber una cantidad de ellas desde el ínterin que sean necesarias para obtenerla en un plazo breve.
Expandido
Tenga en cuenta que Rakudo tiene una optimización para
Range.sum
que no tenga que recorrer todos los valores.fuente