Podaj N-ty ciąg sekwencji Van Eck.

Sekwencja Van Ecka jest zdefiniowana jako:

• Zaczyna się od 0.
• Jeśli ostatni termin jest pierwszym wystąpieniem tego terminu, następnym terminem jest 0.
• Jeśli poprzedni termin miał miejsce wcześniej, następnym terminem jest ile kroków wstecz było ostatnie wystąpienie.

https://oeis.org/A181391

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

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

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

Testy:

Wejście | Wydajność

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

EDYTOWAĆ

1 indeksowany jest preferowany, 0 indeksowany jest dopuszczalny; co może zmienić niektóre z już przesłanych rozwiązań.

Poproszę tylko N-ty termin.

To samo (poza tym, że widzę, że jest już opublikowana część), wydaje się, że golfiści kodu i obserwatorzy numerów mają przyzwoite nakładanie.

JavaScript (ES6),  46 41  37 bajtów

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

Wypróbuj online!

W jaki sposób?

Nie musimy przechowywać pełnej sekwencji. Musimy tylko śledzić ostatnią pozycję każdej liczby całkowitej, która pojawia się w sekwencji. W tym celu używamy podstawowego obiektu funkcji rekurencyjnej .$g$

Dla danego terminu nie musimy ustawiać na jego rzeczywistą pozycję bezwzględną w sekwencji, ponieważ interesuje nas tylko odległość z bieżącą pozycją. Dlatego możemy po prostu zapisać bieżącą wartość wejścia , która jest używana jako licznik malejący w kodzie.$p$$g[p]$$n$

Dlatego odległość podaje się za pomocą . Dogodnie, to ocenia na NaN, jeśli jest to pierwsze wystąpienie , które można łatwo przekształcić w oczekiwane .$g[p]-n$p 0$p$$0$

Skomentował

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 bajtów

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

Wypróbuj online!

_{Uwaga: jak wspomniał Erik the Outgolfer, ten kod działa również dobrze w Pythonie 2.}

0-indeksowane (chociaż, aby być całkowicie przewrotnym, możesz zrobić to -1-indeksując, zmieniając if nna if~n: P)

Wykorzystuje wspaniały rozpakowujący „gwiazdowy operator” Pythona, aby rekurencyjnie budować serię, aż nosiągnie zero.

Funkcja buduje serię w odwrotnej kolejności, aby uniknąć konieczności jej odwrócenia podczas wyszukiwania. Dodatkowo faktycznie przechowuje negacje wszystkich elementów, ponieważ konwersja ich z powrotem na końcu była wolna (inaczej -musiałoby to być spacja) i oszczędza nam bajt po drodze, używając ~s.index(l)zamiast -~s.index(l).

Może być 51 bajtów, jeśli krotki Pythona mają te same findciągi funkcji (zwracają -1, jeśli nie zostaną znalezione, zamiast zgłaszania błędu), ale nie mają szczęścia ...

R , 62 bajty

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

Wypróbuj online!

Buduje listę w odwrotnej kolejności; matchzwraca pierwszy indeks F[1](poprzedniej wartości) z F[-1](pozostała część listy), zwracając 0jeśli nie znaleziono dopasowania.

Fjest inicjowany FALSEi wymuszany 0przy pierwszym przejściu whilepętli.

Perl 6 , 47 42 bajtów

-5 bajtów dzięki nwellnhof

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

Wypróbuj online!

Anonimowy blok kodu, który wyprowadza element o indeksie 0 w sekwencji.

Wyjaśnienie:

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

Powłoka Bourne'a, 102 bajty

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

spróbuj online

Stax , 10 9 bajtów

é"▬π²"ô↕j

Uruchom i debuguj

Jeśli indeksowanie na podstawie 0 jest dozwolone:

Stax , 8 bajtów

à┐æ8Å/[┤

Uruchom i debuguj

J , ²⁹ 23 bajtów

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

Wypróbuj online!

Prawdziwa praca jest wykonywana w czasowniku iteracyjnym czasownika potęgowego ^:, który iteruje tyle razy, ile argument [, rozpoczynając iterację od stałej wartości 0 &0...

• (#|1+}.i.{.)Właśnie to iteruje. Rozbijam to ...
• }.i.{.Znajdź indeks i.nagłówka listy {.na końcu listy }.. Zwróci to indeks oparty na 0, więc jeśli bieżący element zostanie znaleziony 1 poprzedni, zwróci 0. Jeśli nie zostanie znaleziony, zwróci długość listy, tj. Długość ogona.
• 1+Dodaj jeden do wartości, aby poprawić indeksowanie na podstawie 0, ponieważ „jak daleko wstecz” Ven Ecka opiera się na 1. Zauważ, że jeśli nie zostanie znaleziony, wartość będzie teraz długością pełnej listy.
• #|Zwraca pozostałą część wartości obliczonej w poprzednim kroku, podzieloną przez długość pełnej listy. Zauważ, że zmienia to „nie znaleziono” w 0, ale pozostawia wszystkie pozostałe wartości bez zmian.
• ,~Dołącz nową wartość na początku listy. Korzystamy z przodu, a nie tylko dla wygody.
• 1{ zwróć 2. pozycję na liście, ponieważ obliczyliśmy ją zbyt wiele razy, ponieważ w ten sposób jest krótsza.

Python , 51 bajtów

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

Wypróbuj online!

Wyjścia Falsedla 0. Implementuje specyfikację dosłownie, szukając najniższej dodatniej liczby całkowitej, itakiej jak f(n-1)==f(n-i-1). Jeśli takie wyszukiwanie prowadzi do i>=n, poprzedni element nie pojawił się wcześniej i produkujemy 0.

Zamiast robić coś rozsądnego, jak przechowywanie wcześniejszych wartości na liście, funkcja po prostu przelicza je rekurencyjnie od zera, gdy są potrzebne, a czasem, gdy nie są potrzebne. To powoduje, że funkcja działa bardzo wolno dla wejść powyżej 10 lub więcej.

APL (Dyalog Unicode) , 19 17 bajtów ^SBCS

Ogromne podziękowania dla ngn, Adám, Richard Park i H.PWiz za pomoc w pisaniu i grze w golfa w The APL Orchard , doskonałym miejscu do nauki APL i uzyskania pomocy APL.

Edycja: -2 bajty z Adám.

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

Wypróbuj online!

Wyjaśnienie

⊃(⊢,⍨≢|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 bajtów

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

Wypróbuj online!

Niezerowe wartości są zwracane jako listy singletonów .

05AB1E , 8 bajtów

F¯Rćk>Dˆ

$n$

Wyjaśnienie:

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 bajtów

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

Nie zaciemnione:

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

Węgiel , 23 bajty

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔⁰θ

Ustaw pierwszy termin na 0.

Ｆ⊖Ｎ«

n-1Czasy pętli (Jeśli indeksowanie 0 jest dopuszczalne, ⊖można je usunąć, aby zaoszczędzić 1 bajt.)

≔⊕⌕⮌υθη

Następny termin to zwiększony indeks bieżącego terminu na odwróconej liście poprzednich terminów.

⊞υθ

Dodaj bieżący termin do listy poprzednich terminów.

≔ηθ

Ustaw bieżący termin na następny.

»Ｉθ

Wydrukuj bieżący termin na końcu pętli.

Galaretka , 7 bajtów

Ḷ߀ṚiḢ$

Wypróbuj online!

0-indeksowane.

Galaretka , 8 bajtów

ẎiḢ$;µ¡Ḣ

$n$$n^{th}$

Wypróbuj online!

W jaki sposób?

Ẏ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

Pamiętaj, że bez finału Ḣ, który rzeczywiście zebraliśmy[a(n), a(n-1), ..., a(2), a(1), n]

C (gcc) , 63 bajty

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

Wypróbuj online!

0-indeksowane.

Haskell , 68 67 66 bajtów

Dość prosta implementacja (z wykorzystaniem indeksowania opartego na 0).

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

Wypróbuj online!

Haskell, 61 bajtów

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

Indeksowanie na podstawie 0.

Wypróbuj online!

Japt -h , 11 bajtów

@ÒZÔÅbX}hTo

Spróbuj

C # (interaktywny kompilator Visual C #) , 77 bajtów

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

Wypróbuj online!

Prawie port odpowiedzi Java w tym momencie.

Python 3 , 128 114 111 102 99 bajtów

102 -> 99 bajtów, dzięki 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]

Wypróbuj online!

Perl 5 ( -p), 42 bajty

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

Wypróbuj online!

Python 3 , 112 bajtów

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

Wypróbuj online!

-3 bajty dzięki mypetlion

Czerwony , 106 95 bajtów

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]

Wypróbuj online!

CJam (15 bajtów)

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

Demo online . Jest to pełny program z indeksowaniem 0.

Sekcja

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 bajtów

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

Niestety bardziej funkcjonalne podejście wydaje się być dłuższe.

DC, 94 91 90 bajtów

Dane wejściowe są pobierane podczas programu. Zapisz to w pliku, a następnie wykonaj polecenie „dc”, aby uruchomić. Zdecydowanie nie najkrótszy, ale dobrze się bawię z takimi wyzwaniami w DC. Dane wejściowe są indeksem 1, zgodnie z preferencjami.

[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 bajtów

197 -> 189 bajtów, dzięki pułapkowi cat

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

Wypróbuj online!

Pyth , 18 bajtów

VQ=Y+?YhxtYhY0Y;hY

Wypróbuj online!

Tworzy sekwencję w odwrotnej kolejności i drukuje pierwszy element (ostatni termin sekwencji).

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]