Istilah ke-8 Urutan Van Eck

41

Keluarkan istilah N dari Urutan Van Eck.

Urutan Van Eck didefinisikan sebagai:

  • Mulai dengan 0.
  • Jika istilah terakhir adalah kejadian pertama dari istilah itu maka istilah berikutnya adalah 0.
  • Jika istilah terakhir telah terjadi sebelumnya istilah berikutnya adalah berapa banyak langkah mundur adalah kejadian terbaru.

https://oeis.org/A181391

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

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

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

Tes:

Masukan | Keluaran

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

EDIT

1 diindeks lebih disukai, 0 diindeks dapat diterima; yang mungkin mengubah beberapa solusi yang sudah dikirimkan.

Tolong, istilah Nth saja.

Sama (kecuali untuk melihat itu sudah diposting bagian), tampaknya pegolf kode dan pengamat numberphile memiliki tumpang tindih yang layak.

182764125216
sumber
9
Menonton video numpherphile di tempat kerja dan akan memposting ini ketika saya sampai di rumah. Terkutuklah kamu karena telah sampai di sana dulu. : P
Draco18s
17
Apakah harus diindeks 1, atau bolehkah kita menggunakan pengindeksan 0?
Robin Ryder
6
Bisakah kita mengembalikan atau menampilkan urutan yang tak terbatas sebagai gantinya?
Jo King
2
... atau npersyaratan pertama ?
Shaggy
@ Draco18s Sama, saya datang ke sini untuk mempostingnya setelah melihat video Numberphile, ketika saya melihat ini.
Geza Kerecsenyi

Jawaban:

25

JavaScript (ES6),  46 41  37 byte

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

Cobalah online!

Bagaimana?

Kami tidak perlu menyimpan urutan lengkap. Kita hanya perlu melacak posisi terakhir setiap bilangan bulat yang muncul dalam urutan. Kami menggunakan objek yang mendasari fungsi rekursif untuk tujuan itu.g

Untuk istilah diberikan , kita tidak perlu mengatur ke posisi absolut aktualnya dalam urutan karena kita hanya tertarik pada jarak dengan posisi saat ini. Itu sebabnya kita bisa menyimpan nilai input , yang digunakan sebagai penghitung penurunan kode.pg[p]n

Oleh karena itu, jarak diberikan oleh . Mudahnya, ini mengevaluasi ke NaN jika ini adalah kejadian pertama dari , yang dapat dengan mudah diubah menjadi diharapkan .g[p]np 0p0

Berkomentar

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
sumber
18

Python 3 , 69 63 62 byte

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

Cobalah online!

Catatan: seperti yang disebutkan Erik the Outgolfer, kode ini juga berfungsi dengan baik di Python 2.

Diindeks 0 (walaupun, hanya untuk benar-benar menyimpang, Anda dapat membuatnya -1-diindeks dengan mengubah if nke if~n: P)

Manfaatkan "operator bintang" Python yang cantik membongkar, untuk secara rekursif membangun seri, hingga nmencapai nol.

Fungsi membangun seri dalam urutan terbalik, untuk menghindari keharusan membalikkannya untuk pencarian. Selain itu, ia sebenarnya menyimpan negasi dari semua elemen, karena mengonversinya kembali pada akhirnya adalah gratis (kalau -tidak harus ada spasi) dan menghemat kita satu byte di sepanjang jalan, dengan menggunakan ~s.index(l)alih-alih -~s.index(l).

Bisa jadi 51 byte jika Python tuple memiliki findfungsi string yang sama (mengembalikan -1 jika tidak ditemukan, alih-alih memunculkan kesalahan), tetapi tidak ada keberuntungan ...

ArBo
sumber
3
Sebenarnya, "operator bintang" yang Anda gunakan bukanlah operator pembongkaran Python 3, melainkan operator vararg yang juga ada di Python 2.
Erik the Outgolfer
3
Yang pertama adalah, tetapi bukankah yang kedua membongkar suntuk panggilan rekursif?
ArBo
1
Saya sudah mengujinya dengan Python 2 dan berhasil.
Erik the Outgolfer
@EriktheOutgolfer hmm, tapi bukankah penggunaan kedua membongkar? Fungsi tidak harus mendukung varargs untuk menggunakan sintaksis seperti itu.
ArBo
@ ArBo: Tidak berbeda dengan def func(f, *args): f(*args); membongkar panggilan fungsi di dalam adalah py2 yang valid. Apa py3-hanya membongkar dalam daftar / dict comprehensions (yaitu [1, 2, *s]) atau membongkar variabel: a, *b = [1,2,3,4].
Ehsan Kia
9

R , 62 byte

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

Cobalah online!

Buat daftar secara terbalik; matchmengembalikan indeks pertamaF[1] (nilai sebelumnya) di F[-1](sisa daftar), kembali 0jika tidak ditemukan kecocokan.

Fdiinisialisasi ke FALSEdan dipaksa untuk 0pada lintasan pertama whileloop.

Giuseppe
sumber
2
Saya agak kagum pada seberapa baik matchuntuk masalah ini ketika Anda membangunnya dengan cara ini. Sangat bersih.
CriminallyVulgar
Apakah nilai tambah pada baris kedua berfungsi di sini? Saya berasumsi itu memperbaiki kasus tepi, tetapi saya tidak dapat menemukannya untuk itu.
CriminallyVulgar
1
@CriminallyVulgar harus memaksa Funtuk 0saat n==1yang lain itu akan kembali FALSE.
Giuseppe
Ahh, begitu. Masuk akal, saya mencoba banyak rentang tetapi bukan nilai tunggal.
CriminallyVulgar
9

Perl 6 , 47 42 byte

-5 byte berkat nwellnhof

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

Cobalah online!

Codeblock anonim yang menampilkan elemen 0-diindeks dalam urutan.

Penjelasan:

{                                            } # 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
Jo King
sumber
8

Bourne shell, 102 byte

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

coba online

jnfnt
sumber
3
Selamat datang di PPCG!
Arnauld
6

J , 29 23 byte

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

Cobalah online!

Pekerjaan nyata dilakukan dalam kata kerja iterasi dari kata kerja kekuatan ^:, yang berulang sebanyak argumen [, mulai iterasi dengan nilai konstan 0 &0...

  • (#|1+}.i.{.)Ini adalah apa yang diulang. Memecahnya ...
  • }.i.{.Temukan indeks i.kepala daftar {.dalam daftar ekor }.. Ini akan mengembalikan indeks berbasis 0, jadi jika item saat ini ditemukan 1 sebelumnya akan kembali 0. Jika tidak ditemukan, itu akan mengembalikan panjang daftar, yaitu, panjang ekor.
  • 1+Tambahkan satu ke nilai untuk memperbaiki pengindeksan berbasis 0, karena Ven Eck "seberapa jauh" adalah berbasis 1. Perhatikan bahwa jika tidak ditemukan, nilainya akan menjadi panjang dari daftar lengkap.
  • #|Kembalikan sisa nilai yang dihitung pada langkah sebelumnya, ketika dibagi dengan panjang daftar lengkap. Perhatikan bahwa ini mengubah "tidak ditemukan" menjadi 0, tetapi membiarkan semua nilai lainnya tidak berubah.
  • ,~Tambahkan nilai baru ke depan daftar. Kami menggunakan front daripada bertahan hanya untuk kenyamanan.
  • 1{ kembalikan item ke-2 dalam daftar, karena kami menghitungnya terlalu banyak karena lebih pendek.
Jonah
sumber
6

Python , 51 byte

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

Cobalah online!

Output Falseuntuk 0. Implements spec cukup harfiah, mencari bilangan bulat positif terendah isehingga f(n-1)==f(n-i-1). Jika pencarian seperti itu mengarah ke i>=n, elemen sebelumnya tidak muncul sebelumnya dan kami menghasilkan 0.

Alih-alih melakukan sesuatu yang masuk akal seperti menyimpan nilai sebelumnya dalam daftar, fungsi tersebut hanya menghitung ulang secara rekursif dari awal kapan pun diperlukan, dan kadang-kadang saat tidak diperlukan. Ini membuat fungsi berjalan sangat lambat untuk input di atas 10 atau lebih.

Tidak
sumber
5

APL (Dyalog Unicode) , 19 17 byte SBCS

Terima kasih banyak kepada ngn, Adám, Richard Park dan H.PWiz atas bantuan mereka dalam menulis dan bermain golf jawaban ini di The APL Orchard , tempat yang bagus untuk belajar APL dan mendapatkan bantuan APL.

Edit: -2 byte dari Adám.

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

Cobalah online!

Penjelasan

⊃(⊢,⍨≢|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
sumber
4

05AB1E , 8 byte

F¯Rćk>Dˆ

n

Penjelasan:

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
sumber
1
Itu cara yang aneh untuk menyensor kata-kata kotor!
negatif tujuh
1
@negativeseven Lol, butuh saya beberapa menit untuk tahu apa yang Anda maksud, tapi saya kira Anda mengacu pada F¯Rćk? ;)
Kevin Cruijssen
4

Java, 96 80 76 byte

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

Tidak dikaburkan:

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
sumber
2
Anda harus dapat menghapus beberapa byte dengan mengubah loop sementara ke loop for.
MegaTom
1
Halo, Anda bisa bermain golf lebih banyak dengan menguraikan deklarasi int[]dalam intdeklarasi, dan juga menggunakan <1alih-alih ==0. Contoh: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
Dan sekarang lambda, serta golf yang disebutkan oleh @MegaTom dengan total 80 byte: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
Akhirnya, Anda bisa memeriksa tip untuk bermain golf di Jawa .
Olivier Grégoire
3

Arang , 23 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

≔⁰θ

Setel istilah pertama ke 0.

F⊖N«

n-1Waktu loop . (Jika pengindeksan 0 dapat diterima, dapat dihapus untuk penghematan 1 byte.)

≔⊕⌕⮌υθη

Istilah berikutnya adalah indeks yang meningkat dari istilah saat ini dalam daftar terbalik dari istilah sebelumnya.

⊞υθ

Tambahkan istilah saat ini ke daftar istilah sebelumnya.

≔ηθ

Tetapkan istilah saat ini ke istilah berikutnya.

»Iθ

Cetak istilah saat ini di akhir loop.

Neil
sumber
2

Jelly , 7 byte

Ḷ߀ṚiḢ$

Cobalah online!

Diindeks 0.

Erik the Outgolfer
sumber
2

Jelly , 8 byte

ẎiḢ$;µ¡Ḣ

nnth

Cobalah online!

Bagaimana?

Ẏ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

Perhatikan bahwa tanpa final, kami sudah benar-benar mengumpulkan[a(n), a(n-1), ..., a(2), a(1), n]

Jonathan Allan
sumber
2

C (gcc) , 63 byte

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

Cobalah online!

Diindeks 0.

attinat
sumber
2

Haskell , 68 67 66 byte

Implementasi yang cukup mudah (menggunakan pengindeksan berbasis 0).

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

Cobalah online!

cacat
sumber
2

Haskell, 61 byte

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

Pengindeksan berbasis 0.

Cobalah online!

nimi
sumber
2

Python 3 , 128 114 111 102 99 byte

102 -> 99 byte, terima kasih kepada 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]

Cobalah online!

ruohola
sumber
Anda dapat meniadakan kondisi Anda dan menggunakan -alih-alih !=menyimpan byte.
Jonathan Frech
Juga, karena golf Anda tampaknya lebih sedikit efek samping, Anda dapat menggunakan daftar alih-alih tupel.
Jonathan Frech
@JonathanFrech Tetapi jika saya memiliki daftar sebagai argumen default, itu tidak akan berfungsi dengan benar untuk panggilan berurutan?
ruohola
Kenapa tidak?
Jonathan Frech
1
Kemungkinan besar karena skrip Anda sebelumnya memodifikasi daftar, yaitu bukan efek samping: contoh .
Jonathan Frech
1

Perl 5 ( -p), 42 byte

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

Cobalah online!

Grimmy
sumber
1

Python 3 , 112 byte

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

Cobalah online!

-3 byte terima kasih kepada mypetlion

HyperNeutrino
sumber
Baris kedua dapat 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]menghemat 3 byte.
mypetlion
@mypetlion terima kasih
HyperNeutrino
1

Merah , 106 95 byte

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]

Cobalah online!

Galen Ivanov
sumber
1

CJam (15 byte)

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

Demo online . Ini adalah program lengkap dan 0-diindeks.

Pembedahan

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
sumber
0

Clojure, 69 byte

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

Sayangnya pendekatan yang lebih fungsional tampaknya lebih lama.

NikoNyrh
sumber
0

DC, 94 91 90 byte

Masukan diambil selama program. Simpan ini ke file dan kemudian lakukan "dc" untuk menjalankan. Jelas bukan yang terpendek, tapi saya bersenang-senang dengan tantangan seperti ini di dc. Input adalah indeks berbasis-1, sesuai keinginan.

[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
sumber
0

C ++ (dentang) , 241 235 234 219 197 189 byte

197 -> 189 byte, terima kasih kepada 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];}

Cobalah online!

ruohola
sumber
0

Pyth , 18 byte

VQ=Y+?YhxtYhY0Y;hY

Cobalah online!

Membangun urutan secara terbalik dan mencetak elemen pertama (istilah terakhir dari urutan).

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
sumber