Enésimo término de la secuencia de Van Eck

41

Salida del enésimo término de la secuencia de Van Eck.

La secuencia de Van Eck se define como:

  • Comienza con 0.
  • Si el último término es la primera aparición de ese término, el siguiente término es 0.
  • Si el último término se produjo anteriormente, el siguiente término es cuántos pasos atrás fue la ocurrencia más reciente.

https://oeis.org/A181391

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

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

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

Pruebas:

Entrada | Salida

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

EDITAR

Se prefiere 1 indexado, se acepta 0 indexado; eso podría cambiar algunas de las soluciones ya enviadas.

Solo el enésimo término por favor.

Lo mismo (excepto por ver que ya publicó una parte), parece que los golfistas de código y los observadores numéricos tienen una superposición decente.

182764125216
fuente
99
Vi el video de numpherphile en el trabajo e iba a publicar esto cuando llegara a casa. Te maldigo por llegar primero. : P
Draco18s
17
¿Tiene que estar indexado en 1 o podemos usar indexación en 0?
Robin Ryder
66
¿Podemos devolver o generar la secuencia infinita en su lugar?
Jo King
2
... o los primeros ntérminos?
Shaggy
@ Draco18s Igual, vine aquí para publicarlo después de ver el video de Numberphile, cuando vi esto.
Geza Kerecsenyi

Respuestas:

25

JavaScript (ES6),  46 41  37 bytes

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

Pruébalo en línea!

¿Cómo?

No necesitamos almacenar la secuencia completa. Solo necesitamos hacer un seguimiento de la última posición de cada entero que aparece en la secuencia. Usamos el objeto subyacente de la función recursiva para ese propósito.g

Para un término dado , tampoco necesitamos establecer en su posición absoluta real en la secuencia porque solo estamos interesados ​​en la distancia con la posición actual. Es por eso que solo podemos almacenar el valor actual de la entrada , que se utiliza como un contador decreciente en el código.pg[p]n

Por lo tanto, la distancia viene dada por . Convenientemente, esto se evalúa como NaN si esta es la primera aparición de , que puede convertirse fácilmente en el esperado .g[p]np 0p0

Comentado

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

Pruébalo en línea!

Nota: como mencionó Erik the Outgolfer, este código también funciona bien en Python 2.

0 indexado (aunque, para ser completamente perverso, puede hacerlo -1 indexado cambiando if na if~n: P)

Utiliza el magnífico "operador estrella" de Python para desempacar, para construir recursivamente la serie, hasta nllegar a cero.

La función construye la serie en el orden inverso, para evitar tener que invertirla para la búsqueda. Además, en realidad almacena las negaciones de todos los elementos, porque convertirlos de nuevo al final fue gratuito (de lo contrario, -debería haber sido un espacio) y nos ahorra un byte en el camino, al usarlo en ~s.index(l)lugar de -~s.index(l).

Podría ser de 51 bytes si las tuplas de Python tuvieran las mismas findfunciones que las cadenas (devolviendo -1 si no se encuentra, en lugar de generar un error), pero no hay suerte ...

ArBo
fuente
3
En realidad, el "operador estrella" que está utilizando no es el operador de desempaquetado de Python 3, sino el operador de vararg que también existe en Python 2.
Erik the Outgolfer
3
El primero es, pero ¿no es el segundo desempaquetado spara la llamada recursiva?
ArBo
1
Lo probé en Python 2 y funciona.
Erik the Outgolfer
@EriktheOutgolfer hmm, pero ¿no es el segundo uso desempacar? La función no tiene que admitir varargs para usar dicha sintaxis.
ArBo
@ArBo: No es diferente de def func(f, *args): f(*args); Desempaquetar dentro de las llamadas a funciones es válido py2. ¿Cuál es el AP3-solamente es descomprimir el interior de las listas por comprensión / dict (es decir, [1, 2, *s]las variables) o desembalaje: 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]}

Pruébalo en línea!

Construye la lista a la inversa; matchdevuelve el primer índice de F[1](el valor anterior) en F[-1](el resto de la lista), devolviendo 0si no se encuentra ninguna coincidencia.

Fse inicializa FALSEy se coacciona 0en el primer paso del whilebucle.

Giuseppe
fuente
2
Me asombra lo bueno que matches este problema cuando lo construyes de esta manera. Muy limpio
CriminallyVulgar
¿El plus en la segunda línea hace algo aquí? Asumí que solucionó un caso de borde, pero no puedo encontrar uno para él.
CriminallyVulgar
1
@CriminallyVulgar debería obligar Fa 0cuándo n==1más volvería FALSE.
Giuseppe
Ahh ya veo. Tiene sentido, estaba probando muchos rangos pero no el único valor.
CriminallyVulgar
9

Perl 6 , 47 42 bytes

-5 bytes gracias a nwellnhof

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

Pruébalo en línea!

Codeblock anónimo que genera el elemento indexado 0 en la secuencia.

Explicación:

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

Bourne 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

pruébalo en línea

jnfnt
fuente
3
Bienvenido a PPCG!
Arnauld
6

J , 29 23 bytes

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

Pruébalo en línea!

El trabajo real se realiza en el verbo de iteración del verbo de poder ^:, que itera tantas veces como el argumento [, comenzando la iteración con el valor constante 0 &0...

  • (#|1+}.i.{.)Esto es lo que itera. Desglosándolo ...
  • }.i.{.Encuentre el índice de i.la cabecera de la lista {.dentro de la cola de la lista }.. Esto devolverá un índice basado en 0, por lo que si el elemento actual se encuentra 1 anterior, devolverá 0. Si no se encuentra, devolverá la longitud de la lista, es decir, la longitud de la cola.
  • 1+Agregue uno al valor para corregir la indexación basada en 0, ya que el "qué tan atrás" de Ven Eck se basa en 1. Tenga en cuenta que si no se encontró, el valor ahora será la longitud de la lista completa.
  • #|Devuelve el resto del valor calculado en el paso anterior, cuando se divide por la longitud de la lista completa. Tenga en cuenta que esto convierte "no encontrado" en 0, pero deja todos los demás valores sin cambios.
  • ,~Agregue el nuevo valor al principio de la lista. Usamos el frente en lugar de durar simplemente por conveniencia.
  • 1{ devuelve el segundo elemento de la lista, ya que calculamos uno demasiadas veces porque es más corto de esa manera.
Jonás
fuente
6

Python , 51 bytes

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

Pruébalo en línea!

Salidas Falsepara 0. Implementa la especificación literalmente, buscando el entero positivo más bajo ital que f(n-1)==f(n-i-1). Si tal búsqueda conduce i>=n, el elemento anterior no ha aparecido antes y producimos 0.

En lugar de hacer algo razonable como almacenar valores anteriores en una lista, la función simplemente los recalcula recursivamente desde cero siempre que se necesitan, y a veces cuando no se necesitan. Esto hace que la función se ejecute muy lentamente para entradas superiores a 10 más o menos.

xnor
fuente
5

APL (Dyalog Unicode) , 19 17 bytes SBCS

Muchas gracias a ngn, Adám, Richard Park y H.PWiz por su ayuda para escribir y jugar golf en esta respuesta en The APL Orchard , un excelente lugar para aprender APL y obtener ayuda de APL.

Editar: -2 bytes de Adám.

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

Pruébalo en línea!

Explicación

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

05AB1E , 8 bytes

F¯Rćk>Dˆ

n

Explicación:

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
fuente
1
¡Esa es una forma extraña de censurar la blasfemia!
negativo siete
1
@negativeseven Lol, me tomó unos minutos saber a qué te referías, pero supongo que te estás refiriendo a la 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;}

No ofuscado:

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
fuente
2
Debería poder eliminar algunos bytes cambiando el ciclo while a un ciclo for.
MegaTom
1
Hola, podrías jugar más al golf al incluir la declaración de int[]en la intdeclaración, y también usar en <1lugar de ==0. Ejemplo: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
Y ahora una lambda, así como el golf mencionado por @MegaTom para un total de 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
Finalmente, puede consultar consejos para jugar al golf en Java .
Olivier Grégoire
3

Carbón , 23 bytes

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

Pruébalo en línea! El enlace es a la versión detallada del código. Explicación:

≔⁰θ

Establece el primer término en 0.

F⊖N«

n-1Tiempos de bucle . (Si la indexación 0 es aceptable, se puede eliminar para guardar 1 byte).

≔⊕⌕⮌υθη

El siguiente término es el índice incrementado del término actual en la lista inversa de términos anteriores.

⊞υθ

Agregue el término actual a la lista de términos anteriores.

≔ηθ

Establecer el término actual para el próximo término.

»Iθ

Imprime el término actual al final del ciclo.

Neil
fuente
2

Jalea , 8 bytes

ẎiḢ$;µ¡Ḣ

nnth

Pruébalo en línea!

¿Cómo?

Ẏ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

Tenga en cuenta que sin la final realmente hemos recopilado[a(n), a(n-1), ..., a(2), a(1), n]

Jonathan Allan
fuente
2

Haskell , 68 67 66 bytes

Implementación bastante sencilla (usando indexación basada en 0).

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

Pruébalo en línea!

falla
fuente
2

Haskell, 61 bytes

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

Indexación basada en 0.

Pruébalo en línea!

nimi
fuente
2

Python 3 , 128 114 111 102 99 bytes

102 -> 99 bytes, gracias a 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]

Pruébalo en línea!

ruohola
fuente
Puede negar su condición y usarla en -lugar de !=guardar un byte.
Jonathan Frech
Además, dado que su golf parece no tener efectos secundarios, puede usar listas en lugar de tuplas.
Jonathan Frech
@ JonathanFrech ¿Pero si tengo una lista como argumento predeterminado, no funcionará correctamente para llamadas consecutivas?
ruohola
¿Por qué no debería?
Jonathan Frech
1
Lo más probable es que su script anterior modificó la lista, es decir, no fue sin efectos secundarios: ejemplo .
Jonathan Frech
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])

Pruébalo en línea!

-3 bytes gracias a mypetlion

Hiperneutrino
fuente
La segunda línea puede convertirse 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]para guardar 3 bytes.
mypetlion
@mypetlion gracias
HyperNeutrino
1

Rojo , 106 95 bytes

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]

Pruébalo en línea!

Galen Ivanov
fuente
1

CJam (15 bytes)

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

Demo en línea . Este es un programa completo e indexado a 0.

Disección

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

Lamentablemente, un enfoque más funcional parece ser más largo.

NikoNyrh
fuente
0

DC, 94 91 90 bytes

La entrada se toma durante el programa. Guarde esto en un archivo y luego ejecute "dc". Definitivamente no es el más corto, pero me divierto con desafíos como estos en DC. La entrada es un índice basado en 1, como se prefiere.

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

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

197 -> 189 bytes, gracias a 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];}

Pruébalo en línea!

ruohola
fuente
0

Pyth , 18 bytes

VQ=Y+?YhxtYhY0Y;hY

Pruébalo en línea!

Construye la secuencia en reversa e imprime el primer elemento (último término de la secuencia).

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
fuente