N-ty kadencja sekwencji Van Eck


41

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.


9
Obejrzałem film z ptasznikiem w pracy i zamierzałem go opublikować, kiedy wrócę do domu. Przeklnij, że dotarłeś tam pierwszy. : P
Draco18s,

17
Czy musi to być indeksowanie 1, czy może korzystamy z indeksowania 0?
Robin Ryder

6
Czy zamiast tego możemy zwrócić nieskończoną sekwencję?
Jo King

2
... czy pierwsze nwarunki?
Kudłaty

@ Draco18s To samo, przyszedłem tutaj, aby opublikować to po obejrzeniu filmu Numberphile, kiedy to zobaczyłem.
Geza Kerecsenyi

Odpowiedzi:


25

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.pg[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]np 0p0

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

18

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


3
W rzeczywistości używany przez ciebie „gwiezdny operator” nie jest operatorem rozpakowywania w Pythonie 3, ale operatorem vararg, który również istnieje w Pythonie 2.
Erik, Outgolfer

3
Pierwszy to, ale czy drugi nie rozpakowuje srekurencyjnego połączenia?
ArBo

1
Przetestowałem to w Pythonie 2 i działa.
Erik the Outgolfer

@EriktheOutgolfer hmm, ale czy to nie drugie rozpakowanie? Funkcja nie musi obsługiwać varargs, aby użyć takiej składni.
ArBo

@ArBo: Nie różni się niczym def func(f, *args): f(*args); rozpakowywanie wewnątrz wywołań funkcji jest prawidłowe py2. Co znajduje się w py3-tylko rozpakowuje wewnątrz Ułatwienia lista / dict (tj [1, 2, *s]) lub rozpakowywanie zmiennych a, *b = [1,2,3,4].
Ehsan Kia

9

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.


2
Jestem trochę pod wrażeniem tego, jak dobry matchjest ten problem, kiedy go skonstruujesz w ten sposób. Naprawdę czyste.
CriminallyVulgar

Czy plus na drugiej linii coś tu robi? Zakładałem, że naprawiono skrzynkę brzegową, ale nie mogę jej znaleźć.
CriminallyVulgar

1
@CriminallyVulgar powinien przymusić Fdo tego, 0kiedy n==1wróci FALSE.
Giuseppe

Ahh rozumiem. Ma sens, próbowałem wielu zakresów, ale nie jednej wartości.
CriminallyVulgar

9

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

8

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


3
Witamy w PPCG!
Arnauld


6

J , 29 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.

6

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.


5

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.


4

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)

1
To dziwny sposób na cenzurowanie wulgaryzmów!
negatywne siedem

1
@negativeseven Lol, zajęło mi kilka minut, aby wiedzieć, co masz na myśli, ale myślę, że masz na myśli F¯Rćk? ;)
Kevin Cruijssen

4

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

2
Powinieneś być w stanie usunąć kilka bajtów, zmieniając pętlę while na pętlę for.
MegaTom

1
Witaj, możesz golfa więcej, wpisując deklarację int[]w intdeklaracji, a także użyć <1zamiast ==0. Przykład: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
A teraz lambda, a także golf wspomniany przez @MegaTom w sumie 80 bajtów: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,


3

Węgiel , 23 bajty

≔⁰θF⊖N«≔⊕⌕⮌υθη⊞υθ≔ηθ»Iθ

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

≔⁰θ

Ustaw pierwszy termin na 0.

F⊖N«

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.

»Iθ

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



2

Galaretka , 8 bajtów

ẎiḢ$;µ¡Ḣ

nnth

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]



2

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!





2

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!


Możesz zanegować swój stan i użyć -zamiast !=zapisać bajt.
Jonathan Frech

Ponadto, ponieważ Twój golf wydaje się być bez efektów ubocznych, możesz używać list zamiast krotek.
Jonathan Frech

@JathanathanFrech Ale jeśli mam listę jako domyślny argument, to nie będzie działać poprawnie dla kolejnych wywołań?
ruohola

Dlaczego nie?
Jonathan Frech

1
Najprawdopodobniej, ponieważ poprzedni skrypt zmodyfikował listę, tzn. Nie był bez skutków ubocznych: przykład .
Jonathan Frech


1

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


Druga linia może stać się 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]na zapisanie 3 bajtów.
mypetlion

@mypetlion dzięki
HyperNeutrino


1

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

0

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.


0

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
```

0

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!


0

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]
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.