En Gödel, Escher, Bach , Douglas Hofstadter introduce una secuencia de enteros que comúnmente se conoce como la secuencia figura-figura:
2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ...
Puede disfrutar elaborando la definición de la secuencia usted mismo como parte del desafío, pero si no puede o no quiere resolverlo, puede encontrarlo en OEIS como secuencia A030124 y una definición un poco más clara en Wikipedia .
Escriba un programa o función que, dado a n
través de STDIN, ARGV o argumento de función, imprima una lista de los primeros n
números de la secuencia en STDOUT en cualquier formato de lista razonable.
Este es el código de golf, la solución más corta en bytes gana.
code-golf
number
number-theory
sequence
Martin Ender
fuente
fuente
Haskell,
676160565553 caracteresvolviendo al primer algoritmo.
Esta solución calcula la secuencia del complemento sumando los elementos iniciales de la secuencia. luego calcula la secuencia como todos los números entre los números de secuencia del complemento.
(#)
es la función que calcula los números entre la secuencia del complemento.h
Es la secuencia misma.g
es la función que responde la pregunta.la función g se define para tomar la cantidad necesaria de elementos de h.
sutilezas:
h
es en realidad la secuencia de figuras figura excepto los primeros 2 elementos.no se calcula la secuencia del complemento, sino la secuencia del complemento con 1 agregado para cada elemento.
Estas dos sutilezas son la razón
scanl(+)8h
(que es el código para la secuencia del complemento (a excepción de los primeros 2 elementos) con 1 agregado) que tiene8
. es para el tercer elemento de la secuencia del complemento con 1 agregado.la razón por la computación no le faltan los dos primeros elementos se debe a que se añaden en
g
en2:4:h
.ejemplo:
fuente
Rubí,
5448Manifestación
Editar: Golfed esto un poco más una vez que me di cuenta de que no necesito mantener la secuencia completa del complemento en la memoria. Así es como funciona ahora: utilizamos
x
para realizar un seguimiento del número calculado más grande en la secuencia del complemento, yb
es un grupo de candidatos para la secuencia.n
veces, sacamos el elemento restante más pequeñob
y lo agregamosx
para calcular el siguiente número en la secuencia del complemento. Luego eliminamos ambos números del grupo de candidatos, por lo que siempre estamos generando el número más pequeño que no se agregó a ninguna de las secuencias.Trucos de golf Ruby: la sintaxis lambda Stabby es más corta que una definición de método. El requisito de que se dé salida a STDOUT en lugar de como valor de retorno me inspiró a usar el hecho de que el valor de retorno de
p(x)
esx
, lo que normalmente no recuerdo porque no es el caso en la versión Ruby utilizada en Anarchy Golf.fuente
2..2*n
. Tengo que usarn*n
porque lo estoy haciendo deb = [x]^b
manera efectiva, por lo que necesito que el elemento másb
grande sea mayor que el valor más grande dex
, perob -= [x]
solo requiere queb
contenga el mayor valor posible de la secuencia de salida.GolfScript (
2421 bytes)Demostración en línea
Esto comenzó de manera bastante diferente, pero terminó convergiendo en un puerto GolfScript de la solución Ruby de histocrat antes de que Dennis hiciera algunas sugerencias que lo llevan en una dirección ligeramente diferente. En particular, imprimir los números a medida que los identificamos ahorra un poco más que reunirlos en una matriz para imprimir al final; la razón es que significa que en ningún momento tenemos que preocuparnos por más de 3 elementos en la pila.
Disección
fuente
^
con\-
, puede reemplazar).*
con3*
. Esto no guardará ningún byte, pero reduce drásticamente el tiempo de ejecución y el uso de memoria. - Debería poder guardar un byte manteniendo el número entero en la parte superior de la matriz. El bucle tendrá el mismo número de bytes, pero la inicialización será un byte más corto.~.3*,1>\{(\(.p@+\|}*;
J - 28 char
Función tomando
n
como argumento.Ejecutamos una función,
n
como argumento izquierdo, en su argumento derecho repetidamente hasta que no produce ningún cambio. El argumento para comenzar es la lista2 4
.En la función misma, tomamos las sumas parciales
+/\
y la suma total+/
, y luego las incrementamos con ambas&:>:
. Luego generamos cada número entero de 2 a uno más que la suma total (2+i.
), y establecemos restar (-.
) las sumas parciales, dejando una secuencia figura-figura más larga por definición. Finalmente, acortamos o ampliamos cíclicamente la lista a la longitudn
.El resultado es que se
2 4
convierte3 7
, y esto se elimina de la2..8
partida2 4 5 6 8
. Después de otra ronda,2 4 5 6 8
se3 7 12 18 26
convierte enDe esta manera, repetidamente ampliamos la secuencia figura-figura. El
$
comportamiento de la longitud es solo una forma no trivial de guardar el carácter de esperar a que la secuencia crezca a una longitudn
o mayor, y generar eln
primeros valores cuando dejan de cambiar. Tampoco tenemos que esperar mucho: podemos obtener hasta 46336 términos de cuatro aplicaciones del verbo interno.La misma función en k:
{{x#y@&~_lin[y:1+!1+/y;1+\y]}[x]/2 4}
{{x#y@&~(y:2+!1+/y)in\:1+\y}[x]/2 4}
fuente
Java -
183158¡Esto fue lo máximo que he jugado al golf, y estoy orgulloso de ello! (Aunque no está cerca de la parte superior de los gráficos (porque es Java))
Gracias a Peter Taylor por las sugerencias.
más grande -
fuente
Byte.valueOf
ahorra tres, y dado que la pregunta no especifica el rango de entrada, creo que debería ser aceptable. Fuera de los bucles,m
solo se usa para inicializarn
, por lo quek++<m
podría serm-->0
, eliminando pork
completo.int[] n
se puede inicializarint n[]
y fusionar en el inicializador anterior.n
nunca tiene valores distintos de1
, por lo quen[...]!=0
podría sern[...]>0
. El inicializador puede convertirse en la parte inicial del primerfor
bucle.u
y sólo tiene que utilizar++w
, no hay necesidad de ajustarn[q]
on[w]
. Hay un error, en el que se ejecuta al final den
cuándom==2
, que parece resolverse mejor inicializandon=new int[2*m*m]
, pero creo que se reduce a 157 bytes.for(int q=1,w=2,m=...,n[]=...;m-->0;){...
guardar un punto y coma.Python 2 - 77 bytes
Código:
Funciona igual que la solución de @ histocrat, excepto que la entrada proviene de stdin.
fuente
Python 2 - 68
fuente
Jalea , 15 bytes
Pruébalo en línea!
Error de memoria en la entrada de 6.
Cómo funciona
Versión más eficiente, 16 bytes.
Pruébalo en línea!
Utiliza una idea de esta respuesta J . Trunca a la longitud deseada cada iteración, y toma el punto de fijación. Pensé en usar
S
(sum) en lugar deṀ‘
(max + 1), pero no puedo garantizar su corrección.fuente