(Desafío tomado de un juego multijugador (choque de código) en codingame.com )

El reto

Encontrar el n término -ésimo de la siguiente secuencia: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4...o, para hacerlo más obvio,{1}, {1,2}, {1,2,3}, {1,2,3,4}...

La secuencia se compone de rangos concatenados de 1 a x , comenzando desde 1, hasta el infinito.

Reglas / IO

La entrada y la salida pueden estar en cualquier formato, siempre que sea distinguible. La entrada puede tomarse de cualquier fuente apropiada: STDIN, archivo, etc.

La entrada puede ser 0 o 1 indexada, y la indexación seleccionada debe mencionarse en la publicación.

Tendrá que manejar al menos hasta un resultado de 255 inclusive (lo que significa que la entrada máxima indexada a 0 es 32640). Cualquier cosa sobre eso debe ser manejada, si su idioma lo admite.

¡Esto es code-golfpara que gane el conteo de bytes más corto!

Casos de prueba (indexación basada en 0)

0 -> 1
1 -> 1
5 -> 3
10 -> 1
59 -> 5
100 -> 10
1001 -> 12

05AB1E , 5 bytes

El programa está indexado a 0, código:

ÌLL¹è

Explicación:

Ì       # Double increment the input
 LL     # List of list on the input
   ¹è   # Get nth element

Utiliza la codificación CP-1252 . Pruébalo en línea!

Haskell , 27 26 bytes

([z|k<-[1..],z<-[1..k]]!!)

Pruébalo en línea!

Gracias @DanD. por -1 byte!

Esta es una función anónima, creando la secuencia infinita un solo devolver el nelemento -ésimo de los mismos: [[1..k]| k<-[1..]]produce una lista infinita de lista: [[1],[1,2],[1,2,3],[1,2,3,4],...]. Para concatenarlos, podemos escribir lo [z|k<-[1..],z<-[1..k]]que resulta [1,1,2,1,2,3,1,2,3,4,...]y finalmente (...!!)acepta la entrada n(notación sin sentido) y devuelve el nenésimo término (basado en 0).

JavaScript, 29 28 bytes

-1 byte gracias a Arnauld!

f=(n,m)=>n++<m?n:f(n+~m,-~m)

Utiliza la fórmula recursiva indexada en 0 que se encuentra en OEIS.

Cuando se llama con 1 argumento como se esperaba, el valor predeterminado del segundo m, será undefined. Sin embargo, -~undefineddevuelve 1, lo que nos permite poner en marcha la recursividad sin un explícito m = 1en la lista de argumentos (¡gracias @Arnauld!)

Fragmento de prueba:

f=(n,m)=>n++<m?n:f(n+~m,-~m)

let examples = [0, 1, 5, 10, 15, 1000];

examples.forEach(function log(x) {
    console.log(x, " => ", f(x))
});

Alternativamente, para el mismo recuento de bytes, podemos tener una función curry como esta:

f=n=>m=>n++<m?n:f(n+~m)(-~m)

Puede llamar a esto con f(5)(): devuelve una función que, cuando se llama, devuelve el resultado, como se describe en esta meta publicación .

Jalea , 5 bytes, 1 indexado

RRF³ị

Pruébalo en línea!

Explicación:

                                      (Assume N = 4 for the examples)
R      Generate a list of 1 to N      [1, 2, 3, 4]
 R     Generate new lists for each item on the previous list, with that item as N
                                      [[1], [1,2], ...]
  F    Flatten that list              [1, 1, 2, 1, 2, 3 ...]
   ³ị  Use the input number (³) as index (ị) on the list. 
       This is one-based:             [1, 1, 2, 1, 2, 3 ...] 
                                                ^

Octava, 39 bytes

@(z)z-(n=ceil((8*z+1)^.5/2-.5))*(n-1)/2

1- índice basado

Explicación:

Considere esta secuencia:

1   1   2   1   2   3   1   2   3   4   1   2   3   4   5

si contamos el número de elementos de subsecuencias tenemos

1   2        3          4               5         

entonces, usando la fórmula de Gauss para un número triangular , podemos formar una fórmula para z:

z=n*(n+1)/2

esa es una ecuación cuadrática si la resolvemos para n tenemos

n=(sqrt(8*z+1)-1)/2

¡Pruébelo en línea!

Haskell, 25 24 bytes

(!!)$[1..]>>= \x->[1..x]

Ejemplo de uso: ((!!)$[1..]>>= \x->[1..x]) 10-> 1. Pruébalo en línea! .

Asigna la función anónima make-a-list-from-1-to-x \x->[1..x](la función incorporada enumFromTo 1es un byte más larga) a la lista infinita [1..]y concatena las listas resultantes en una sola lista. !!selecciona el enésimo elemento.

Gracias a @flawr por un byte.

Octava , 39 bytes

@(n){v=1:n,A=triu(v'+0*v),A(A>0)(n)}{3}

Pruébalo en línea!

Esto utiliza un enfoque alternativo.

Por ejemplo, n=1esto A=triu(v'+0*v)crea la matriz

1   1   1   1
0   2   2   2
0   0   3   3
0   0   0   4

Al eliminar todos los elementos cero y agregar las columnas A(A>0), obtenemos la secuencia:

1   1  2  1  2  3  1  2  3  4

Entonces es solo una cuestión de extraer el nenésimo término de esa secuencia.

Python , 39 36 bytes

-3 bytes gracias a Dennis!

Una lambda recursiva que utiliza indexación basada en 1.

f=lambda n,m=1:n*(n<=m)or f(n-m,m+1)

Pruébalo en línea!

Llevamos un registro del tamaño actual de "aumento" usando m. Si nes menor o igual que m, cabe dentro del "aumento" actual, y así lo devolvemos. Sin embargo, si es más grande que m, le mquitamos, que sumamos 1 my llamamos a la función de forma recursiva (pasando al siguiente aumento).

R, 25 bytes

i=scan();sequence(1:i)[i]

El índice está basado en 1.

Pyth , 6 5 bytes

¡1 byte guardado gracias a @TheBikingviking!

@s._S

Esto usa indexación basada en 0.

Pruébalo en línea!

Explicación

@          Index with implicit input into
   ._      all prefixes of
     S     1-based range of implicit input
 s         concatenated into an un-nested list

Mathematica, 27 24 bytes

¡Gracias @MartinEnder por 3 bytes!

((r=Range)@r@#<>1)[[#]]&

1 indexado. Esto arroja errores que son seguros de ignorar.

Explicación

((r=Range)@r@#<>1)[[#]]&
  r=Range                 (* Store Range function in r *)
           r@#            (* Create list {1..n} *)
 (r      )@               (* For each element, generate {1..n} *)
              <>1         (* Join the lists and append a 1; throws errors *)
(                )[[#]]&  (* Take the nth element *)

brainf * ck, 78 bytes

,>+<[>[->>+>+<<<]>>>[-<<<+>>>]<<+[->->+<<]>[<<->>>[-<<+>>]<[-]]>[-]<<<+<-]>>+.

Toma entradas (basadas en 0) y salidas como valores de bytes.

Puedes probarlo aquí.

La entrada requiere un \número decimal anterior (por ejemplo, \10para 10). Si la salida es un carácter ASCII imprimible, debería verlo. De lo contrario, presione ver memoria -> volcado final. El valor que se imprimió está en la tercera celda (celda número 2).

Explicación:

Celda 0 (ENTRADA): es la entrada y se disminuye mi 1 cada vez a través del bucle.

Celda 1 (RESET): se incrementa en 1 cada vez que es igual a TERM. Para hacer esto, cada vez a través del ciclo sumamos 1 y si no son iguales restamos 1.

Celda 2 (TERM): aumenta en 1 cada ciclo y se establece en 0 si coincide con RESET. Para hacer esto, solo copio el valor de HOLD si esta celda no es igual a RESET.

Celda 3 (IGUAL): se utiliza para verificar si RESET y TERM son iguales.

Celda 4 (RETENER): se usa para copiar los valores de RESET y TERM de nuevo después de la verificación de igualdad.

,>+<              # get input and put a 1 in RESET
[                 # for INPUT to 0
  >[->>+>+<<<]    # copy RESET to EQUAL and HOLD
  >>>[-<<<+>>>]   # copy HOLD back into RESET
  <<+             # add 1 to TERM
  [->->+<<]       # subtract TERM from EQUAL and copy it to HOLD
  >[              # if RESET and TERM were not equal
    <<-           # subtract 1 from RESET
    >>>[-<<+>>]   # copy HOLD back to TERM
    <[-]          # zero out EQUAL
  ]               # end if
  >[-]            # zero out HOLD
  <<<+            # add 1 to RESET (this cancels out the subtraction if
                  #     RESET did not equal TERM)
  <-              # subtract 1 from INPUT
]>>+.             # end for and add 1 because the sequence resets to 1 not 0

Pyke, 6 bytes

OmSsQ@

Pruébalo aquí!

O      -    input+2
 mS    -   map(range(1,i+1), range(^))
   s   -  sum(^)
    Q@ - ^[input]

0 indexado.

R, 43 41 bytes

Editar: Encontró un enfoque recursivo más corto utilizando A002262 + 1 (0 indexado):

f=function(n,m=1)`if`(n<m,n+1,f(n-m,m+1))

Versión antigua:

n=scan();n-choose(floor((1+sqrt(8*n))/2),2)

Fórmula 1 indexada de OEIS.

Perl 6 , 21 bytes

{map(|^*,^∞)[$_]+1}

0 indexado. Pruébalo en línea!

Cómo funciona:

{                 }  # A lambda.
         ^∞          # Range from 0 to Inf-1. (Same byte count as 0..*, but cooler.)
 map( ^*,  )         # Map each number n to the range 0..(n-1),
     |               # And slip each range into the outer list.
            [$_]     # Index the sequence with the lambda argument.
                +1   # Add 1.

Perl 6 , 21 bytes

{[\,](1..*).flat[$_]}

0 indexado. Pruébalo en línea!

Cómo funciona:

{                   }  # A lambda.
      1..*             # Range from 1 to infinity.
 [ ,](    )            # Fold it with the comma operator,
  \                    # and return all intermediate results, e.g. (1), (1,2), (1,2,3)...
           .flat       # Flatten the sequence.
                [$_]   # Index it with the lambda argument.

Ninguna de estas soluciones es tan corta como la de JungHawn Min , pero son enfoques alternativos, que es algo que supongo. Ambas son funciones sin nombre que toman una entrada de entero positivo (1 indexado) y devuelven un entero positivo.

Mathematica, 30 bytes

-#^2-#&@⌈√(2#)-3/2⌉/2+#&

¡Una fórmula matemática real para esta función! Hecho más legible (en parte mediante la traducción de los caracteres 3-byte ⌈, √y ⌉):

# - ((#^2 + #) / 2 &)[Ceiling[Sqrt[2 * #] - 3/2]] &

Ceiling[Sqrt[2 * #] - 1/2]nos dice a qué sublista se refiere la entrada, de la cual restamos una para decirnos qué sublista termina antes de llegar a la entrada; luego ((#^2 + #) / 2 &)calcula cuántos elementos ocurren en todas las sublistas antes de la que nos interesa, que restamos de la entrada #para obtener nuestra respuesta. (Algunos notarán la fórmula familiar (#^2 + #) / 2para el #número triangular th; Ceiling[Sqrt[2 * #] - 1/2]es esencialmente la función inversa).

Mathematica, 32 bytes

If[#2<=#,#2,#0[#+1,#2-#]]&[1,#]&

Solución recursiva, básicamente la misma que en la respuesta de Billywob y otras.

Brain-Flak , 46 bytes

Cero indexado

(<>()){(({}())[()]){({}[()])<>}{}}<>([{}()]{})

Pruébalo en línea!

Pila limpia, 48 bytes

(<>()){(({}())[()]){({}[()])<>}{}}{}<>([{}()]{})

Pruébalo en línea!

Explicación

Esta es una versión modificada de la función de módulo . En lugar de utilizar un número constante como divisor, incrementa el divisor cada vez que se sustrae el divisor (una vez por iteración de bucle externo).

Código anotado

(<>())       # Switch to the opposite stack and push 1 (the initial divisor)
{            # (outside loop) While top of stack is not 0...
  (          # Push...
    ({}())   # Push the divisor plus 1
  [()])      # ...minus one (ie push a copy of the original divisor
  {          # (inner loop) While the top of stack does not equal zero
    ({}[()]) # Decrement the top of the active stack
    <>       # Switch stacks
  }{}        # (inside loop) End loop and pop zero off the top of stack)
}            # (outside loop) End loop
<>           # Switch stacks (to the one with the divisor)
([{}()]{})   # Calculate the result

Java 8, 85 73 55 bytes

n->f(n,1)+1int f(int n,int m){return n<m?n:f(n-m,m+1);}

Enfoque recursivo indexado en 0 con la fórmula proporcionada en el OEIS :

a(n) = 1 + A002262(n).
A002262 : a(n)=f(n,1)con f(n,m) = if n<m then n else f(n-m,m+1).

Pruébalo aquí

Respuesta anterior ( 85 56 bytes):

n->{int m=~-(int)Math.sqrt(8*n+1)/2;return n-m*-~m/2+1;}

Usó la otra fórmula indexada en 0 proporcionada en el OEIS :

el enésimo término es n - m*(m+1)/2 + 1, donde m = floor((sqrt(8*n+1) - 1) / 2).

Pruébalo aquí

Perl , 30 bytes

29 bytes de código + -pbandera.

map{$\-=$c++if$c<++$\}0..$_}{

Pruébalo en línea!

MATL, 8 bytes

:"@:]vG)

Esta solución utiliza indexación basada en 1

Pruébalo en MATL Online

Explicación

        Implicitly grab input (N)
:       Create an array from [1...N]
"       For each element (A) in this array...
  @:    Create an array from [1....A]
]       End for loop
v       Vertically concatenate everything on the stack
G       Explicitly grab the input again
)       And use it to index into the vertically concatenated array
        Implicitly display the result

QBIC , 21 bytes, 1 indexado

:[a|[b|~q=a|_Xc\q=q+1

Explicación:

:      Get 'a' from the cmd line
[a|    FOR (b = 1; b <= a; b++) This creates an outer loop from 1 to N
[b|    FOR (c = 1; c <= b; c++) This creates an iteration, yielding the 1, 12, 123 pattern
       'q' stores how many terms we've seen. It starts at 1 b default.
~q=a   if we are at the desired term (q == a)
|_Xc   Then quit, and print 'c' (the current number in the sequence)
\q=q+1 Else, increase 'q' and run again.

Enfoque un poco más interesante, pero 10 bytes más:

:{~b+q>=a|_xa-b|\b=b+q┘q=q+1

Este programa calcula continuamente el número total de números en este paréntesis y todos los anteriores ( 1 at loop 1, 3 at loop 2, 6 at loop 3 ...). Cuando ese contador excede el índice N buscado, entonces devuelve X desde el soporte actual, donde X es N menos la cantidad anterior del contador.

Rubí, 30 bytes.

->n{(0..n).find{|x|0>=n-=x}+n}

Indexación basada en 1

R, 37 bytes

n=scan();for(i in 2:n)T=c(T,1:i);T[n]

Toma información de ny crea la secuencia para las primeras nsecuencias. Esto lo hace algo ineficiente en entradas más altas, pero debería estar bien. Luego devuelve la nentrada -th, 1-indexada.

Utiliza un pequeño truco al comenzar la secuencia con T, que es TRUEo 1por defecto.

C11, 48 bytes

int f(int x){int q=1;while(x>q)x-=q++;return x;}

Pruébalo en línea!

También funciona en C ++ y Java.

Una alternativa para el mismo conteo de bytes:

int f(int x){int q=0;while(x>++q)x-=q;return x;}

brainfuck, 141 bytes

Sé que soy demasiado tarde para la recompensa, pero solo quería ver cuántos bytes el algoritmo que pensé terminaría siendo.

Este programa está indexado a cero.

,>+<[[->>+>+<<<]>>[-<<+>>]<[->+>>+<<<]>[-<+>]>>+[[-<->>+<]>[-<+>]<<<<]>>[>>>]>[.[<<<]]<<<<<<<[[-]>>>[-<+<<+>>>]<[->+<]<<<<<]>>>[>>>]<<<]>[.>]

Pruébalo en línea

• Seleccione memoria dinámica (infinita) , o no funcionará
• Para probar los valores de entrada> 255, cambie el Tamaño de celda (Bits) a 16 o 32 .
• El intérprete explica cómo dar entrada. Para entrada decimal use \5para entrada de 5.
  • El valor decimal máximo con el que puede probar la entrada es \999
  • La entrada hexadecimal puede aumentar el tamaño de la celda.

Explicación:

Esto muestra el programa dividido por pasos, que muestra lo que sucede para la entrada de 5. #se colocan en las ubicaciones de volcado de memoria ideales para el intérprete.

Probablemente desee usar la casilla de verificación Volcar memoria en char:# si ejecuta esta versión. Esto volcará la memoria al golpear #, permitiéndole ver el valor en la cinta en caso de que sea un carácter no imprimible, o ver qué sucede en cualquier paso que desee. La celda en la que está el puntero estará en negrita.

,>+<                       (5) 1
[[->>+>+<<<]>>[-<<+>>]       5 1 (0) 5
<[->+>>+<<<]>[-<+>]>>+       5 1 0 5 (2)
[[-<->>+<]>[-<+>]<<<<] (0) 0 4 1 0 3 2 0 0
>>[>>>]                      4 1 0 3 2 0 (0) 0
                             1 1 0 (0) 2 0
>[.#[<<<]]<<<<                4 1 0 (3) 2 0 0 0
<<<[[-]>>>[-<+<<+>>>]<[->+<]<<<<<]>>> (3) 1 0 3 2 0 0 0
[>>>]<<<]>[.#>]

Tape structure:
    (cell_1 cell_2 temp), (cell_1 cell_2 temp), ...

Take Input;
If not zero:
  copy last pair to the right and add one to its cell_2
  subtract each cell_2 from each cell_1 (leaving each cell_2 intact)
  move checking from left to right: 
    If cell_1 is zero and cell_2 isn't:
      print cell_2
    Else:
      copy last cell_1 back, overwriting each previous cell_1
Else:
  right one and print result

Pruébalo en línea

• Seleccionar memoria dinámica (infinita) , o no funcionará
• Volcado de memoria en char: #

Notas:

• Para ejecutar esto en otro intérprete que no permita moverse a la izquierda de la celda inicial (es por eso que uso la memoria dinámica), agregue un montón >al comienzo. El número requerido puede variar según el valor de entrada, pero es O (1).

tinylisp (repl), 90 bytes (indexado 0)

(d r(q((n j x)(i n(i(e j x)(r(s n 1)1(s x(s 0 1)))(r(s n 1)(s j(s 0 1))x))j
(q((n)(r n 1 1

O, no compitiendo (usando una función que se confirmó después de que se publicó este desafío), 80 bytes :

(d r(q((n j x)(i n(i(e j x)(r(s n 1)1(a x 1))(r(s n 1)(a j 1)x))j
(q((n)(r n 1 1

La primera línea define una función auxiliar r, y la segunda línea es una función sin nombre que toma ny devuelve el enésimo término de la secuencia. He especificado esto como un envío de respuesta porque la respuesta completa automáticamente los paréntesis al final de cada línea, no solo al final del programa. Con esas advertencias, aquí hay una versión modificada para que funcione en Pruébelo en línea , y aquí hay una versión no protegida que se ejecuta contra las entradas 0 a 54.

Explicación

Usaré la versión no competitiva aquí. La única diferencia es que la versión oficial tiene que implementar la suma como dos restas.

(d r           Define r to be:
 (q(           A lambda function (= a list of two elements, quoted to prevent evaluation):
  (n j x)       Arguments n, j (the range counter), and x (the range limit)
  (i n          If n is truthy, i.e. nonzero:
   (i(e j x)     If counter equals limit:
    (r            Call r recursively on:
     (s n 1)       n-1
     1             counter reset to 1
     (a x 1))      limit increased by 1
    (r           Else, call r recursively on:
     (s n 1)       n-1
     (a j 1)       counter increased by 1
     x))           same limit
   j))))        Else, we're done; return the counter value

(q(            Lambda function:
 (n)            Argument n
 (r n 1 1)))    Call r with n, counter = 1, range limit = 1

C, 54 bytes

No es la solución C más corta, pero tiene el mérito de ejecutarse en tiempo constante (sin bucles, solo matemática). Utiliza indexación basada en cero:

x;f(n){x=floor(sqrt(8*n+1)-1)/2;return 1+n-x*(x+1)/2;}

Sin golf:

int f(int n) {
    int x = floor(sqrt(8*n+1)-1)/2; //calculate the number of the current subsequence (zero based)
    return 1+n-x*(x+1)/2;   //x*(x+1)/2 is the zero based index of the `1` starting the subsequence
}

Prueba con:

#include <math.h>
#include <assert.h>
#include <stdio.h>

x;f(n){x=floor(sqrt(8*n+1)-1)/2;return 1+n-x*(x+1)/2;}

int main(){
    int i;
    for(i = 0; i < 10; i++) printf("%d ", f(i));
    printf("\n");

    assert(f(0) == 1);
    assert(f(1) == 1);
    assert(f(5) == 3);
    assert(f(10) == 1);
    assert(f(59) == 5);
    assert(f(100) == 10);
    assert(f(1001) == 12);
}

C, 103 bytes

Para un principiante está bien, creo :).

int main(){int n,c,i,j;scanf("%d",&n);while(c<n){for(i=1;i<=j;i++){c++;if(c==n)printf("%d",i);}j++;}}

o la forma formateada

#include <stdio.h>

int main() {
    int n,c,i,j;
    scanf("%d",&n);
    while(c<n) 
    {
        for(i=1;i<=j;i++)
        {
            c++;
            if(c==n) printf("%d",i);
        }
        j++;
    }
}

CC , 21 bytes, indexación basada en 0

?d8*1+v1-2/d1+*2/-1+p

¡Prueba el programa de cc en línea!

Explicación:

?      Push input number n.
d      Duplicate n at the top of the stack.
8*1+   Replace n at the top of the stack with 8n+1.
v      Replace 8n+1 at the top of the stack with the floor of its square root.
1-2/   Subtract 1, and divide by 2 (ignoring any fractional part).

La parte superior de la pila ahora contiene el índice k del mayor número triangular que es <= n.

d1+*2/ Compute k(k+1)/2, which is the greatest triangular number <= n.
-      Subtract n-(the greatest triangular number <= n). The first n is on the stack in position 2, because the input number n was duplicated at the top of the stack at the very beginning of the program, and only one of the values was popped and used (until now).
1+     Add 1 because the desired sequence starts over again at 1 (not 0) at every triangular number.
p      Print the answer.

Este programa de CC se puede convertir en un script bash de tamaño competitivo:

Utilidades Bash + Unix, 28 bytes, indexación basada en 0

dc -e"?d8*1+v1-2/d1+*2/-1+p"

¡Prueba el programa bash en línea!

C, 81 44 bytes

método iterativo directo, 0 indexado y con un ligero masaje;

m=1,c=1;f(n){for(;n--;c=c^m?c+1:!!++m);c=c;}

Pruébalo en línea!