Generiere Hofstädters Figur-Figur-Sequenz

16

Douglas Hofstadter führt in Gödel, Escher, Bach eine ganzzahlige Folge ein, die gemeinhin als Figur-Figur-Folge bezeichnet wird:

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

Es mag Ihnen Spaß machen, die Definition der Sequenz als Teil der Herausforderung selbst zu erarbeiten. Wenn Sie sie jedoch nicht herausfinden können oder wollen, finden Sie sie in OEIS als Sequenz A030124 und eine etwas klarere Definition in Wikipedia .

Schreiben Sie ein Programm oder eine Funktion, die nüber STDIN, ARGV oder ein Funktionsargument eine Liste der ersten nNummern der Sequenz in einem beliebigen vernünftigen Listenformat an STDOUT ausgibt.

Dies ist Codegolf, die kürzeste Lösung in Bytes gewinnt.

Martin Ender
quelle

Antworten:

6

CJam, 38 30 29 21 Bytes

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

Probieren Sie es online aus.

Wie es funktioniert

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.                  ";

Beispiellauf

$ 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
quelle
Sie haben das "s out of aditsu" verpasst, als Sie die URL für den Interpreter
Beta Decay,
@ BetaDecay dann warum nicht bearbeiten, um es zu beheben;)
Martin Ender
@ Martin Ich dachte nicht, ich hätte genug Repräsentanten ...
Beta Decay
2
@BetaDecay Tust du nicht, aber du kannst sie trotzdem vorschlagen (was dir sogar 2 Wiederholungen gibt, wenn sie akzeptiert werden).
Martin Ender
Ich fühlte mich so schlau, 8 zusätzliche Bytes meines Codes abzuspielen. Dann wurde mir klar, dass es jetzt genau das Gleiche tut wie die Antworten von Histokrat, Matsjoyce und Peter Taylor ...
Dennis
5

Rubin, 54 48

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

Demo

Edit: Golfed dies ein bisschen mehr, als mir klar wurde, dass ich nicht die vollständige Komplementsequenz im Gedächtnis behalten muss. So funktioniert es jetzt: Wir verwenden x, um die größte berechnete Zahl in der Komplementsequenz zu verfolgen, und es bhandelt sich um einen Pool von Kandidaten für die Sequenz. nMal geben wir das kleinste verbleibende Element in aus bund addieren es x, um die nächste Zahl in der Komplementsequenz zu berechnen. Dann entfernen wir beide Zahlen aus dem Kandidatenpool, sodass wir immer die kleinste Zahl ausgeben, die keiner Sequenz bereits hinzugefügt wurde.

Ruby-Golf-Tricks: Die Stabby-Lambda-Syntax ist kürzer als eine Methodendefinition. Die Anforderung, dass die Ausgabe an STDOUT anstatt als Rückgabewert ausgegeben wird, hat mich dazu inspiriert, die Tatsache zu verwenden, dass der Rückgabewert von p(x)ist x, an die ich mich normalerweise nicht erinnere, da dies in der in Anarchy Golf verwendeten Ruby-Version nicht der Fall ist.

Histokrat
quelle
1
Wie funktioniert es?
stolzer Haskeller
1
FWIW könntest du benutzen 2..2*n. Ich muss verwenden, n*nweil ich es effektiv mache, b = [x]^bdamit ich das größte Element von bgrößer als den größten Wert von brauche x, aber Ihr b -= [x]verlangt nur, dass es bden größtmöglichen Wert der Ausgabesequenz enthält.
Peter Taylor
5

Haskell, 67 61 60 56 55 53 Zeichen

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

zurück zum ersten Algorithmus.

Diese Lösung berechnet die Komplementsequenz durch Summieren der Startelemente der Sequenz. Dann berechnet es die Folge als alle Zahlen zwischen den Folgenummern des Komplements.

(#)ist die Funktion, die die Zahlen zwischen der Komplementsequenz berechnet.
hist die Sequenz selbst.
gist die Funktion, die die Frage beantwortet.

Die g-Funktion ist so definiert, dass sie nur die benötigte Anzahl von Elementen aus h entnimmt.

Feinheiten:

hist eigentlich die Figurenfolge mit Ausnahme der ersten 2 Elemente.
Es wird nicht die Komplementsequenz berechnet, sondern die Komplementsequenz mit der hinzugefügten 1 für jedes Element.
Diese beiden Feinheiten sind der Grund scanl(+)8h(das ist der Code für die Komplementsequenz (mit Ausnahme der ersten 2 Elemente) mit hinzugefügten Einsen) 8. Es ist für das dritte Element der Komplementsequenz, dem 1 hinzugefügt wurde.
der Grund , wird die Berechnung die ersten beiden Elemente nicht fehlen, weil sie in dem Nachspiel sind gin 2:4:h.

Beispiel:

>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]
stolzer haskeller
quelle
4

GolfScript ( 24 21 Bytes)

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

Online-Demo

Dies fing ganz anders an, endete aber auf einer GolfScript-Portierung der Ruby-Lösung von Histocrat , bevor Dennis einige Vorschläge machte, die in eine etwas andere Richtung gehen. Insbesondere das Drucken der Nummern bei der Identifizierung spart eine Menge Zeit, wenn Sie sie am Ende in einem Array zum Drucken zusammenfassen. Der Grund dafür ist, dass wir uns zu keinem Zeitpunkt Gedanken über mehr als drei Gegenstände auf dem Stapel machen müssen.

Präparation

~.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
quelle
Wenn Sie ersetzen ^mit \-, können Sie ersetzen ).*mit 3*. Dadurch werden keine Bytes gespart, aber die Laufzeit und die Speichernutzung werden drastisch reduziert. - Sie sollten ein Byte speichern können, indem Sie die Ganzzahl über dem Array belassen. Die Schleife hat die gleiche Byteanzahl, die Initialisierung ist jedoch ein Byte kürzer.
Dennis
2
Set Union funktioniert noch besser als Unterschied:~.3*,1>\{(\(.p@+\|}*;
Dennis
3

J - 28 Zeichen

Funktion nals Argument nehmen.

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

Wir führen eine Funktion mit dem nArgument left so oft auf das Argument right aus, bis keine Änderung mehr erfolgt. Das zu startende Argument ist die Liste 2 4.

In der Funktion selbst nehmen wir die Teilsummen +/\und die Gesamtsumme +/und erhöhen sie dann mit &:>:. Wir generieren dann jede ganze Zahl von 2 bis zu einer, die mehr als die volle Summe ( 2+i.) ist, und setzen subtrahieren ( -.) die Teilsummen, wobei wir per Definition eine längere Figur-Figur-Sequenz hinterlassen. Schließlich kürzen oder verlängern wir die Liste zyklisch auf Länge n.

Das Ergebnis ist, dass 2 4wird 3 7, und dies wird vom 2..8Verlassen entfernt 2 4 5 6 8. Nach einer weiteren Runde 2 4 5 6 8wird 3 7 12 18 26wird

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

Auf diese Weise erweitern wir immer wieder die Figurenfolge. Das $Längenverhalten ist nur eine nicht triviale Methode, um darauf zu warten, dass die Sequenz länger noder länger wird, und die nersten Werte auszugeben , wenn sie sich nicht mehr ändern. Wir müssen auch nicht lange warten: Wir können bis zu 46336 Terme aus vier Anwendungen des inneren Verbs erhalten.

Die gleiche Funktion in k:

  • k2, 37 Zeichen: {{x#y@&~_lin[y:1+!1+/y;1+\y]}[x]/2 4}
  • k4, 36 Zeichen: {{x#y@&~(y:2+!1+/y)in\:1+\y}[x]/2 4}
algorithmshark
quelle
2

Java - 183 158

Das war das Meiste, was ich je golfen habe und ich bin stolz darauf! (Obwohl es nicht in der Nähe der Spitze der Charts ist (weil es Java ist))

Danke an Peter Taylor für die Vorschläge

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;);}}}

größer -

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;)
                ;
        }
    }
}
Stretch Maniac
quelle
Diese innere for-Schleife ist beeindruckend verschleiert, aber ich denke, Sie können ein paar Bytes sparen. Byte.valueOfspart drei, und da die Frage nicht den Bereich der Eingabe spezifiziert, denke ich, sollte es akzeptabel sein. Außerhalb der Schleifen mwird nur zur Initialisierung verwendet n, so k++<mkönnte sein m-->0, beseitigen kvollständig. int[] nkann als initialisiert int n[]und mit dem vorherigen Initialisierer zusammengeführt werden. nhält niemals andere Werte als 1, so n[...]!=0könnte es sein n[...]>0. Der Initialisierer kann dann der Initialisiererteil der ersten forSchleife werden.
Peter Taylor
Und wenn Sie loswerden uund nur verwenden ++w, müssen Sie n[q]oder nicht einstellen n[w]. Es gibt einen Fehler, dass Sie das Ende ablaufen , nwenn m==2, das scheint nach der Initialisierung am besten festgelegt werden n=new int[2*m*m], aber ich denke , es ist auf 157 Bytes nach unten.
Peter Taylor
Was ich damit gemeint habe, dass der Initialisierer der Initialisierungsteil der ersten for-Schleife wird, war das for(int q=1,w=2,m=...,n[]=...;m-->0;){...Speichern eines Semikolons.
Peter Taylor
1

Python 2 - 77 Bytes


Code:

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

Funktioniert genauso wie die Lösung von @ histocrat, außer dass die Eingabe von stdin stammt.

Matsjoyce
quelle
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
quelle
0

Gelee , 15 Bytes

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

Probieren Sie es online!

Speicherfehler am Eingang von 6.

Wie es funktioniert

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

Effizientere Version, 16 Bytes

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

Probieren Sie es online!

Verwendet eine Idee aus dieser Antwort . Schneiden Sie jede Iteration auf die gewünschte Länge ab und nehmen Sie den Fixpunkt. Ich habe überlegt, S(sum) anstelle von Ṁ‘(max + 1) zu verwenden, kann aber die Richtigkeit nicht garantieren.

Bubbler
quelle
12 Bytes .
Erik der Outgolfer 15.11.18