Generar la secuencia figura-figura de Hofstadter

16

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 ntravés de STDIN, ARGV o argumento de función, imprima una lista de los primeros nnú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.

Martin Ender
fuente

Respuestas:

6

CJam, 38 30 29 21 bytes

li_3*,2>\{(_pX+:X-}*;

Pruébalo en línea.

Cómo funciona

li                     " Read an integer N from STDIN.              ";
  _3*,2>               " Push S := [ 2 3 ... (N * 3 - 1) ].         ";
        \{        }*   " Do the following N times:                  ";
          (            " Shift an integer I from S.                 ";
           _p          " Print a copy of I, followed by a linefeed. ";
             X+:X      " Execute X += I. (X is initialized to 1.)   ";
                 -     " Remove X from S.                           ";
                    ;  " Discard S from the stack.                  ";

Ejecución de ejemplo

$ cjam <(echo 'li_3*,2>\{(_pX+:X-}*;') <<< 20
2
4
5
6
8
9
10
11
13
14
15
16
17
19
20
21
22
23
24
25
Dennis
fuente
Te has perdido el aditsu al escribir la url para el intérprete
Beta Decay
@BetaDecay, entonces, ¿por qué no editar para arreglarlo?)
Martin Ender
@ Martin No pensé que tenía suficiente reputación ...
Beta Decay
2
@BetaDecay No lo haces, pero aún puedes sugerirlos (lo que incluso te da 2 repeticiones si son aceptados).
Martin Ender
Me sentí muy listo para jugar 8 bytes adicionales de mi código. Entonces me di cuenta de que ahora hace exactamente lo mismo que las respuestas de histocrat, matsjoyce y Peter Taylor ...
Dennis
6

Haskell, 67 61 60 56 55 53 caracteres

g n=take n$2:4:h
a#(x:s)=[a..x-2]++x#s
h=5#scanl(+)8h

volviendo 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.
hEs la secuencia misma.
ges la función que responde la pregunta.

la función g se define para tomar la cantidad necesaria de elementos de h.

sutilezas:

hes 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 tiene 8. 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 gen 2:4:h.

ejemplo:

>g 50
[2,4,5,6,8,9,10,11,13,14,15,16,17,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,36,37,38,39,40,41,42,43,44,46,47,48,49,50,51,52,53,54,55,57,58,59]
orgulloso Haskeller
fuente
5

Rubí, 54 48

f=->n{x=1
b=*2..n*n
n.times{b-=[x+=p(b.shift)]}}

Manifestació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: utilizamosx para realizar un seguimiento del número calculado más grande en la secuencia del complemento, y bes un grupo de candidatos para la secuencia. nveces, sacamos el elemento restante más pequeño by lo agregamos xpara 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.

histocrat
fuente
1
¿Como funciona?
orgulloso Haskeller
1
FWIW que podrías usar 2..2*n. Tengo que usar n*nporque lo estoy haciendo de b = [x]^bmanera efectiva, por lo que necesito que el elemento más bgrande sea mayor que el valor más grande de x, pero b -= [x]solo requiere que bcontenga el mayor valor posible de la secuencia de salida.
Peter Taylor
4

GolfScript ( 24 21 bytes)

~.3*,1>\{(\(.p@+\|}*;

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

~.3*,           # Eval input n, dup, multiply by 3, make list [0 1 ... 3n-1]
1>              # Discard 0, which is part of neither sequence
\{              # Execute n times: stack contains pool of numbers not yet seen
                # in either sequence and the first element of it is the next element of the
                # complement sequence
  (\(           #   Pop two numbers from the start of the pool: stack is
                #     pool[0] pool[2..max] pool[1]
  .p            #   Print pool[1]
  @+            #   Rotate pool[0] to top and add to pool[1]
  \|            #   Place pool[0]+pool[1] at the start of the pool and
                #   (this is the clever bit) remove it from later in the pool
}*
;               # Discard the unused remainder of the pool
Peter Taylor
fuente
Si reemplaza ^con \-, puede reemplazar ).*con 3*. 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.
Dennis
2
Establecer unión funciona incluso mejor que la diferencia:~.3*,1>\{(\(.p@+\|}*;
Dennis
3

J - 28 char

Función tomando ncomo argumento.

($+/\(-.~2+i.)&:>:+/)^:_&2 4

Ejecutamos una función, ncomo argumento izquierdo, en su argumento derecho repetidamente hasta que no produce ningún cambio. El argumento para comenzar es la lista 2 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 longitud n.

El resultado es que se 2 4convierte 3 7, y esto se elimina de la 2..8partida 2 4 5 6 8. Después de otra ronda, 2 4 5 6 8se 3 7 12 18 26convierte en

2 4 5 6 8 9 10 11 13 14 15 16 17 19 20 21 22 23 24 25 27

De 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 longitud no 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:

  • k2, 37 caracteres: {{x#y@&~_lin[y:1+!1+/y;1+\y]}[x]/2 4}
  • k4, 36 caracteres: {{x#y@&~(y:2+!1+/y)in\:1+\y}[x]/2 4}
Algoritmo de tiburón
fuente
2

Java - 183 158

¡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.

class f{public static void main(String[]a){int q=1,m=Byte.valueOf(a[0]),w=2,n[]=new int[m*m*2];for(n[q+=w]=1;m-->0;){System.out.println(w);for(;n[++w]>0;);}}}

más grande -

public class f {
    public static void main(String[] a) {
        int q = 1, m = Byte.valueOf(a[0]), w = 2, n[] = new int[m * m * 2];
        for (n[q += w] = 1; m-- > 0;) {
            System.out.println(w);
            for (; n[++w] > 0;)
                ;
        }
    }
}
Estiramiento Maniaco
fuente
Ese bucle for interno está bastante ofuscado, pero creo que puede guardar algunos bytes. Byte.valueOfahorra tres, y dado que la pregunta no especifica el rango de entrada, creo que debería ser aceptable. Fuera de los bucles, msolo se usa para inicializar n, por lo que k++<mpodría ser m-->0, eliminando por kcompleto. int[] nse puede inicializar int n[]y fusionar en el inicializador anterior. nnunca tiene valores distintos de 1, por lo que n[...]!=0podría ser n[...]>0. El inicializador puede convertirse en la parte inicial del primer forbucle.
Peter Taylor
Y si a deshacerse de uy sólo tiene que utilizar ++w, no hay necesidad de ajustar n[q]o n[w]. Hay un error, en el que se ejecuta al final de ncuándo m==2, que parece resolverse mejor inicializando n=new int[2*m*m], pero creo que se reduce a 157 bytes.
Peter Taylor
Lo que quise decir sobre que el inicializador se convirtió en la parte inicial del primer bucle for fue for(int q=1,w=2,m=...,n[]=...;m-->0;){...guardar un punto y coma.
Peter Taylor
1

Python 2 - 77 bytes


Código:

n=input();x=1;b=range(2,n*n)
while n:v=b.pop(0);x+=v;print v;b.remove(x);n-=1

Funciona igual que la solución de @ histocrat, excepto que la entrada proviene de stdin.

matsjoyce
fuente
1

Python 2 - 68

R=[1]
s=0
n=input()
while n:s+=1+(s+1in R);R+=[R[-1]+s];print s;n-=1
Falko
fuente
0

Jalea , 15 bytes

SƤŻ‘µṀ‘Rḟ
2dz¡ḣ

Pruébalo en línea!

Error de memoria en la entrada de 6.

Cómo funciona

SƤŻ‘µṀ‘Rḟ  Aux. link (monad). Input: part of the desired sequence
SƤŻ‘       Sum of prefixes, then prepend a zero and increment
           This is a list of numbers to exclude from the next iteration
    µ      Re-focus on the above
     Ṁ‘Rḟ  Create range 1..Max + 1, then remove all elements of the above
           +1 is needed to progress from [2] to [2,4]

2dz¡ḣ  Main link (monad). Input: n, number of terms
2dz¡   Starting from 2, apply aux. link n times
    ḣ  Take n elements from the beginning

Versión más eficiente, 16 bytes.

SƤŻ‘µṀ‘Rḟḣ³
2ÇÐL

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.

Bubbler
fuente
12 bytes .
Erik the Outgolfer