La secuencia es demasiado meta

Leaky Nun 09/11/2017. 6 answers, 2.053 views
code-golf sequence

Comenzamos con una secuencia en blanco de 1 índice:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,... 

En el enésimo paso, completamos cada a (n) espacios en blanco con los números enteros mayores que 1 comenzando en el primer espacio en blanco restante, donde a (n) es la enésima entrada de la secuencia.

Después del primer paso:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,... 

Tenga en cuenta que a (1) tiene que ser 2 porque el primer entero mayor que 1 es 2.

En el segundo paso, completamos cada a (2) espacios en blanco. Será evidente que a (2) debe ser 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,... 

En el tercer paso, completamos cada a (3) espacios en blanco. De la secuencia, a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,... 

En el cuarto paso, completamos cada a (4) espacios en blanco. De la secuencia, a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,... 

Finalmente:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,... 

Tarea

Dado n, devuelve el n- ésimo elemento de la secuencia.

Los primeros 10 000 000 términos de la secuencia se pueden encontrar aquí .

Esto es . La respuesta más corta en bytes gana. Lagunas estándar se aplican.

5 Comments
Leaky Nun 06/20/2017
@LuisMendo Gracias, lo he agregado.
Dead Possum 06/20/2017
Simplemente curioso, ¿qué error hizo mr.One para ser excluido de la secuencia?
Leaky Nun 06/20/2017
@DeadPossum, si completas cada espacio en blanco, entonces terminaste en un solo paso.
2 Leaky Nun 06/20/2017
@DeadPossum Si a (n) es 1, entonces el n-ésimo paso completará cada espacio en blanco restante, terminando la generación.
1 Leaky Nun 06/20/2017
@QBrute Proporcioné una lista de los primeros 10,000,000 vinculados en la pregunta; solo complátelos.

6 Answers


Anders Kaseorg 06/20/2017.

Haskell , 80 67 bytes

 g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m 

¡Pruébalo en línea!

Haskell es el lenguaje perfecto para definir una lista infinita en términos de sí mismo.

5 comments
1 Julian Wolf 06/20/2017
Dado que el enlace TIO funciona como se esperaba, supongo que mi pregunta debería ser: ¿podría agregar una explicación de cómo funciona esto?
2 Anders Kaseorg 06/20/2017
@JulianWolf Parece que no estás familiarizado con los patrones de protección. pattern1 | let pattern2 = expr2 = expr1 pattern1 | let pattern2 = expr2 = expr1 significa lo mismo que pattern1 = let pattern2 = expr2 in expr1 (por la misma razón que [expr1 | let pattern2 = expr2] significa lo mismo que [let pattern2 = expr2 in expr1] ).
1 Ørjan Johansen 06/20/2017
¡Tengo que recordar let guardias de patrón (especialmente que pueden hacer funciones)! Además, m=2:2:2`drop`g m es un byte más corto.
1 Ørjan Johansen 06/20/2017
(!!)$0:m es dos bytes más corto.
1 Ørjan Johansen 06/20/2017
En realidad, puedes soltar el 2:2: cosas completamente con un poco más de holgazanería: g ~(a:b)|... m=g m .

Doorknob 06/20/2017.

C, 123 bytes

 f(n)NO 

¡Pruébalo en línea!

Tutorial

 f(n)NO 

por cortocircuito, y luego por las leyes de De Morgan y el hecho de que 0 es falso en C:

 if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
} 

Esto esencialmente dice: "si este espacio está vacío, incremente k . Y si k anteriormente era un múltiplo del tamaño del paso, ejecute la siguiente declaración". Por lo tanto, ejecutamos la declaración en cada elemento de step size , que es exactamente cómo se describe la secuencia. La declaración en sí es simple; todo lo que hace es generar 2 , 3 , 4 , ....

 n=p[n-1];} 

Utilizando el truco-return-without-a-return que funciona con gcc , "devolvemos" el último elemento de los primeros n términos en la secuencia, que es el n ésimo término.


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1 

Pruébalo en línea

Cómo funciona

En lugar de jugar con listas, esto utiliza una fórmula recursiva simple.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input()))) 

xnor 06/20/2017.

Haskell , 67 bytes

 0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j 

¡Pruébalo en línea!

Una solución aritmética recursiva que resultó básicamente el mismo método que la respuesta Pyth de Anders Kaseorg .

Este código está cubierto de verrugas, partes feas que parecen que podrían jugarse golf, pero no vi cómo.

La función i%j realmente quiere usar un guardia para verificar si mod i(f j)>0 y evaluar una de las dos expresiones correspondientes. Pero, ambas expresiones usan div i(f j) . Encuadernar eso en un guardia no hará que se aplique a ambos lados. Hasta donde yo sé, no se puede hacer que un guardia "distribuya" sobre otros guardias. let y where son demasiado largos. Entonces, el código usa el last para elegir una de las dos expresiones mientras el guardia ata la variable. Ugh.

Idealmente, divMod porque se divMod tanto div como mod , pero (d,m)<-divMod ... es una expresión larga. En lugar de eso, comprobamos que el mod es distinto de cero al ver si el valor div multiplicado por el divisor es inferior al valor original.

El caso 0%j=2 no sería necesario si Haskell cortocircuitó div 0 , que no lo hace. El .pred convierte la entrada indexada a cero, o de lo contrario habría -1 correcciones en todas partes.

4 comments
Ørjan Johansen 06/21/2017
Si activa % 1-indexado, entonces necesita una corrección de cinco bytes, que solo ata. However , puede alinear f en % sin costo, y luego f convierte en anónimo, por lo que ahorra dos bytes en total.
xnor 06/21/2017
@ ØrjanJohansen ¿Qué quieres decir con inline? No veo cómo cambiar las referencias a f sin perder bytes.
Ørjan Johansen 06/21/2017
divMod parece ser un byte más barato, porque permite la ramificación con !!(0^m) . Hasta ahora tengo: 1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);‌​(%1)
Ørjan Johansen 06/21/2017
Como puede ver, la línea de entrada presupone la 1-reindexación, que elimina el .pred .

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 91 bytes

Una función recursiva que se detiene tan pronto como el resultado esté disponible.

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

Versión alternativa, 90 bytes

Suggested by Shaggy for -1 byte

Este debe ser llamado con f(n)() . Aunque la publicación correspondiente en meta actualmente da una puntuación positiva, esta sintaxis es aparentemente controvertida.

 n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

Manifestación

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
} 

2 comments
Shaggy 06/20/2017
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k‌​?c:++v:(i=1,v=2),i=0‌​,k=a[p]||2)) debería funcionar para 92 bytes. Llámalo con f(n)() .
Arnauld 06/20/2017
@Shaggy Gracias! Agregado como una versión alternativa.

Xanderhall 06/20/2017.

Java 8, 124 bytes

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];} 

Expresión lambda

Crea una matriz de enteros y la rellena continuamente hasta que se llene el enésimo valor.

Predeclarar variables en la parte superior para reducir tantas declaraciones como sea posible, ya que cada int cuesta 4 bytes de espacio en lugar de agregar ,n que es 2.

En la j 'ésima iteración del cálculo, el número de' espacios en blanco 'que se debe omitir es igual a a[j] (o 2, si está en blanco). Resulta que si el primer espacio en blanco que tenemos que rellenar está en la posición k , k * a[j] nos da el 'paso' ( s ).

Related questions

Hot questions

Language

Popular Tags