Nter Term von Van Eck Sequence

41

Geben Sie den N-ten Term der Van-Eck-Sequenz aus.

Van-Eck-Sequenz ist definiert als:

  • Beginnt mit 0.
  • Wenn der letzte Term das erste Vorkommen dieses Terms ist, ist der nächste Term 0.
  • Wenn der letzte Begriff zuvor aufgetreten ist, gibt der nächste Begriff an, um wie viele Schritte zurück der letzte aufgetreten ist.

https://oeis.org/A181391

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

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

Reihenfolge: 0,0,1,0,2,0,2,2,1,6,0,5,0,2, ...

Tests:

Eingabe | Ausgabe

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

BEARBEITEN

1 indiziert ist bevorzugt, 0 indiziert ist akzeptabel; Das könnte einige der bereits eingereichten Lösungen ändern.

Nur das neunte Semester bitte.

Gleich (mit Ausnahme des bereits veröffentlichten Teils), scheint es, dass Codegolfer und Numberphile-Beobachter eine anständige Überlappung haben.

code-golf sequence 182764125216
quelle
9
Hab mir das Numpherphile-Video bei der Arbeit angesehen und wollte es posten, als ich nach Hause kam. Verfluche dich dafür, dass du zuerst da bist. : P
Draco18s
17
Muss es 1-indiziert sein, oder dürfen wir 0-indizieren?
Robin Ryder
6
Dürfen wir stattdessen die unendliche Folge zurückgeben oder ausgeben?
Jo King
2
... oder die ersten nSemester?
Shaggy
@ Draco18s Das gleiche gilt, ich bin hierher gekommen, um es zu posten, nachdem ich das Numberphile-Video gesehen habe, als ich es gesehen habe.
Geza Kerecsenyi

Antworten:

25

JavaScript (ES6),  46 41  37 Byte

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

Probieren Sie es online!

Wie?

Wir müssen nicht die gesamte Sequenz speichern. Wir müssen nur die letzte Position jeder Ganzzahl verfolgen, die in der Sequenz erscheint. Wir verwenden dazu das der rekursiven Funktion zugrunde liegende Objekt .g

Für einen gegebenen Term brauchen wir auf seine tatsächliche absolute Position in der Sequenz zu setzen, weil uns nur die Entfernung mit der aktuellen Position interessiert. Deshalb können wir nur den aktuellen Wert des Eingangs speichern , der als Dekrementierungszähler im Code verwendet wird.pg[p]n

Daher ist der Abstand durch . Günstigerweise ergibt dies NaN, wenn dies das erste Auftreten von , das leicht in die erwartete .g[p]−np 0p0

Kommentiert

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
Arnauld
quelle
18

Python 3 , 69 63 62 Bytes

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

Probieren Sie es online!

Hinweis: Wie Erik der Outgolfer erwähnte, funktioniert dieser Code auch in Python 2 einwandfrei.

0-indiziert (obwohl Sie es, nur um absolut pervers zu sein, -1-indizieren können, indem Sie if nzu if~n: P wechseln )

Nutzt Pythons großartigen "Sternoperator" zum rekursiven Aufbau der Serie, bis nNull erreicht ist.

Die Funktion baut die Serie in umgekehrter Reihenfolge auf, um zu vermeiden, dass sie für die Suche umgekehrt werden muss. Außerdem werden die Negationen aller Elemente gespeichert, da das Zurückkonvertieren am Ende kostenlos war (andernfalls -hätte es ein Leerzeichen sein müssen), und es wird ein Byte auf dem Weg gespart, indem ~s.index(l)statt verwendet wird -~s.index(l).

Könnten 51 Bytes sein, wenn Python-Tupel dieselben findFunktionen haben wie Strings (-1 zurückgeben, wenn sie nicht gefunden werden, anstatt einen Fehler auszulösen), aber kein solches Glück ...

ArBo
quelle
3
Tatsächlich ist der von Ihnen verwendete "Stern-Operator" nicht der Entpack-Operator von Python 3, sondern der Vararg-Operator, der auch in Python 2 vorhanden ist.
Erik the Outgolfer,
3
Der erste ist, aber entpackt der zweite nicht sfür den rekursiven Aufruf?
ArBo
1
Ich habe es in Python 2 getestet und es funktioniert.
Erik der Outgolfer
@EriktheOutgolfer hmm, aber ist der zweite Einsatz nicht das Auspacken? Die Funktion muss varargs nicht unterstützen, um eine solche Syntax zu verwenden.
ArBo
@ Arbo: Es ist nicht anders als def func(f, *args): f(*args); das entpacken innerhalb von funktionsaufrufen ist py2 gültig. Was ist py3-nur innerhalb Liste / dict Comprehensions (dh Auspacken [1, 2, *s]) oder Auspacken Variablen: a, *b = [1,2,3,4].
Ehsan Kia,
9

R , 62 Bytes

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

Probieren Sie es online!

Erstellt die Liste in umgekehrter Reihenfolge. matchGibt den ersten Index von F[1](den vorherigen Wert) in F[-1](den Rest der Liste) zurück und zurück, 0wenn keine Übereinstimmung gefunden wird.

Fwird beim ersten Durchlauf der Schleife initialisiert FALSEund gezwungen .0while

Giuseppe
quelle
2
Ich bin ein bisschen verblüfft, wie gut matchdieses Problem ist, wenn Sie es so konstruieren. Wirklich sauber.
CriminallyVulgar
Tut das Pluszeichen in der zweiten Zeile hier etwas? Ich nahm an, dass es einen Randfall repariert, aber ich kann keinen dafür finden.
CriminallyVulgar
1
@CriminallyVulgar sollte es erzwingen F, 0wann n==1es sonst zurückkehren würde FALSE.
Giuseppe
Ahh, ich verstehe. Sinnvoll, ich habe viele Bereiche ausprobiert, aber nicht den einzelnen Wert.
CriminallyVulgar
9

Perl 6 , 47 42 Bytes

-5 bytes dank nwellnhof

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

Probieren Sie es online!

Anonymer Codeblock, der das 0-indizierte Element in der Sequenz ausgibt.

Erläuterung:

{                                            } # 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
Scherzen
quelle
8

Borowski-Shell, 102 Bytes

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

versuche es online

jnfnt
quelle
3
Willkommen bei PPCG!
Arnauld
6

J , 29 23 Bytes

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

Probieren Sie es online!

Die eigentliche Arbeit wird im Iterationsverb des ^:Potenzverbs geleistet , das so oft wie das Argument iteriert und [die Iteration mit dem konstanten Wert 0 beginnt &0...

  • (#|1+}.i.{.)Dies wird wiederholt. Brechen sie ab...
  • }.i.{.Finden Sie den Index des i.Kopfes der Liste {.innerhalb des Endes der Liste }.. Dies gibt einen 0-basierten Index zurück. Wenn das aktuelle Element also 1 vorher gefunden wurde, wird 0 zurückgegeben. Wenn es nicht gefunden wird, wird die Länge der Liste zurückgegeben, dh die Länge des Endes.
  • 1+Fügen Sie dem Wert eine hinzu, um die 0-basierte Indizierung zu korrigieren, da das "Wie weit zurück" des Ven Eck 1-basiert ist. Beachten Sie, dass der Wert nun der Länge der vollständigen Liste entspricht, wenn er nicht gefunden wurde.
  • #|Gibt den Rest des im vorherigen Schritt berechneten Werts zurück, dividiert durch die Länge der vollständigen Liste. Beachten Sie, dass dies "nicht gefunden" zu 0 macht, aber alle anderen Werte unverändert lässt.
  • ,~Fügen Sie den neuen Wert an den Anfang der Liste an. Wir verwenden die Vorderseite eher als letztes, nur aus Bequemlichkeitsgründen.
  • 1{ Geben Sie das zweite Element in der Liste zurück, da wir es zu oft berechnet haben, da es auf diese Weise kürzer ist.
Jona
quelle
6

Python , 51 Bytes

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

Probieren Sie es online!

Ausgänge Falsefür 0. Implementiert die Spezifikation ziemlich wörtlich und sucht nach der niedrigsten positiven Ganzzahl, iso dass f(n-1)==f(n-i-1). Wenn eine solche Suche zu führt, i>=nist das vorherige Element noch nicht erschienen und wir produzieren 0.

Anstatt sinnvolle Maßnahmen wie das Speichern früherer Werte in einer Liste zu ergreifen, berechnet die Funktion diese nur rekursiv von Grund auf neu, wenn sie benötigt werden und manchmal, wenn sie nicht benötigt werden. Dadurch läuft die Funktion bei Eingängen über 10 sehr langsam.

xnor
quelle
5

APL (Dyalog Unicode) , 19 17 Byte SBCS

Vielen Dank an ngn, Adám, Richard Park und H.PWiz für ihre Hilfe beim Schreiben und Golfen dieser Antwort in The APL Orchard , einem großartigen Ort, um APL zu lernen und APL-Hilfe zu erhalten.

Edit: -2 Bytes von Adám.

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

Probieren Sie es online!

Erläuterung

⊃(⊢,⍨≢|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.
Sherlock9
quelle
4

05AB1E , 8 Bytes

F¯Rćk>Dˆ

n

Erläuterung:

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)
Kevin Cruijssen
quelle
1
Das ist ein seltsamer Weg, um die Obszönität zu zensieren!
negative sieben
1
@negativeseven Lol, ich habe ein paar Minuten gebraucht, um zu wissen, was du meinst, aber ich nehme an, du meinst das F¯Rćk? ;)
Kevin Cruijssen
4

Java, 96 80 76 Bytes

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

Nicht verschleiert:

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;
};
Achaaab
quelle
2
Sie sollten in der Lage sein, einige Bytes zu entfernen, indem Sie die while-Schleife in eine for-Schleife ändern.
MegaTom
1
Hallo, du könntest mehr Golf spielen, indem du die Deklaration von int[]in die intDeklaration einfügst und <1stattdessen auch verwendest ==0. Beispiel:int f(int n){int l[]=new int[n],i=0,j,v=0;while(++i<n){j=l[v];l[v]=i;v=j<1?0:i-j;}return v;}
Olivier Grégoire
2
Und jetzt ein Lambda sowie der von @MegaTom erwähnte Golf für insgesamt 80 Bytes:n->{int l[]=new int[n],i=0,j,v=0;for(;++i<n;l[v]=i,v=j<1?0:i-j)j=l[v];return v;}
Olivier Grégoire,
1
Schließlich können Sie in Java nach Tipps zum Golfen suchen .
Olivier Grégoire
3

Holzkohle , 23 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

≔⁰θ

Setzen Sie den ersten Term auf 0.

Ｆ⊖Ｎ«

Loop- n-1Zeiten. (Wenn die 0-Indizierung akzeptabel ist, ⊖kann sie für eine 1-Byte-Speicherung entfernt werden.)

≔⊕⌕⮌υθη

Der nächste Begriff ist der inkrementierte Index des aktuellen Begriffs in der umgekehrten Liste der vorherigen Begriffe.

⊞υθ

Fügen Sie den aktuellen Begriff zur Liste der vorherigen Begriffe hinzu.

≔ηθ

Setzen Sie den aktuellen Begriff auf den nächsten Begriff.

»Ｉθ

Gibt den aktuellen Term am Ende der Schleife aus.

Neil
quelle
2

Gelee , 8 Bytes

ẎiḢ$;µ¡Ḣ

nnth

Probieren Sie es online!

Wie?

Ẏ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

Beachten Sie, dass Ḣwir ohne das Finale tatsächlich gesammelt haben[a(n), a(n-1), ..., a(2), a(1), n]

Jonathan Allan
quelle
2

C (gcc) 63 Bytes

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

Probieren Sie es online!

0-indiziert.

attinat
quelle
2

Haskell , 68 67 66 Bytes

Ganz unkomplizierte Implementierung (mit 0-basierter Indizierung).

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

Probieren Sie es online!

fehlerhaft
quelle
2

Haskell, 61 Bytes

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

0-basierte Indizierung.

Probieren Sie es online!

nimi
quelle
2

Python 3 , 128 114 111 102 99 Bytes

102 -> 99 Bytes, danke an 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]

Probieren Sie es online!

Ruohola
quelle
Sie können Ihre Bedingung negieren und -stattdessen verwenden !=, um ein Byte zu speichern.
Jonathan Frech
Da Ihr Golf anscheinend nebenwirkungsfrei ist, können Sie auch Listen anstelle von Tupeln verwenden.
Jonathan Frech
@ JonathanFrech Aber wenn ich eine Liste als Standardargument habe, funktioniert es nicht richtig für aufeinanderfolgende Aufrufe?
Ruohola
Warum sollte es nicht?
Jonathan Frech
1
Höchstwahrscheinlich, weil Ihr vorheriges Skript die Liste geändert hat, also nicht nebenwirkungsfrei war: Beispiel .
Jonathan Frech
1

Perl 5 ( -p), 42 Bytes

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

Probieren Sie es online!

Grimmig
quelle
1

Python 3 , 112 Bytes

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])

Probieren Sie es online!

-3 Bytes dank mypetlion

HyperNeutrino
quelle
Die zweite Zeile kann 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]3 Bytes speichern.
Mypetlion
@ mypetlion danke
HyperNeutrino
1

CJam (15 Bytes)

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

Online-Demo . Dies ist ein vollständiges Programm und 0-indiziert.

Präparation

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
Peter Taylor
quelle
0

Clojure, 69 Bytes

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

Leider scheint ein funktionalerer Ansatz länger zu dauern.

NikoNyrh
quelle
0

DC, 94 91 90 Bytes

Die Eingabe erfolgt während des Programms. Speichern Sie dies in eine Datei und führen Sie dann "dc" aus. Auf jeden Fall nicht die kürzeste, aber ich habe Spaß mit solchen Herausforderungen in DC. Die Eingabe erfolgt wie bevorzugt über einen 1-basierten Index.

[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
```
FlexEast
quelle
0

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

197 -> 189 Bytes dank 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];}

Probieren Sie es online!

Ruohola
quelle
0

Pyth , 18 Bytes

VQ=Y+?YhxtYhY0Y;hY

Probieren Sie es online!

Baut die Sequenz in umgekehrter Reihenfolge auf und druckt das erste Element (letzter Term der Sequenz).

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]
ar4093
quelle