Voltear triángulo numérico

30

Digamos que enumeras los enteros positivos en un triángulo, luego voltéalo de izquierda a derecha. Dado un número, envíe el número al que se envía. Este es un mapeo autoinverso.

         1                      1         
       2   3                  3   2       
     4   5   6    <--->     6   5   4     
   7   8   9  10         10   9   8   7   
11  12  13  14  15     15  14  13  12  11

Este es el enésimo elemento de A038722 , un índice:

1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...

Esta secuencia invierte trozos contiguos de los enteros positivos con longitudes crecientes:

 1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, ...
<-><----><-------><-----------><------------------>

Casos de prueba:

1 -> 1
2 -> 3
3 -> 2
4 -> 6
14 -> 12
990 -> 947
991 -> 1035
1000 -> 1026
1035 -> 991
1036 -> 1081
12345 -> 12305

Tabla de clasificación:

Mostrar fragmento de código

code-golf math sequence xnor
fuente

Respuestas:

15

JavaScript (ES7), 26 bytes

n=>((2*n)**.5+.5|0)**2-n+1

Una implementación de la siguiente fórmula de OEIS :

fórmula

Manifestación

Mostrar fragmento de código

Arnauld
fuente
¡Me gusta que la operación OR lo fragmente en un entero! ¡buen trabajo!
CraigR8806
7

Jalea , 8 7 bytes

RṁR€UFi

¡Gracias a @ErikTheOutgolfer por guardar 1 byte!

Pruébalo en línea!

Cómo funciona

RṁR€UFi  Main link. Argument: n

R        Range; yield [1, ..., n].
  R€     Range each; yield [[1], [1, 2], [1, 2, 3], ..., [1, ..., n]].
 ṁ       Mold the left argument like the right one, yielding
         [[1], [2, 3], [4, 5, 6], ...]. The elements of the left argument are 
         repeated cyclically to fill all n(n+1)/2 positions in the right argument.
    U    Upend; reverse each flat array, yielding [[1], [3, 2], [6, 5, 4], ...].
     F   Flatten, yielding [1, 3, 2, 6, 5, 4, ...].
      i  Index; find the first index of n in the result.
Dennis
fuente
6

Alice , 27 bytes

Gracias a Sp3000 por la .Cidea.

/o
\i@/.2:e2,tE*Y~Z.H2*~.C+

Pruébalo en línea!

Explicación

Creo que puede haber una forma más corta de calcular esto usando números triangulares, pero pensé que este es un abuso interesante de un incorporado, así que aquí hay una solución diferente.

La idea básica es hacer uso de los elementos integrados de "empaquetar" y "desempaquetar" de Alice. "Pack", o Ztoma dos enteros, los asigna biyetivamente a un solo entero. "Desempaquetar", o Y, invierte esta biyección y convierte un número entero en dos. Normalmente, esto se puede usar para almacenar una lista o árbol de enteros en un solo entero (grande) y recuperar los valores individuales más adelante. Sin embargo, en este caso podemos usar las funciones en el orden opuesto, para permitir que la naturaleza de la biyección funcione para nosotros.

Desempacar un entero en dos enteros consiste básicamente en tres pasos:

  1. Mapa ℤ → ℕ (incluido cero) con un simple "plegado". Es decir, mapear enteros negativos a naturales impares, y enteros no negativos a naturales pares.

  2. Mapa ℕ → ℕ 2 , utilizando la función de emparejamiento de Cantor . Es decir, los naturales se escriben a lo largo de las diagonales de una cuadrícula infinita y devolvemos los índices:

       ...
3  9 ...
2  5 8 ...
1  2 4 7 ...
0  0 1 3 6 ...

   0 1 2 3

    Por ejemplo 8, se asignaría a la pareja (1, 2).

  3. Mapa ℕ 2 → ℤ 2 , utilizando el inverso del paso 1 en cada entero de forma individual. Es decir, los naturales impares se asignan a enteros negativos, e incluso los naturales se asignan a enteros no negativos.

Para agrupar dos enteros en uno, simplemente invertimos cada uno de esos pasos.

Ahora, podemos ver que la estructura de la función de emparejamiento de Cantor codifica convenientemente el triángulo que necesitamos (aunque los valores son off-by-one). Para invertir esas diagonales, todo lo que tenemos que hacer es intercambiar las coordenadas x e y en la cuadrícula.

Desafortunadamente, dado que los tres pasos anteriores se combinan en un solo incorporado Y(o Z), necesitamos deshacer las asignaciones ℤ → ℕ o ℕ → ℤ nosotros mismos. Sin embargo, mientras lo hacemos, podemos guardar un par de bytes utilizando directamente las asignaciones ℕ + → ℤ o ℤ → ℕ + , para solucionar el error off-by-one en la tabla. Así que aquí está el algoritmo completo:

  1. Mapa ℕ + → ℤ usando (n / 2) * (-1) n-1 . Este mapeo se elige de modo que cancele el mapeo implícito ℤ → ℕ durante el desempaquetado, excepto que desplaza el valor hacia abajo en 1.
  2. Descomprima el resultado en dos enteros.
  3. Intercambiarlos.
  4. Empaquete los valores intercambiados en un solo entero nuevamente.
  5. Mapa ℤ → ℕ + usando | 2n | + (n≥0) . Nuevamente, esta asignación se elige de modo que cancele la asignación implícita ℕ → ℤ durante el empaquetado, excepto que eleva el valor en 1.

Con eso fuera del camino, podemos ver el programa:

/o
\i@/...

Esto es simplemente un marco para programas aritméticos lineales con entrada y salida de enteros.

.    Duplicate the input.
2:   Halve it.
e    Push -1.
2,   Pull up the other copy of the input.
t    Decrement.
E    Raise -1 to this power.
*    Multiply. We've now computed (n/2) * (-1)^(n-1).
Y    Unpack.
~    Swap.
Z    Pack.
.H   Duplicate the result and take its absolute value.
2*   Double.
~    Swap with other copy.
.C   Compute k-choose-k. That's 1 for k ≥ 0 and 0 for k < 0.
+    Add. We've now computed |2n| + (n≥0).
Martin Ender
fuente
4

Octava , 71 68 bytes

3 bytes guardados gracias a Conor O'Brien .

x=triu(ones(n=input('')));x(~~x)=1:nnz(x);disp(nonzeros(flip(x))(n))

Esto no funciona para entradas grandes debido a limitaciones de memoria.

Pruébalo en línea!

Explicación

Considere la entrada n = 4. El código primero construye la matriz

 1     1     1     1
 0     1     1     1
 0     0     1     1
 0     0     0     1

Luego se reemplaza entradas no nulas con el fin de columna mayor (hacia abajo, luego de diámetro) por 1, 2, 3...:

 1     2     4     7
 0     3     5     8
 0     0     6     9
 0     0     0    10

Luego voltea la matriz verticalmente:

 0     0     0    10
 0     0     6     9
 0     3     5     8
 1     2     4     7

Finalmente, toma el nenésimo valor distinto de cero en orden de columna principal, que en este caso es 6.

Luis Mendo
fuente
1
@ rahnema1 ¡Eso ees genial! Definitivamente debe publicarlo como respuesta, junto con sus otras muy buenas sugerencias. En cuanto a ans =, nunca estoy seguro de si es válido o no
Luis Mendo
4

Haskell , 31 bytes

r=round
f n=r(sqrt$2*n)^2-r n+1

Pruébalo en línea!

Esta respuesta solo usa la fórmula. Es la respuesta menos interesante aquí, pero también resulta ser la más golfista.

Haskell , 38 36 34 bytes

x!y|x<=y=1-x|v<-y+1=v+(x-y)!v
(!0)

Pruébalo en línea!

(!0) es la función de punto libre que nos preocupa.

Explicación

Permítanme comenzar diciendo que estoy muy feliz con esta respuesta.

La idea básica aquí es que si eliminamos el número triangular más grande más pequeño que nuestra entrada, podemos revertirlo y agregar el número triangular nuevamente. Entonces definimos un operador !, !toma nuestra entrada regular x, pero también toma un número adicional y. yrealiza un seguimiento del tamaño del número triangular creciente. Si x>yqueremos recursivo, disminuimos xpor ye incrementar ypor uno. Entonces lo calculamos (x-y)!(y+1)y le agregamos y+1. Si x<=yhemos alcanzado nuestro caso base, para revertir xla ubicación en la fila del triángulo volvemos 1-x.

Haskell , 54 bytes

f x|u<-div(x^2-x)2=[u+x,u+x-1..u+1]
(!!)$0:(>>=)[1..]f

Pruébalo en línea!

(!!)$0:(>>=)[1..]f es una función sin puntos

Explicación

Lo primero que nos ocupa es f, fes una función que toma xy devuelve el xª ª fila de triángulo a la inversa. Lo hace calculando primero el x-1nd número triangular y asignándolo a u. u<-div(x^2-x)2. Luego devolvemos la lista [u+x,u+x-1..u+1]. u+xes el xnúmero triangular th y el primer número en la fila, u+x-1es uno menos que eso y el segundo número en la fila u+1es uno más que el último número triangular y, por lo tanto, el último número en la fila.

Una vez que tenemos f, formamos una lista (>>=)[1..]f, que es un aplanamiento del triángulo. Agregamos cero al frente 0:para que nuestras respuestas no se compensen con una, y se lo proporcionamos a nuestra función de indexación (!!).

Haskell , 56 bytes

f 0=[0]
f x|u<-f(x-1)!!0=[u+x,u+x-1..u+1]
(!!)$[0..]>>=f

Pruébalo en línea!

Este es 2 bytes más largo pero un poco más elegante en mi opinión.

Asistente de trigo
fuente
3

C (gcc) , 48 bytes

k,j,l;f(n){for(k=j=0;k<n;)l=k,k+=++j;n=1+k-n+l;}

Pruébalo en línea!

Probablemente subóptimo, pero estoy bastante contento con este. Utiliza el hecho de que

NTF N = T N + A057944 ( N ) - N + 1

(Si escribí la fórmula correctamente, eso es).

Conor O'Brien
fuente
No está llamando a return, pero se usa el valor de retorno. Ese es un comportamiento indefinido.
2501
@ 2501 Mientras el programa funcione, está permitido. Y, escribir en el primer argumento de una función es equivalente a devolver un valor.
Conor O'Brien
Y, escribir en el primer argumento de una función es equivalente a devolver un valor. No existe tal cosa en el lenguaje C. El estándar incluso dice explícitamente que usar el valor devuelto de una función que no devuelve es un comportamiento indefinido.
2501
1
@ 2501 Parece confundir el entorno C (gcc) para la especificación C. Sí, el lenguaje C / especificación lo llama indefinido, pero se implementa como tal. Entonces, cuando digo "equivalente", definitivamente me estoy refiriendo a la implementación de C por gcc y la mayoría de los otros compiladores. En PPCG, no escribimos código "perfecto"; mucho código va en contra de las especificaciones por el bien del golf. Como dije, mientras funcione, es una respuesta válida.
Conor O'Brien
@ 2501 Le animo a leer algunos artículos en el meta sitio, particularmente este .
Conor O'Brien
2

05AB1E , 30 bytes

U1V[YLO>X›iYLOX-UY<LO>X+,q}Y>V

Pruébalo en línea!

Eduardo Hoefel
fuente
Estaba a punto de decir "¿Qué? ¿Una respuesta 05AB1E sin Unicode?" pero luego el único personaje que no es ASCII lo arruina ...: P Buena primera respuesta, ¡bienvenido a Programming Puzzles y Code Golf!
clismique
@ Qwerp-Derp ¡Muchas gracias! Recién comencé a aprender este idioma, así que no me sorprende que mi respuesta fuera tan mala.
Eduardo Hoefel
2

Casco , 6 bytes

!ṁ↔´CN

Pruébalo en línea!

Explicación

!ṁ↔´CN  -- implicit input N, for example: 4
   ´ N  -- duplicate the natural numbers:
           [1,2,3,…] [1,2,3,…]
    C   -- cut the second argument into sizes of the first:
           [[1],[2,3],[4,5,6],[7,8,9,10],…]
 ṁ↔     -- map reverse and flatten:
           [1,3,2,6,5,4,10,9,8,7,15,…
!       -- index into that list:
           6
ბიმო
fuente
2

tinylisp , 78 bytes

(d _(q((R N T)(i(l T N)(_(a R 1)N(a T R))(a 2(a T(s T(a N R
(d f(q((N)(_ 2 N 1

Define una función fque realiza la asignación. Pruébalo en línea!

Sin golf

Encontramos el número triangular más pequeño que es mayor o igual que el número de entrada, así como en qué fila del triángulo se encuentra nuestro número. A partir de estos, podemos calcular la versión invertida del número.

  • Si el número triangular actual es menor que N, vuelva a la siguiente fila del triángulo. (Tratamos la fila superior como la fila 2 para simplificar las matemáticas).
  • De lo contrario, la versión invertida de N es (TN) + (TR) +2.

La función principal flipsimplemente llama a la función auxiliar a _flippartir de la fila superior.

(load library)

(def _flip
 (lambda (Num Row Triangular)
  (if (less? Triangular Num)
   (_flip Num (inc Row) (+ Triangular Row))
   (+ 2
    (- Triangular Num)
    (- Triangular Row))))))

(def flip
 (lambda (Num) (_flip Num 2 1)))
DLosc
fuente
1

05AB1E , 9 bytes

·LD£í˜¹<è

Pruébalo en línea!

Explicación

·L          # push range [1 ... 2n]
  D         # duplicate
   £        # split the first list into pieces with size dependent on the second list
    í       # reverse each sublist
     ˜      # flatten
      ¹<è   # get the element at index <input>-1

Desafortunadamente, el aplanamiento de matrices no maneja muy bien las listas más grandes.
Al costo de 1 byte podríamos hacer · t2z + ïn¹-> usando la fórmula matemática floor(sqrt(2*n)+1/2)^2 - n + 1encontrada en OEIS .

Emigna
fuente
1

Lote, 70 bytes.

@set/ai=%2+1,j=%3+i
@if %j% lss %1 %0 %1 %i% %j%
@cmd/cset/ai*i+1-%1

Utiliza un bucle para encontrar el índice del número triangular al menos tan grande como n.

Neil
fuente
0

PHP, 35 bytes

<?=((2*$argn)**.5+.5^0)**2-$argn+1;

La misma fórmula que se utiliza en el enfoque de Arnaulds

Jörg Hülsermann
fuente
0

C #, 46 44 bytes

n=>Math.Pow((int)(Math.Sqrt(2*n)+.5),2)-n+1;

Puerto de E @ solución de Arnauld . ¡Gracias!

  • Pow de 0.5 es Sqrt. ¡2 bytes guardados!
aloisdg dice Reinstate Monica
fuente
0

APL (Dyalog), 27 bytes

Tengo dos soluciones en el mismo bytecount.

Un tren:

⊢⊃⊃∘(,/{⌽(+/⍳⍵-1)+⍳⍵}¨∘⍳)

Pruébalo en línea!

Y un dfn:

{⍵⊃⊃((⍳⍵),.{1+⍵-⍳⍺}+\⍳⍵)}

Pruébalo en línea!

Ambas soluciones primero crean el triángulo invertido y luego extraen el elemento en el índice indicado por el argumento ( 1basado en).

Kritixi Lithos
fuente
0

J, 25 bytes

3 :'>:y-~*:>.-:<:%:>:8*y'

Como explicación, considere f(n) = n(n+1)/2. f(r), dada la fila r, devuelve el número más a la izquierda de la fila rth del triángulo reflejado. Ahora considere g(n) = ceiling[f⁻¹(n)]. g(i), dado el índice i, devuelve la fila en la que se encuentra el índice i. Luego, f(g(n))devuelve el número más a la izquierda de la fila en la que se encuentra el índice n. Entonces, h(n) = f(g(n)) - (n - f(g(n)-1)) + 1es la respuesta al problema anterior.

Simplificando, obtenemos h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1.

Por el aspecto de la fórmula de @ Arnauld, parece que:

ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)].

ljeabmreosn
fuente