Comptons...

Compter jusqu'à 2 et revenir à 1
Compter jusqu'à 4 et revenir à 1
Compter jusqu'à 6 et revenir à 1
... ok vous l'avez compris ...

mettez tout cela ensemble et vous obtiendrez la séquence suivante

 {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...}

Défi
Étant donné un entier n>0pour 1-indexé (ou n>=0pour 0-indexé), sortez le nième terme de cette séquence

Cas de test

Input->Output  

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

Règles

votre programme doit être capable de calculer des solutions jusqu'à n = 10000 en moins d'une minute

C'est le code-golf , donc le code le plus court en octets gagne!

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

1 octet enregistré grâce à Titus

Entrée attendue: 1 indexée.

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

Initialement inspiré d'une formule pour A004738 , qui est une séquence similaire. Mais j'ai fini par le réécrire entièrement.

Cas de test

let f=

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

console.log(f(1))     // -> 1
console.log(f(68))    // -> 6
console.log(f(668))   // -> 20
console.log(f(6667))  // -> 63
console.log(f(10000)) // -> 84

Comment?

La séquence peut être organisée en triangle, avec la partie gauche en ordre croissant et la partie droite en ordre décroissant.

Voici les 4 premières lignes, contenant les 32 premiers termes:

            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

Maintenant, introduisons quelques 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

Nous commençons avec 2 éléments en haut et ajoutons 4 éléments à chaque nouvelle ligne. Par conséquent, le nombre d'éléments sur la ligne r indexée 0 peut être exprimé comme suit:

a(r) = 4r + 2

La position de départ x indexée 1 de la ligne r est donnée par la somme de tous les termes précédents de cette série arithmétique plus un, ce qui conduit à:

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

Réciproquement, étant donné une position n indexée 1 dans la séquence, la ligne correspondante peut être trouvée avec:

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

ou comme code JS:

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

Une fois que nous connaissons r (n) , nous soustrayons la position de départ x (r) moins un de n :

n -= r * r * 2

Nous comparons n avec a (r) / 2 + 1 = 2r + 2 pour savoir si nous sommes dans la partie ascendante ou descendante:

n < ++r * 2 ?

Si cette expression est vraie, nous retournons n . Sinon, nous retournons 4 (r + 1) - n . Mais puisque r a déjà été incrémenté dans la dernière instruction, cela est simplifié comme suit:

n : r * 4 - n

Haskell , 37 octets

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

Essayez-le en ligne!

Zéro indexé. Génère la liste et y indexe. Merci à Ørjan Johansen pour avoir économisé 2 octets!

Haskell , 38 octets

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

Essayez-le en ligne!

Zéro indexé. Génère la liste et y indexe.

Haskell , 39 octets

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

Essayez-le en ligne!

Zéro indexé. Une méthode récursive.

Python , 46 octets

f=lambda n,k=2:-~min(n,k-n)*(n<k)or f(n-k,k+4)

Essayez-le en ligne!

Zéro indexé.

Husk , 8 octets

!…ṁoe1DN

1 indexé. Essayez-le en ligne!

Explication

!…ṁ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.

Perl 6 , 29 octets

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

Essayez-le en ligne

Basé sur 0

Étendu:

{  # 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 séquence intérieure 1...$+=2...2produit

(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
...

Pour qu'il soit basé sur 1, ajoutez 0,avant le second {ou ajoutez -1après$_

R, 64 octets

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

Fonction qui prend un argument n. Il crée un vecteur 2:navec des incréments de 2. Pour chacun d'eux, le vecteur 1:(x-1)et x:2est créé. Au total, cela sera plus long que n. Nous l'avons unlist, pour obtenir un vecteur et prendre la n-ième entrée.

Python 2 , 56 octets

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

Essayez-le en ligne!

Ceci est indexé 0.

-1 octet grâce à @JustinMariner

Comment cela fonctionne

Nous notons que le 1-indexé n-ème groupe ( 1, 2, ... 2n ..., 2, 1) se produit à partir des éléments numérotés de 0 2(n-1)^2à 2n^2.

Pour trouver l'élément à l'index x, nous pouvons trouver le numéro de groupe nqui xest dedans. À partir de cela, nous calculons la distance du centre du groupe qui xest. (Cette distance est abs(2*n**2+2*n+2-x)).

Cependant, comme les éléments diminuent encore plus loin du centre d'un groupe, nous soustrayons la distance de la valeur maximale du groupe.

05AB1E , 8 octets

Code:

ÅÈ€1Ÿ¦¹è

Utilise l' encodage 05AB1E . Essayez-le en ligne!

Explication:

ÅÈ           # 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

JavaScript, 39 octets

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

Gelée , 10 , 9 octets

ḤŒḄṖµ€Fị@

Essayez-le en ligne!

Aussi 1 indexé, et se termine assez rapidement.

Un octet enregistré grâce à @ErikTheOutgolfer!

Explication:

Hypothétiquement, disons que l'entrée ( a) est 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
            #

MATL , 15 octets

li:"@EZv4L)]vG)

1 basé.

Essayez-le en ligne!

Cela arrive à expiration pour les plus grands cas de test de TIO, mais se termine à temps sur mon ordinateur de bureau (compilateur fonctionnant sur MATLAB R2017a). Pour afficher le temps écoulé, ajoutez Z`à la fin du code.

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

Explication

Le code génère beaucoup plus de termes que nécessaire. Plus précisément, il calcule des n"morceaux" de la séquence, où chaque morceau est un décompte vers le haut et retour à 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

Husk , 12 10 octets

!ṁ§¤+hḣṫİ0

Essayez-le en ligne!

1 indexé, fonctionne assez rapidement

Explication

!ṁ§¤+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

Mathematica, 90 octets

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

Essayez-le en ligne!

Rétine , 62 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. L'entrée est indexée sur 1. La première étape est juste une conversion décimale en unaire. La deuxième étape trouve le nombre carré le plus élevé sstrictement inférieur à la moitié de n; $1est s², tout $2est 2s-1. Il calcule deux valeurs, premièrement le nombre de nombres dans la montée / descente actuelle, qui est 4(s+1) = 4s+4 = 2$2+6, et deuxièmement la position dans cette course, qui estn-2s² = n-(2$1+1)+1 = n-$&+1 , ce qui nécessite juste un 1pour compenser le 1utilisé pour appliquer l'inégalité stricte. L'étape finale compte ensuite à partir de cette position jusqu'au début et à la fin de la course et prend le résultat inférieur et le convertit en décimal.

Mathematica, 67 octets

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

Essayez-le en ligne!

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

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

Essayez-le en ligne!

Je travaillais sur une formule pour calculer directement le n-ième élément. Puis j'ai vu que @ fireflame241 avait fait ce travail, et je l'ai joué au golf dans Perl.

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

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

Essayez-le en ligne!

Les résultats sont indexés à 0.

Haskell , 115 81 octets

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

Essayez-le en ligne!

Il y a de la magie ici. Cela pourrait probablement être plus court si j'utilisais une approche normale.

Explication

Nous définissons d'abord %. %est une fonction qui prend deux variables x, et y. Il construit une liste scanl(+)y[y+1,y+3..]et trouve le premier élément de cette liste supérieur à x. scanl(+)effectue simplement des sommes itératives, pour obtenir les nombres triangulaires que nous ferions scanl(+)0[1..], pour obtenir les nombres carrés que nous ferions scanl(+)0[1,3..]. Les deux listes en particulier que nous allons construire sont scanl(+)2[3,5..]et scanl(+)1[2,4..]ce sont les points d'inflexion du motif.

Maintenant, nous définissons la fonction principale gqui prend un x. Si xc'est un, nous revenons 1car c'est la première valeur. Sinon, nous vérifions les deux points d'inflexion suivants, si l'inflexion vers le bas est plus grande, 1%x>2xnous renvoyons le successeur g$x-1sinon nous retournons le prédécesseur deg$x-1 .

Ok mais pourquoi ça marche?

Tout d'abord "Quelle est la façon dont nous trouvons les sommets?". Il est important de noter la distance entre les sommets consécutifs du même type. Vous remarquerez que les différences augmentent de 2 à chaque fois. Cela a du sens car les bases des triangles s'élargissent de 2 fois à chaque fois. Nous pouvons faire une différence constante de liste en utilisant un littéral de liste comme ça [2,4..]et nous utilisonsscanl(+) pour transformer ces listes en listes de sommets, en fonction de l'emplacement du premier sommet et de la première différence.

Alors maintenant que nous avons un moyen de trouver des sommets vers le haut et vers le bas, nous pouvons utiliser ces informations pour obtenir les valeurs. Nous disons que la première valeur est 1sinon nous devons prendre soit le successeur soit le prédécesseur. Si le sommet suivant est vers le haut, nous voulons prendre le prédécesseur, sinon nous prenons le successeur.

Haskell , 56 51 46 octets

Voici ma meilleure solution avec moins de mathématiques et moins d'octets.

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

Essayez-le en ligne!

Pyke , 14 octets

SF}SDtO_+)sQt@

Essayez-le ici!

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

C # (.NET Core) , 120 octets

Explication: assez simple, la première boucle imbriquée grimpe à notre maximum, la seconde redescend à 2. La répétition pour chaque multiple 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;}

Essayez-le en ligne!

Rubis , 78 75 octets

1 octet enregistré grâce à Step Hen

1 octet enregistré grâce à M. 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}

Essayez-le en ligne!

J'espère que je pourrai obtenir quelques conseils pour réduire davantage le nombre de bytes. J'ai essayé d'adopter une approche simple.

Java (OpenJDK 8) , 53 octets

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

Essayez-le en ligne!

-2 octets grâce à Nevay.

1 indexé.

TL; DR Nous divisons la séquence en morceaux pratiques, trouvons que le morceau nest dedans , puis trouvons lenth position dans le morceau.

Ici, nous pouvons diviser la séquence comme [[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...], ce qui nous donne des tailles de morceaux de 4i-2. A partir de i=2, nous soustrayons à ipartir n, essentiellement déplacer vers le haut un morceau à la fois. Une fois que nous sommes satisfaits n<=i, nous savonsn maintenant que la position de la valeur correcte est dans le bloc actuel.

Nous obtenons ensuite la valeur en la comparant nà ila taille du morceau. Le milieu de chaque morceau est égal à i/2+1; s'il nest inférieur à cela, nous revenons simplement n. Si nest plus grand, nous revenonsi-n+2 .

Exemple

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

Python 2 , 5! octets (120 octets: 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]

Essayez-le en ligne!

Simple, fait la liste et prend ensuite l'élément d'entrée

Python 3 , 184 156 octets

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)

Essayez-le en ligne!

golfé avec un générateur Python pour une évaluation "paresseuse"

QBIC , 47 octets

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

Explication

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

Röda , 54 octets

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

Essayez-le en ligne!

Appeler avec: try f(n)

Cette fonction renvoie rapidement la réponse, mais après cela fait des calculs inutiles et finit par manquer de mémoire.

Comme la fonction renvoie la réponse réelle peu de temps après son appel (clairement en moins d'une minute), je pense que cette réponse est valide.

(Dans Röda, les fonctions peuvent renvoyer des valeurs avant leur sortie en raison du parallélisme.)

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

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;}

Essayez-le en ligne!

Fonction lambda qui prend et retourne un entier. Boucle unique qui gère le comptage de haut en bas.

PHP, 65 + 1 octets

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

Exécutez en tant que pipe avec -Rou essayez-le en ligne (ou décommentez l'une des autres versions).

Un port de JavaScript récursif de tsh prend 66 octets:

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

Un port de la solution d'Arnauld prend 62 + 1:

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

Un port de golf de Java de Xanderhall possède le code le plus court à ce jour (55 + 1 octets):

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

Pyth ,  19  18 octets

-yhKs@/Q2 2a*yKhKt

Essayez-le ici!