Affiche le Nième terme de la séquence de Van Eck.

La séquence de Van Eck est définie comme:

• Commence par 0.
• Si le dernier terme est la première occurrence de ce terme, le prochain terme est 0.
• Si le dernier terme s'est déjà produit, le nombre suivant de pas en arrière correspond au dernier événement.

https://oeis.org/A181391

https://www.youtube.com/watch?v=etMJxB-igrc

https://www.youtube.com/watch?v=8VrnqRU7BVU

Séquence: 0,0,1,0,2,0,2,2,1,6,0,5,0,2, ...

Tests:

Entrée | Sortie

• 1 | 0
• 8 | 2
• 19 | 5
• 27 | 9
• 52 | 42
• 64 | 0

MODIFIER

1 indexé est préféré, 0 indexé est acceptable; cela pourrait changer certaines des solutions déjà présentées.

Juste le Nième terme s'il vous plaît.

Idem (à l'exception de la partie déjà affichée), il semble que les golfeurs et les observateurs de numérosphiles se chevauchent de manière décente.

JavaScript (ES6),  46 41  37 octets

n=>(g=p=>--n?g(g[p]-n|0,g[p]=n):p)(0)

Essayez-le en ligne!

Comment?

Nous n'avons pas besoin de stocker la séquence complète. Nous devons seulement garder trace de la dernière position de chaque entier qui apparaît dans la séquence. Nous utilisons l'objet sous-jacent de la fonction récursive $g$ à cette fin.

Pour un terme donné $p$ , nous n'avons pas besoin non plus de régler $g[p]$ sur sa position absolue réelle dans la séquence car nous ne sommes intéressés que par la distance avec la position actuelle. C'est pourquoi nous pouvons simplement stocker la valeur actuelle de l'entrée $n$ , qui sert de compteur de décrémentation dans le code.

Par conséquent, la distance est donnée par $g[p]-n$ . Cela équivaut à NaN s'il s'agit de la première occurrence de $p$ , qui peut facilement être convertie en $0$ attendu .

Commenté

n => (             // n = input
  g = p =>         // g = recursive function taking p = previous term of the sequence
                   //     g is also used as an object to store the last position of
                   //     each integer found in the sequence
    --n ?          // decrement n; if it's not equal to 0:
      g(           //   do a recursive call:
        g[p] - n   //     subtract n from the last position of p
                   //     if g[p] is undefined, the above expression evaluates to NaN
        | 0,       //     in which case we coerce it to 0 instead
        g[p] = n   //     update g[p] to n
      )            //   end of recursive call
    :              // else:
      p            //   we've reached the requested term: stop recursion and return it
)(0)               // initial call to g with p = 0

Python 3 , 69 63 62 octets

f=lambda n,l=0,*s:f(n-1,l in s and~s.index(l),l,*s)if n else-l

Essayez-le en ligne!

_{Remarque: comme l'a mentionné Erik the Outgolfer, ce code fonctionne également dans Python 2.}

0-indexé (bien que, pour être tout à fait pervers, vous pouvez le faire -1 indexé en changeant if nà if~n: P)

Utilise le superbe "opérateur étoile" de décompression de Python, pour construire la série de manière récursive, jusqu'à natteindre zéro.

La fonction construit la série dans l'ordre inverse, pour éviter de l'inverser pour la recherche. De plus, il stocke les négations de tous les éléments, car leur conversion à la fin était libre (sinon, -il aurait fallu que ce soit un espace) et cela nous évite de perdre un octet en cours de route, en utilisant ~s.index(l)plutôt que -~s.index(l).

Pourrait être de 51 octets si les tuples Python avaient les mêmes findfonctions que les chaînes (renvoyer -1 si non trouvé, au lieu de générer une erreur), mais pas de chance ...

R , 62 octets

function(n){while(sum(F|1)<n)F=c(match(F[1],F[-1],0),F)
+F[1]}

Essayez-le en ligne!

Construit la liste à l’inverse; matchrenvoie le premier index de F[1](la valeur précédente) dans F[-1](le reste de la liste), retournant 0si aucune correspondance n'est trouvée.

Fest initialisé FALSEet forcé 0lors du premier passage de la whileboucle.

Perl 6 , 47 42 octets

-5 octets grâce à nwellnhof

{({+grep(@_[*-1],:k,[R,] @_)[1]}...*)[$_]}

Essayez-le en ligne!

Codeblock anonyme qui sort l'élément 0-indexé dans la séquence.

Explication:

{                                            } # Anonymous codeblock
 (                                      )[$_]  # Return the nth element
                                    ...*       # Of the infinite sequence
  {                            }  # Where each element is
    grep(        :k        )[1]   # The key of the second occurrence
         @_[*-1],                 # Of the most recent element
                   ,[R,] @_       # In the reversed sequence so far
   +     # And numify the Nil to 0 if the element is not found

Bourne shell, 102 octets

until [ 0"$i" -eq $1 ];do i=$((${i:-0}+1)) a=${n:-0};eval 'n=$(($i-${m'$a:-$i'}))' m$a=$i;done;echo $a

essayez-le en ligne

Stax , 10 à 9 octets

é"▬π²"ô↕j

Exécuter et déboguer

Si l'indexation basée sur 0 est autorisée:

Stax , 8 octets

à┐æ8Å/[┤

Exécuter et déboguer

J , ²⁹ 23 octets

1{(,~#|1+}.i.{.)@]^:[&0

Essayez-le en ligne!

Le vrai travail se fait dans le verbe d'itération du verbe de pouvoir ^:, qui itère autant de fois que l'argument [, en commençant l'itération avec la valeur constante 0 &0...

• (#|1+}.i.{.)C'est ce que itère. Le décomposer ...
• }.i.{.Trouvez l'index de i.la tête de liste {.dans la queue de la liste }.. Cela retournera un index basé sur 0, donc si l'élément actuel est trouvé 1 précédent, il retournera 0. S'il n'est pas trouvé, il retournera la longueur de la liste, c'est-à-dire la longueur de la queue.
• 1+Ajoutez un à la valeur à corriger pour l'indexation basée sur 0, étant donné que "quelle distance en arrière" de Ven Eck est basé sur 1. Notez que s'il n'a pas été trouvé, la valeur sera désormais la longueur de la liste complète.
• #|Renvoie le reste de la valeur calculée à l'étape précédente, lorsqu'elle est divisée par la longueur de la liste complète. Notez que ceci transforme "non trouvé" en 0, mais laisse toutes les autres valeurs inchangées.
• ,~Ajoutez la nouvelle valeur au début de la liste. Nous utilisons l'avant plutôt que le dernier pour plus de commodité.
• 1{ renvoie le 2e élément de la liste, car nous en avons calculé un trop souvent, car il est plus court.

Python , 51 octets

f=lambda n,i=1:n>i and[f(n,i+1),i][f(n-1)==f(n+~i)]

Essayez-le en ligne!

Sorties Falsepour 0. Implémente littéralement la spécification, en recherchant le plus petit entier positif itel que f(n-1)==f(n-i-1). Si une telle recherche aboutit à i>=n, l'élément précédent n'est pas apparu auparavant et nous produisons 0.

Au lieu de faire quelque chose de raisonnable, comme de stocker des valeurs antérieures dans une liste, la fonction les recalcule de manière récursive à partir de zéro, chaque fois que cela est nécessaire, et parfois même si elles ne le sont pas. Cela rend la fonction très lente pour les entrées supérieures à 10 ou plus.

APL (Dyalog Unicode) , 19 17 octets ^{SBCS de}

Un grand merci à ngn, Adám, Richard Park et H.PWiz pour leur aide dans l’écriture et le golf de cette réponse dans The APL Orchard. , un endroit formidable pour apprendre l’APL et obtenir de l’aide.

Éditez: -2 octets d'Adám.

⊃(⊢,⍨≢|1∘↓⍳⊃)⍣⎕-1

Essayez-le en ligne!

Explication

⊃(⊢,⍨≢|1∘↓⍳⊃)⍣⎕-1

                 -1  We initialize our array of results with -1.
 (           )⍣⎕    ⍣ repeats the train (in parentheses) our input, ⎕, times.
        1∘↓⍳⊃        We take the index of the head (our last element in the sequence).
                     To signify "element not found", this returns the length of the array.
      ≢|             We take our index modulo the length of the array.
                     This turns our "element not found" from the length of the array to 0.
  ⊢,⍨                And we prepend to our array.
⊃                    Finally, we return the first element of the array,
                     which is the most recently-generated.
                     This is the ⍵-th element of the Van Eck sequence.

Wolfram Language (Mathematica) , 48 octets

#<1||Last[#-1-Array[#0,#-2]~Position~#0[#-1],0]&

Essayez-le en ligne!

Les valeurs non nulles sont renvoyées sous forme de listes de singleton .

05AB1E , 8 octets

F¯Rćk>Dˆ

Essayez-le en ligne ou sortez le premier$n$ valeurs dans la liste .

Explication:

F         # Loop the (implicit) input amount of times:
 ¯        #  Push the global array
  R       #  Reverse it
   ć      #  Extract the head; push the remainder and the head to the stack
    k     #  Get the 0-based index of the head in the remainder (-1 if not found)
     >    #  Increase it by 1 to make it 1-indexed (or 0 if not found)
      Dˆ  #  Add a copy to the global array
          # (after the loop, output the top of the stack implicitly as result,
          #  which is why we need the `D`/duplicate)

Java, 96 80 76 octets

n->{int i,v=0,m[]=new int[n];for(;--n>0;m[v]=n,v=i<1?0:i-n)i=m[v];return v;}

Non obscurci:

Function<Integer, Integer> vanEck =
n -> {

    int i;                  // i is the value of n when v was previously encountered
    int v = 0;              // v is the current element of vanEck sequence
    int[] m = new int[n];   // m[v] is the value of n when v was previously encountered

    while (--n > 0) {       // n is used as a decrementing counter

        i = m[v];
        m[v] = n;
        v = i == 0 ? 0 : i - n;
    }

    return v;
};

Charbon de bois , 23 octets

≔⁰θＦ⊖Ｎ«≔⊕⌕⮌υθη⊞υθ≔ηθ»Ｉθ

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

≔⁰θ

Définissez le premier terme sur 0.

Ｆ⊖Ｎ«

n-1Temps de boucle . (Si l'indexation 0 est acceptable, vous ⊖pouvez la supprimer pour une sauvegarde de 1 octet.)

≔⊕⌕⮌υθη

Le terme suivant est l'index incrémenté du terme actuel dans la liste inversée des termes précédents.

⊞υθ

Ajoutez le terme actuel à la liste des termes précédents.

≔ηθ

Définissez le terme actuel sur le prochain terme.

»Ｉθ

Imprimer le terme actuel à la fin de la boucle.

Gelée , 7 octets

Ḷ߀ṚiḢ$

Essayez-le en ligne!

0 indexé.

Gelée , 8 octets

ẎiḢ$;µ¡Ḣ

Un lien monadique acceptant un entier positif, $n$qui donne la $n^{th}$ terme de la séquence de Van Eck.

Essayez-le en ligne!

Comment?

ẎiḢ$;µ¡Ḣ - Link: n
     µ¡  - repeat this monadic link n times - i.e. f(f(...f(n)...)):
         - (call the current argument L)
Ẏ        -   tighten (ensures we have a copy of L, so that Ḣ doesn't alter it)
   $     -   last two links as a monad:
  Ḣ      -     head (pop off & yield leftmost of the copy)
 i       -     first index (of that in the rest) or 0 if not found
    ;    -   concatenate with L
       Ḣ - head

Notez que sans la finale, Ḣnous avons effectivement recueilli[a(n), a(n-1), ..., a(2), a(1), n]

C (gcc) , 63 octets

f(n){n=g(n,--n);}g(n,i){n=n>0?f(--n)-f(i)?g(n,i)+!!g(n,i):1:0;}

Essayez-le en ligne!

0 indexé.

Haskell , 68 ans 67 66 octets

Implémentation assez simple (utilisant une indexation basée sur 0).

f n|all((/=f(n-1)).f)[0..n-2]=0|m<-n-1=[k|k<-[1..],f(m-k)==f m]!!0

Essayez-le en ligne!

Haskell, 61 octets

(([]#0)1!!)
(l#n)i=n:(((n,i):l)#maybe 0(i-)(lookup n l))(i+1)

Indexation basée sur 0.

Essayez-le en ligne!

Japt -h , 11 octets

@ÒZÔÅbX}hTo

L'essayer

C # (compilateur interactif Visual C #) , 77 octets

n=>{int i,v=0;for(var m=new int[n];--n>0;m[v]=n,v=i<1?0:i-n)i=m[v];return v;}

Essayez-le en ligne!

A peu près un portage de la réponse Java à ce stade.

Python 3 , 128 114 111 102 99 octets

102 -> 99 octets, grâce à Jonathan Frech

f=lambda n,i=1,l=[0]:f(n,i+1,l+[l[i-2::-1].index(l[-1])+1if l[-1]in l[:-1]else 0])if n>i else l[-1]

Essayez-le en ligne!

Perl 5 ( -p), 42 octets

map{($\,$\{$\})=0|$\{$\};$_++for%\}1..$_}{

Essayez-le en ligne!

Python 3 , 112 octets

a=[0]
for _ in a*int(input()):k=a[-1];a+=k in a[:-1]and[a[::-1].index(k)+~a[-2::-1].index(k)]or[0]
print(-a[-2])

Essayez-le en ligne!

-3 octets grâce à mypetlion

Rouge , 106 95 octets

func[n][b: copy[0]loop n[insert b either not find t: next b
b/1[0][-1 + index? find t b/1]]b/2]

Essayez-le en ligne!

CJam (15 octets)

0a{_(#)\+}qi*0=

Démo en ligne . Ceci est un programme complet et indexé par 0.

Dissection

0a      e# Push the array [0]
{       e# Loop...
  _(#   e#   Copy the array, pop the first element, and find its index in the array
  )\+   e#   Increment and prepend
}qi*    e# ... n times, where n is read from stdin
0=      e# Take the first element of the array

Clojure, 69 octets

#((fn f[i c t](if(= i 1)t(f(dec i)(assoc c t i)(-(or(c t)i)i))))%{}0)

Malheureusement, une approche plus fonctionnelle semble être plus longue.

DC, 94 91 90 octets

L'entrée est prise pendant le programme. Enregistrez ceci dans un fichier puis faites "dc" pour le lancer. Ce n'est certainement pas le plus court, mais je m'amuse avec des défis comme ceux-ci en dc L'entrée est un index basé sur 1, selon les préférences.

[st1si0swlbxltlwlu1-sulu0!=m]sm[dlt=qSsli1+siz0!=b0siLs]sb[0pq]sf[lisw2Q]sq?2-dsu1>f0dlmxp

Main control macro
[st                         ]sm   save top value as target
[  1si0sw                   ]sm   reset i to 1 and w to 0
[        lbx                ]sm   execute macro b to get next value in w
[           ltlw            ]sm   restore target to the stack and add w to the stack
[               lu1-su      ]sm   decrement the user inputted variable
[                     lu0!=m]sm   if the user inputted variable is not 0 recurse

Next value finder macro
[dlt=q                  ]sb     if the value on the stack is the target, quit
[     Ss                ]sb     save top value to s register
[       li1+si          ]sb     increment i register
[             z0!=b     ]sb     recurse if still more values            
[                  0si  ]sb     set i to 0 (will be saved to w if relevant)
[                     Ls]sb     move top value of s register to stack

[lisw2Q]sq   Load i, save it to w, and then quit this macro and the one that called it

[0pq]sf print 0 and quit the program
```

C ++ (clang) , 241 235 234 219 197 189 octets

197 -> 189 octets, grâce à ceilingcat

#import<bits/stdc++.h>
int f(int n,int i=0,std::vector<int>l={0}){return~-n>i?l.push_back(find(begin(l),end(l)-1,l[i])-end(l)+1?find(rbegin(l)+1,rend(l),l[i])-rbegin(l):0),f(n,i+1,l):l[i];}

Essayez-le en ligne!

Pyth , 18 octets

VQ=Y+?YhxtYhY0Y;hY

Essayez-le en ligne!

Construit la séquence en sens inverse et affiche le premier élément (dernier terme de la séquence).

VQ                 # for N in range(Q) (Q=input)
  =Y+         Y    # Y.prepend(
        xtY        #   Y[1:].index(    )
           hY      #               Y[0]
       h           #                     +1
     ?Y      0     #                        if Y else 0)
               ;hY # end for loop and print Y[0]