Cuenta hacia adelante y hacia atrás y luego dobla

24

Contemos...

Cuenta hasta 2 y vuelve a 1
Cuenta hasta 4 y vuelve a 1
Cuenta hasta 6 y vuelve a 1
... ok, lo tienes ...

junta todo esto y obtendrás la siguiente secuencia

 {1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}

Desafío
Dado un entero n>0para 1 indexado (o n>=0para 0 indexado), genera el enésimo término de esta secuencia

Casos de prueba

Input->Output  

1->1  
68->6  
668->20  
6667->63  
10000->84

Reglas

su programa debe poder calcular soluciones de hasta n = 10000 en menos de un minuto

Este es el , por lo que gana el código más corto en bytes.

Sr. Xcoder
fuente
2
¿Quién decide qué toma un minuto? Una máquina Turing de tiempo óptimo construida a partir de lego tomaría mucho tiempo, mientras que la misma máquina Turing simulada en, digamos, C, presumiblemente tomaría segundos o minutos, dependiendo del procesador en el que se ejecute. Por lo tanto, si presento dicha descripción de la máquina Turing, ¿es válida?
Arthur
2
@ Arthur Creo que puedes entender por qué hice esta restricción ... No quería que un algoritmo tomara "para siempre" encontrar n = 10000 al producir una lista enorme. La mayoría de las personas aquí dieron respuestas brillantes que encontraron millones en segundos.
44
@BillSteihn Creo que la restricción es innecesaria.
Erik the Outgolfer
2
Las respuestas de @EriktheOutgolfer gode golf pueden ser complicadas ... sin la restricción, una respuesta que produzca 10.000 tuplas [1,2 ... 2n..2,1] sería válida. La restricción es solo para respuestas como esta. No veo dónde está el problema. Solo quiero que su respuesta encuentre todos los casos de prueba en un tiempo razonable.
3
@StraklSeth El consenso general aquí es que debería funcionar en teoría, no necesariamente en la práctica.
Erik the Outgolfer

Respuestas:

16

JavaScript (ES7),  59 ... 44  43 bytes

Guardado 1 byte gracias a Titus

Entrada esperada: 1 indexado.

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

Inicialmente inspirado por una fórmula para A004738 , que es una secuencia similar. Pero terminé reescribiéndolo por completo.

Casos de prueba

¿Cómo?

La secuencia se puede organizar como un triángulo, con la parte izquierda en orden ascendente y la parte derecha en orden descendente.

A continuación se muestran las primeras 4 filas, que contienen los primeros 32 términos:

            1 | 2
        1 2 3 | 4 3 2
    1 2 3 4 5 | 6 5 4 3 2
1 2 3 4 5 6 7 | 8 7 6 5 4 3 2

Ahora, introduzcamos algunas variables:

 row  | range   | ascending part              | descending part
 r    | x to y  | 1, 2, ..., i                | 4(r+1)-(i+1), 4(r+1)-(i+2), ...
------+---------+-----------------------------+-----------------------------------------
  0   |  1 -  2 |                           1 | 4-2
  1   |  3 -  8 |                   1   2   3 | 8-4  8-5  8-6
  2   |  9 - 18 |           1   2   3   4   5 | 12-6 12-7 12-8  12-9  12-10
  3   | 19 - 32 |   1   2   3   4   5   6   7 | 16-8 16-9 16-10 16-11 16-12 16-13 16-14

Comenzamos con 2 elementos en la parte superior y agregamos 4 elementos en cada nueva fila. Por lo tanto, el número de elementos en la fila r indexada en 0 se puede expresar como:

a(r) = 4r + 2

La posición inicial x indexada 1 de la fila r viene dada por la suma de todos los términos anteriores en esta serie aritmética más uno, lo que conduce a:

x(r) = r * (2 + a(r - 1)) / 2 + 1
     = r * (2 + 4(r - 1) + 2) / 2 + 1
     = 2r² + 1

Recíprocamente, dada una posición indexada 1 n en la secuencia, la fila correspondiente se puede encontrar con:

r(n) = floor(sqrt((n - 1) / 2))

o como código JS:

r = (~-n / 2) ** 0.5 | 0

Una vez que conocemos r (n) , restamos la posición inicial x (r) menos uno de n :

n -= r * r * 2

Comparamos n con a (r) / 2 + 1 = 2r + 2 para determinar si estamos en la parte ascendente o en la parte descendente:

n < ++r * 2 ?

Si esta expresión es verdadera, devolvemos n . De lo contrario, devolvemos 4 (r + 1) - n . Pero dado que r ya se incrementó en la última declaración, esto se simplifica como:

n : r * 4 - n
Arnauld
fuente
1
Ok, creo que lo entendí. La longitud de cada parte de arriba hacia abajo es 2,6,10,14 ... por lo que la suma crece con el cuadrado del número de filas, de ahí el sqrt. ¡Muy agradable!
JollyJoker
7

Haskell , 37 bytes

(!!)$do k<-[1,3..];[1..k]++[k+1,k..2]

Pruébalo en línea!

Indexado a cero. Genera la lista e indexa en ella. ¡Gracias a Ørjan Johansen por guardar 2 bytes!


Haskell , 38 bytes

(!!)[min(k-r)r|k<-[0,4..],r<-[1..k-2]]

Pruébalo en línea!

Indexado a cero. Genera la lista e indexa en ella.


Haskell , 39 bytes

n%k|n<k=1+min(k-n)n|j<-k+4=(n-k)%j
(%2)

Pruébalo en línea!

Indexado a cero. Un método recursivo.

xnor
fuente
5

Casco , 8 bytes

!…ṁoe1DN

1 indexado. Pruébalo en línea!

Explicación

!…ṁoe1DN  Implicit input (an integer).
       N  Positive integers: [1,2,3,4,...
  ṁo      Map and concatenate
      D   double: [2,4,6,8,...
    e1    then pair with 1: [1,2,1,4,1,6,1,8,...
 …        Fill gaps with ranges: [1,2,1,2,3,4,3,2,1,2,3,4,5,6,...
!         Index with input.
Zgarb
fuente
3

Perl 6 , 29 bytes

{({|(1...$+=2...2)}...*)[$_]}

Pruébalo en línea

Basado en 0

Expandido:

{  # bare block lambda with implicit parameter 「$_」

  (
    # generate an outer sequence

    {           # bare block lambda

      |(        # flatten into outer sequence

        # generate an inner sequence

        1       # start at 1

        ...     # go (upward) towards:

        $       # an anonymous state variable (new one for each outer sequence)
          += 2  # increment by 2

        ...     # go (downward) towards:

        2       # stop at 2 (1 will come from the next inner sequence)

      )
    }

    ...         # keep generating the outer sequence until:
    *           # never stop

  )[ $_ ]       # index into outer sequence
}

La secuencia interna 1...$+=2...2produce

(1, 2).Seq
(1, 2, 3, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2).Seq
...

Para que esté basado en 1, agregue 0,antes del segundo {o agregue -1después$_

Brad Gilbert b2gills
fuente
3

R, 64 bytes

function(n)unlist(sapply(seq(2,n,2),function(x)c(2:x-1,x:2)))[n]

Función que toma un argumento n. Crea un vector 2:ncon incrementos de 2. Para cada uno de estos, se crea el vector 1:(x-1)y x:2. Esto en total será más largo que n. Lo tenemos unlist, para obtener un vector y tomar la nentrada enésima.

JAD
fuente
¿Podrías hacer en 1:n*2lugar de seq(2,n,2)? ¡Será más grande de lo que necesitas, pero eso debería estar bien! Además, no creo que esto haya funcionado seq(2,n,2)de n=1todos modos.
Giuseppe
2

Python 2 , 56 bytes

def f(x):n=int((x/2)**.5);print 2*n-abs(2*n*n+2*n+1-x)+2

Pruébalo en línea!

Esto está indexado a 0.

-1 byte gracias a @JustinMariner

Cómo funciona esto

Observamos que el 1º ngrupo indexado ( 1, 2, ... 2n ..., 2, 1) se produce a partir de elementos numerados del 0 indexado 2(n-1)^2a 2n^2.

Para encontrar el elemento en el índice x, podemos encontrar el número de grupo nque xestá dentro. A partir de eso, calculamos la distancia desde el centro del grupo que xestá. (Esta distancia es abs(2*n**2+2*n+2-x)).

Sin embargo, dado que los elementos disminuyen más lejos del centro de un grupo, restamos la distancia del valor máximo del grupo.

fireflame241
fuente
He jugado golf esta parte: print 2*n-abs(2*n*n+2*n+1-x)+2- 2*n*n+2*npuede ser 2*n*-~ny +2+2*npuede convertirse -~n*2, lo que nos permite moverlo al principio, lo que ahorra bytes ( 53 bytes )
Sr. Xcoder
2

05AB1E , 8 bytes

Código:

ÅÈ€1Ÿ¦¹è

Utiliza la codificación 05AB1E . Pruébalo en línea!

Explicación:

ÅÈ           # Get all even numbers until input (0, 2, ..., input)
  €1         # Insert 1 after each element
    Ÿ        # Inclusive range (e.g. [1, 4, 1] -> [1, 2, 3, 4, 3, 2, 1])
     ¦       # Remove the first element
      ¹è     # Retrieve the element at the input index
Adnan
fuente
55
No funciona correctamente a menos que elimine ¦ , que también guarda un byte ofc :)
Emigna
€1es raro ...
Magic Octopus Urn
2

JavaScript, 39 bytes

f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n
tsh
fuente
2

Gelatina , 10 , 9 bytes

ḤŒḄṖµ€Fị@

Pruébalo en línea!

También 1 indexado, y termina bastante rápido.

¡Un byte guardado gracias a @ErikTheOutgolfer!

Explicación:

Hipotéticamente, digamos que input ( a) es 3.

    µ€      # (Implicit) On each number in range(a):
            #
Ḥ           # Double
            #   [2, 4, 6]
            #
 ŒḄ         # Convert to a range, and Bounce
            #   [[1, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
            #
   Ṗ        # Pop
            #   [[1, 2], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2]]
            #
     F      # Flatten
            #   [1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2]
            #
      ị@    # Grab the item[a]
            #   1
            #
DJMcMayhem
fuente
Su código es equivalente a Ḥ€ŒḄ€Ṗ€Fị@, por lo que puede usar µ€para -1 (tres o más mónadas al comienzo):ḤŒḄṖµ€Fị@
Erik the Outgolfer el
Esto realmente debería ser ḤŒḄṖ<newline> ½ĊÇ€Fị@para que 12 cumpla con el requisito de 10,000 (ejecutar el código de 9 bytes localmente toma aproximadamente 2:20 en mi i7 y usa 7GB)
Jonathan Allan
1

MATL , 15 bytes

li:"@EZv4L)]vG)

Basado en 1.

Pruébalo en línea!

Esto agota el tiempo para los casos de prueba más grandes en TIO, pero termina a tiempo en mi computadora de escritorio (compilador que se ejecuta en MATLAB R2017a). Para mostrar el tiempo transcurrido, agregue Z`al final del código.

>> matl 'li:"@EZv4L)]vG)Z`'
> 10000
84
15.8235379852476

Explicación

El código genera muchos más términos de los necesarios. Específicamente, calcula n"piezas" de la secuencia, donde cada pieza es un conteo ascendente y de regreso a 1.

l       % Push 1
i       % Push input, n
:       % Range [1 2 ...n]
"       % For each k in that range
  @E    %   Push 2*k
  Zv    %   Symmetric range: [1 2 ... 2*k-1 2*k 2*k-1 ... 2 1]
  4L)   %   Remove last entry: [1 2 ... 2*k-1 2*k 2*k-1 ... 2]
]       % End
v       % Concatenate all stack contents into a column vector
G)      % Get n-th entry. Implicitly display
Luis Mendo
fuente
¡bonito! TIO es lento a veces ...
1
Bueno, la principal causa de lentitud aquí es el algoritmo (que genera muchos más términos de los necesarios). Además, el compilador MATL no es particularmente rápido
Luis Mendo
1

Casco , 12 10 bytes

!ṁ§¤+hḣṫİ0

Pruébalo en línea!

1 indexado, funciona bastante rápido

Explicación

!ṁ§¤+hḣṫİ0
 ṁ      İ0    Map the following function over the even numbers and concatenate the results together
  §   ḣṫ      Get the ranges 1-n and n-1, then... 
   ¤+h         remove the last element from both of them and concatenate them together
!             Return the element of the resulting list at the given index
León
fuente
8 bytes usando
Zgarb
@Zgarb es una gran idea y probablemente deberías publicarla como tu respuesta :)
Leo
Hecho.
Zgarb
1

Mathematica, 90 bytes

Flatten[{1}~Join~Table[Join[Rest[p=Range@i],Reverse@Most@p],{i,2,Round[2Sqrt@#],2}]][[#]]&

Pruébalo en línea!

J42161217
fuente
1

Retina , 62 bytes

.+
$*
^((^.|\2..)*)\1.
6$*1$2$2;1
(?=.+;(.+))\1(.+).*;\2.*
$.2

Pruébalo en línea! El enlace incluye casos de prueba. La entrada está indexada en 1. La primera etapa es solo conversión decimal a unaria. La segunda etapa encuentra el número cuadrado más alto sestrictamente menos de la mitad de n; $1es , mientras $2es 2s-1. Calcula dos valores, primero el número de números en la ejecución actual ascendente / descendente, que es 4(s+1) = 4s+4 = 2$2+6, y en segundo lugar, la posición dentro de esa ejecución, que es n-2s² = n-(2$1+1)+1 = n-$&+1, que solo requiere un 1compensar lo 1utilizado para hacer cumplir la estricta desigualdad. La etapa final cuenta desde esa posición hasta el inicio y el final de la carrera y toma el resultado más bajo y lo convierte a decimal.

Neil
fuente
1

Mathematica, 67 bytes

(t=z=1;While[(x=3-4t+2t^2)<#,t++;z=x];If[#-z>2t-2,4t-5+z-#,#-z+1])&

Pruébalo en línea!

J42161217
fuente
1

Perl 5 , 43 + 1 (-p) = 44 bytes

$_=($n=2*int sqrt$_/2)+2-abs$n/2*$n+$n+1-$_

Pruébalo en línea!

Estaba trabajando en una fórmula para calcular el enésimo elemento directamente. Luego vi que @ fireflame241 había hecho ese trabajo, y lo jugué en Perl.

# Perl 5 , 50 + 1 (-n) = 51 bytes

push@r,1..++$",reverse 2..++$"while@r<$_;say$r[$_]

Pruébalo en línea!

Los resultados son 0 indexados.

Xcali
fuente
1

Haskell , 115 81 bytes

y%x=snd(span(<x)$scanl(+)y[y+1,y+3..])!!0
g 1=1
g x|1%x>2%x=1+g(x-1)|1>0=g(x-1)-1

Pruébalo en línea!

Aquí hay algo de magia. Sin embargo, probablemente podría ser más corto si usara un enfoque normal.

Explicación

Primero definimos %. %es una función que toma dos variables x, y y. Construye una lista scanl(+)y[y+1,y+3..]y encuentra el primer elemento de esa lista mayor que x. scanl(+)solo realiza sumas iterativas, para obtener los números triangulares que haríamos scanl(+)0[1..], para obtener los números cuadrados que haríamos scanl(+)0[1,3..]. Las dos listas en particular que construiremos son scanl(+)2[3,5..]y scanl(+)1[2,4..]estos son los puntos de inflexión del patrón.

Ahora definimos la función principal gque toma un x. Si xes uno, lo devolvemos 1porque ese es el primer valor. De lo contrario, verificamos los siguientes dos puntos de inflexión; si la inflexión descendente es mayor 1%x>2x, devolveremos el sucesor o, de lo g$x-1contrario, devolveremos el predecesor de g$x-1.

Ok, pero ¿por qué funciona eso?

En primer lugar, "¿Cuál es la forma en que encontramos vértices?". Es importante tener en cuenta la distancia entre vértices consecutivos del mismo tipo. Notarás que las diferencias aumentan en 2 cada vez. Esto tiene sentido porque las bases de los triángulos se ensanchan en 2 cada vez. Podemos hacer una diferencia constante de la lista usando una lista literal como esta [2,4..]y usamosscanl(+) convertir estas listas en nuestras listas de vértices, en función de la ubicación del primer vértice y la primera diferencia.

Entonces, ahora que tenemos una forma de encontrar vértices hacia arriba y hacia abajo, podemos usar esa información para obtener los valores. Decimos que el primer valor es, de lo 1contrario, tenemos que tomar el sucesor o el predecesor. Si el siguiente vértice es ascendente, queremos tomar el predecesor; de lo contrario, tomamos el sucesor.

Haskell , 56 51 46 bytes

Aquí está mi mejor solución con menos matemáticas y menos bytes.

d x|e<-[1..x-1]=e++map(x+1-)e
(([1..]>>=d)!!0)

Pruébalo en línea!

Asistente de trigo
fuente
1

Pyke , 14 bytes

SF}SDtO_+)sQt@

Pruébalo aquí!

S              -    range(1, input)
 F}SDtO_+)     -   for i in ^:
  }            -      ^ * 2
   S           -     range(1, ^)
        +      -    ^ + v
     tO_       -     ^[1:-1:-1]
          s    -  sum(^)
           Qt@ - ^[input-1]
Azul
fuente
1

C # (.NET Core) , 120 bytes

Explicación: bastante simple, el primer bucle anidado sube a nuestro máximo, el segundo vuelve a bajar a 2. La repetición para cada múltiplo de 2.

x=>{var a=0;for(int i=2,j=0;j<x;i+=2){for(var b=1;b<=i&j<x;b++,j++){a=b;}for(var c=i-1;c>1&j<x;c--,j++){a=c;}}return a;}

Pruébalo en línea!

Dennis.Verweij
fuente
1

Ruby , 78 75 bytes

Guardado 1 byte gracias a Step Hen

Guardado 1 byte gracias al Sr. Xcoder

->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a<2;a+=c<1?-1:1};a}

Pruébalo en línea!

Espero poder obtener algunos consejos para reducir más el bytecount. Traté de adoptar un enfoque simple.

usuario886
fuente
Bienvenido a PPCG! c=1 ifse puede jugar al golfc=1if
Stephen
76 bytes:->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a==1;a+=c<1?-1:1};a}
Sr. Xcoder
1

Java (OpenJDK 8) , 53 bytes

n->{int i=2;for(;n>i;i+=4)n-=i;return n>i/2?i-n+2:n;}

Pruébalo en línea!

-2 bytes gracias a Nevay.

1 indexado.

TL; DR Dividimos la secuencia en trozos convenientes, encontramos que el trozo nestá adentro, luego encontramos la nthposición en el trozo.

Aquí, podemos dividir la secuencia como [[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...], lo que nos da tamaños de fragmentos de 4i-2. Comenzando con i=2, restamos ide n, esencialmente moviendo hacia arriba un trozo a la vez. Una vez que satisfacemos n<=i, sabemos nque ahora es la posición del valor correcto en el fragmento actual.

Luego obtenemos el valor comparándolo ncon iel tamaño del fragmento. El punto medio de cada fragmento es igual a i/2+1; si nes menor que esto, simplemente regresamos n. Si nes mayor, volvemos i-n+2.

Ejemplo

n = 16, i = 2

Is n > i? Yes, n = n - 2 = 14, i = i + 4 = 6
Is n > i? Yes, n = n - 6 = 8, i = i + 4 = 10
Is n > i? No, stop looping.
10 / 2 + 1 = 6
Is n > 6? Yes, return i - n + 2 = 8 - 6 + 2 = 4
Xanderhall
fuente
No necesitas +1, return n>i/2?i-n+2:nes suficiente.
Nevay
Huh Gracias, división entera.
Xanderhall
1

Python 2 , 5! bytes (120 bytes: P)

r=range
a=[]
for i in r(2,998,2): 
	for j in r(1,i+1): a.append(j)
	for j in r(i-1,1,-1): a.append(j)
print a[input()-1]

Pruébalo en línea!

Directo, hace la lista y luego toma el elemento input

Husnain Raza
fuente
¡Gracias a quien haya votado! ¡Ahora tengo 50 repeticiones para poder comentar!
toques
0

Python 3 , 184156 bytes

l,n,r=list,next,range
h=lambda x:l(r(1,x))+l(r(x-2,1,-1))
def g():
	x=3
	while True:yield from h(x);x+=2
def f(i):
	x=g()
	for _ in r(i-1):n(x)
	return n(x)

Pruébalo en línea!

Golf con generador de Python para evaluación "perezosa"

Conner Johnston
fuente
0

QBIC , 47 bytes

g=q{p=p+1~p=:|_Xg\g=g+q~g=1or g>=r|r=r+1┘q=q*-1

Explicación

g=q         var g is the current value of the sequence; set to 1 at the start
{           DO infinitely
p=p+1       raise the step counter (var p)
~p=:|_Xg    IF p equals the input term a (read from cmd line) THEN QUIT, printing g
\           ELSE
g=g+q       raise (or decrement) g by q (q is 1 at the start of QBIC)
~g=1        IF g is at the lower bound of a subsequence
    or g>=r OR g is at the upper bound (r start as 2 in QBIC)
|r=r+1      THEN increment r (this happens once on lower bound, and once on upper, 
            total of 2 raise per subsequence)
┘q=q*-1     and switch q from 1 to -1
Steenbergh
fuente
0

Röda , 54 bytes

f n{seq 1,n|{|i|seq 1,2*i;seq 2*i-1,2}_|head n+2|tail}

Pruébalo en línea!

Llamar con: try f(n)

Esta función devuelve rápidamente la respuesta, pero luego realiza algunos cálculos innecesarios y finalmente se queda sin memoria.

Como la función devuelve la respuesta real poco después de ser llamada (claramente menos de un minuto), creo que esta respuesta es válida.

(En Röda, las funciones pueden devolver valores antes de que salgan debido al paralelismo).

fergusq
fuente
0

C # (.NET Core) , 99 95 86 bytes

n=>{int i=1,t=2,d=0;for(;n>1;){i+=1-2*d;if(i==t){d++;t+=2;}if(i==1)d--;n--;}return i;}

Pruébalo en línea!

Función lambda que toma y devuelve un entero. Bucle único que maneja el conteo hacia arriba y hacia abajo.

jkelm
fuente
0

PHP, 65 + 1 bytes

for($x=$d=$z=1;--$argn;)$d=($x+=$d)>1?$x>$z?-1:$d:!!$z+=2;echo$x;

Ejecútelo como tubería -Ro pruébelo en línea (o elimine el comentario de una de las otras versiones).

Un puerto de JavaScript recursivo de tsh toma 66 bytes:

function f($n,$t=2){return$t<2*$n?$t<$n?f($n-$t,$t+4):$t-$n+2:$n;}

La solución de un puerto de Arnauld requiere 62 + 1:

$n=$argn;echo($n-=($r=(~-$n/2)**.5|0)*$r*2)<++$r*2?$n:$r*4-$n;

Un puerto golfizado de Java de Xanderhall tiene el código más corto hasta ahora (55 + 1 bytes):

for($n=$argn;$n+2>$i+=4;)$n-=$i-2;echo$n*2>$i?$i-$n:$n;
Titus
fuente