Upside-Down Pyramid Addition ist der Vorgang, bei dem eine Liste von Zahlen erstellt und nacheinander addiert wird, bis eine Zahl erreicht ist.
Wenn die Zahlen angegeben 2, 1, 1
werden, geschieht Folgendes:
2 1 1
3 2
5
Dies endet in der Nummer 5
.
DEINE AUFGABE
Schreiben Sie auf der rechten Seite einer auf dem Kopf stehenden Pyramide (aufsteigend) ein Programm oder eine Funktion, die die ursprüngliche Liste zurückgibt.
Neue Extra-Herausforderung : Versuchen Sie dies in weniger als O (n ^ 2)
BEISPIEL
f([5, 2, 1]) => [2, 1, 1]
f([84,42,21,10,2]) => [4,7,3,8,2]
HINWEIS: Die umgedrehte Pyramide ist niemals leer und besteht NUR aus positiven ganzen Zahlen.
code-golf
math
fastest-algorithm
algorithm
Wimmern
quelle
quelle
Try doing this in less than O(n)
Sicherlich ist es unmöglich, ein Array der Größe n zuzuweisen oder O (n) Elemente darin schneller als O (n) Komplexität zu ändern.Antworten:
JavaScript (ES6),
62 58 4946 Bytes3 Bytes gespart dank @Oliver
Gibt die Liste als durch Kommas getrennte Zeichenfolge zurück.
Probieren Sie es online!
Kommentiert
quelle
Haskell , 22 Bytes
Probieren Sie es online!
quelle
Haskell, 42 Bytes
Probieren Sie es online!
quelle
TI-BASIC, 54 Bytes
Eingabe ist die Liste der rechten Seite des Dreiecks in
Ans
, wie in der Challenge beschrieben.Die Ausgabe ist die oberste Reihe des Dreiecks.
Beispiele:
Erläuterung: Bei
dieser Lösung wird die Tatsache missbraucht, dass das Dreieck, das mit der rechten Seite des Dreiecks als Start gebildet wird, die Änderung in jedem Element ist.
Mit anderen Worten,
wird:
Die resultierende Liste ist somit die rechte Seite dieses neuen Dreiecks, das durch Setzen des letzten Elements auf den Index der Länge der übergeordneten Liste in der resultierenden Liste gebildet werden kann.
Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.
quelle
Gelee , 6 Bytes
Ein monadischer Link, der eine Liste von ganzen Zahlen akzeptiert, die eine Liste von ganzen Zahlen ergibt.
Probieren Sie es online!
Wie?
Bildet das gesamte Dreieck und extrahiert dann die erforderlichen Elemente.
quelle
U
s stattṚ
!IƬUZḢA
würde auch mit der gegebenen Frage arbeiten; Ich frage mich, ob irgendwo ein Byte gespeichert ist ...ạƝƬZṪ€
funktioniert auch, ist aber wieder eine Sechs.MathGolf ,
1411 BytesProbieren Sie es online!
Erläuterung
quelle
Python 2 , 56 Bytes
Eine rekursive Funktion, die eine Liste positiver Ganzzahlen akzeptiert und eine Liste nicht negativer Ganzzahlen zurückgibt.
Probieren Sie es online!
quelle
Gelee , 5 Bytes
Probieren Sie es online!
Wir können davon ausgehen, dass die gesamte Pyramide positiv ist, sodass wir eine && -Operation anstelle einer "richtigen" Operation verwenden können.
quelle
Pari / GP , 36 Bytes
Basierend auf @Lynns Kommentar:
In Pari / GP ist eine Pascal-Matrix integriert, deren Inverse genau die Matrix ist, die wir benötigen:
Probieren Sie es online!
quelle
R ,
6967 BytesProbieren Sie es online!
Gibt einen Spaltenvektor zurück.
-2 Bytes dank Kirill L.
Auch basierend auf Lynns Kommentar:
Es ist länger als die andere Antwort von R, aber es war ein interessanter Ansatz, Golf zu spielen und zu versuchen.
quelle
Javascript (ES6), 127 Byte
Originalcode
Oh, ich habe gerne ... viel verloren ... auf die vorherige Antwort ...
quelle
Wolfram Language (Mathematica) , 57 Byte
Probieren Sie es online!
quelle
05AB1E ,
1211 BytesPort of @JonathanAllan ‚s Jelly Antwort , obwohl ich Gelee über Jelly bequemen builtins in diesem Fall. ;)
-1 byte dank @Emigna .
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
quelle
R.¥.Γ¥}¨
indem Sie von der Liste ausgehen, deren Delta die Eingabe ist.R ,
55635553 BytesProbieren Sie es online!
-2 Bytes dank Giuseppe.
quelle
Perl 6 , 37 Bytes
Probieren Sie es online!
Reduziert wiederholt um elementweise Subtraktion und gibt dann die letzte Nummer jeder Liste in umgekehrter Reihenfolge zurück.
Erläuterung:
quelle
Python 2 , 78 Bytes
Probieren Sie es online!
quelle
C # (Visual C # Interactive Compiler) , 164 Byte
Probieren Sie es online!
quelle
Holzkohle , 19 Bytes
Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:
Wiederholen Sie einmal für jeden Begriff in der ursprünglichen Liste.
Geben Sie den letzten Begriff in der Liste aus, bewegen Sie den Cursor jedoch an den Anfang der vorherigen Zeile, damit die Begriffe in umgekehrter Reihenfolge ausgegeben werden.
Berechnen Sie die Deltas, indem Sie am Anfang einen Dummy-Wert einfügen, damit wir eine Operation verwenden können, die die Länge der Liste nicht ändert.
quelle
APL + WIN, 34 oder 28 Bytes
Probieren Sie es online! Mit freundlicher Genehmigung von Dyalog Classic
Fordert zur Eingabe des Vektors auf der rechten Seite auf.
oder @Lynns Ansatz implementieren:
Probieren Sie es online aus! Mit freundlicher Genehmigung von Dyalog Classic
Fordert zur Eingabe des Vektors auf der rechten Seite auf.
quelle
Attache , 29 Bytes
Probieren Sie es online!
Durchläuft die
Delta
Funktion einfach, bis sie leer ist. Viel kürzer als die sehr ausführlichePeriodicSteps
Lösung ...quelle
C 76 Bytes
Eingabe :
(*a = pointer to array, n = last element's index of that array)
Ausgabe :
return int* = output
Erklärung
von rechts nach oben, da die letzten Elemente sowohl in der Eingabe als auch in der Ausgabe gleich sind, findet die Funktion "Schleife innen" einfach die nächsthöheren Zahlen im Dreieck, die allmählich nach oben reichen und die Antwort am Ende intakt lassen.
ungolfed (aus C ++)
quelle
Japt ,
119 BytesVersuch es
2 Bytes gespart dank Oliver.
1211 BytesVersuch es
Dank Oliver 1 Byte gespart.
quelle
y(f)
ist schon schlimm genug, aber die Newline komplett zu vergessen, ist unverzeihlich! Wird in Kürze aktualisiert. Danke :)Julia 0,6 , 44 Bytes
Probieren Sie es online!
Gleiches iteratives Prinzip wie meine R-Antwort.
Julia 0,6 , 55 Bytes
Probieren Sie es online!
@ Lynns Algorithmus (Inverse der Pascal-Matrix multipliziert mit der Eingabe).
quelle