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://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.
n
términos?Respuestas:
JavaScript (ES6),
46 4137 bytesPrué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.sol
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.pags sol[ p ] norte
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 .sol[ p ] - n p 0pags 0 0
Comentado
fuente
Python 3 ,
696362 bytesPrué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 n
aif~n
: P)Utiliza el magnífico "operador estrella" de Python para desempacar, para construir recursivamente la serie, hasta
n
llegar 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
find
funciones que las cadenas (devolviendo -1 si no se encuentra, en lugar de generar un error), pero no hay suerte ...fuente
s
para la llamada recursiva?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]
.R , 62 bytes
Pruébalo en línea!
Construye la lista a la inversa;
match
devuelve el primer índice deF[1]
(el valor anterior) enF[-1]
(el resto de la lista), devolviendo0
si no se encuentra ninguna coincidencia.F
se inicializaFALSE
y se coacciona0
en el primer paso delwhile
bucle.fuente
match
es este problema cuando lo construyes de esta manera. Muy limpioF
a0
cuándon==1
más volveríaFALSE
.Perl 6 ,
4742 bytes-5 bytes gracias a nwellnhof
Pruébalo en línea!
Codeblock anónimo que genera el elemento indexado 0 en la secuencia.
Explicación:
fuente
Bourne shell, 102 bytes
pruébalo en línea
fuente
Stax ,
109 bytesEjecutar y depurarlo
Si se permite la indexación basada en 0:
Stax , 8 bytes
Ejecutar y depurarlo
fuente
J ,
2923 bytesPrué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 dei.
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.fuente
Python , 51 bytes
Pruébalo en línea!
Salidas
False
para0
. Implementa la especificación literalmente, buscando el entero positivo más bajoi
tal quef(n-1)==f(n-i-1)
. Si tal búsqueda conducei>=n
, el elemento anterior no ha aparecido antes y producimos0
.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.
fuente
APL (Dyalog Unicode) ,
1917 bytes SBCSMuchas 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.
Pruébalo en línea!
Explicación
fuente
Wolfram Language (Mathematica) , 48 bytes
Pruébalo en línea!
Los valores distintos de cero se devuelven como listas singleton .
fuente
05AB1E , 8 bytes
Explicación:
fuente
F¯Rćk
. ;)Java,
968076 bytesNo ofuscado:
fuente
int[]
en laint
declaración, y también usar en<1
lugar 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;}
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;}
Carbón , 23 bytes
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.
n-1
Tiempos 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.
Imprime el término actual al final del ciclo.
fuente
Jalea , 7 bytes
Pruébalo en línea!
0 indexado.
fuente
Jalea , 8 bytes
Pruébalo en línea!
¿Cómo?
Tenga en cuenta que sin la final
Ḣ
realmente hemos recopilado[a(n), a(n-1), ..., a(2), a(1), n]
fuente
C (gcc) , 63 bytes
Pruébalo en línea!
0 indexado.
fuente
Haskell ,
68 6766 bytesImplementación bastante sencilla (usando indexación basada en 0).
Pruébalo en línea!
fuente
Haskell, 61 bytes
Indexación basada en 0.
Pruébalo en línea!
fuente
Japt
-h
, 11 bytesIntentalo
fuente
C # (compilador interactivo de Visual C #) , 77 bytes
Pruébalo en línea!
Más o menos un puerto de la respuesta de Java en este punto.
fuente
Python 3 ,
12811411110299 bytes102 -> 99 bytes, gracias a Jonathan Frech
Pruébalo en línea!
fuente
-
lugar de!=
guardar un byte.Perl 5 (
-p
), 42 bytesPruébalo en línea!
fuente
Python 3 , 112 bytes
Pruébalo en línea!
-3 bytes gracias a mypetlion
fuente
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.Rojo ,
10695 bytesPruébalo en línea!
fuente
CJam (15 bytes)
Demo en línea . Este es un programa completo e indexado a 0.
Disección
fuente
Clojure, 69 bytes
Lamentablemente, un enfoque más funcional parece ser más largo.
fuente
DC,
949190 bytesLa 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.
fuente
C ++ (clang) ,
241235234219197189 bytes197 -> 189 bytes, gracias a ceilingcat
Pruébalo en línea!
fuente
Pyth , 18 bytes
Pruébalo en línea!
Construye la secuencia en reversa e imprime el primer elemento (último término de la secuencia).
fuente