22

Die Differenzliste einer Liste von ganzen Zahlen ist die Differenzliste von aufeinanderfolgenden Mitgliedern.

Zum Beispiel die Differenzliste von

1, 3, 2 ,4

ist

2, -1, 2

Ihre Aufgabe ist es, eine Differenzliste als Eingabe zu nehmen und auszugeben, wie die Differenzliste aussehen würde, wenn die ursprüngliche Liste sortiert wäre.

Zum Beispiel die Differenzliste

2, 1, -2, -1

Könnte eine Liste darstellen

2 4 5 3 2

Was wenn sortiert ist

2 2 3 4 5

Welches hat eine Differenzliste von

0 1 1 1

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

code-golf array-manipulation Weizen-Assistent
quelle

Sind Lösungen garantiert einzigartig?

H.PWiz

@ H.PWiz Ja das sind sie.

Weizen-Zauberer

Verbunden.

Totalhuman

1

@ H.PWiz Schneller Beweis: Eine Liste lässt sich perfekt aus einer Differenzliste (DL) zusammen mit einem ersten Elementwert rekonstruieren, sodass eine Eins-zu-Eins-Konvertierung von L in (FV, DL) erfolgt. Das Erhöhen des FV um einen beliebigen Betrag entspricht dem Addieren dieses Betrags zu jedem Element des L und kann daher die Sortierung von L nicht ändern, wenn dieser Vergleich angemessen monoton ist. (Mit anderen Worten, es wirkt sich nicht auf die Sortierung aus, es sei denn, die Zahl, die Sie hinzufügen, verursacht einen Ganzzahlüberlauf.)

CR Drost

1

Könnten Sie noch ein paar Testfälle hinzufügen? Ich bemerke [-2, 100, -2, -1]zum Beispiel einige Lösungen, die unterschiedliche Ergebnisse liefern .

Shaggy

16

05AB1E , 4 Bytes

.¥{¥

Probieren Sie es online!

Erläuterung

.¥{¥
.¥   # Undelta the input list
  {  # Sort it
   ¥ # And get the deltas

Datboi
quelle

Undelta05AB1E hat die meisten eingebauten Nischen. o0

totalhuman

2

Ahh Mist, schlag mich drauf an. Ich wollte schon immer undelta verwenden.

Magic Octopus Urn

16

Undeltaಠ ___ ಠ

Business Cat

1

"Undelta" ist einfach eine kumulative Summe, oder?

Zgarb

2

@Zgarb Undelta fügt eine 0 als erstes Element der Liste hinzu, genau wie Sie gesagt haben, kumulative Summe oder umgekehrtes Delta.

Magic Octopus Urn

9

Python 3 mit Numpy , 56 54 53 Bytes

2 Bytes weniger dank @Artyer (Numpy's sortstatt Standard sorted). 1 Byte weg dank @notjagan (Umzug 0in cumsum)

lambda x:diff(sort(cumsum([0]+x)))
from numpy import*

Der Code definiert eine anonyme Funktion, die eine Liste oder ein Numpy-Array eingibt und ein Numpy-Array ausgibt.

Probieren Sie es online!

Luis Mendo
quelle

1

Woah, du hast mir heute etwas Neues beigebracht. Meine Annäherung an numpywar viel länger. Ich werde morgen wiederkommen, um das abzustimmen, weil ich sehe, dass du schon mit einer Kappe bedeckt bist. Sehr schön!

Mr. Xcoder

@ Mr.Xcoder Danke! Ich bin kein Experte für Numpy, ich habe nur verfolgt, was ich in Matlab getan habe: diff(sort([0 cumsum(x)]))(in Matlab [ ]ist Verkettung)

Luis Mendo

Pflicht erfüllt!

Mr. Xcoder

-1 Byte durch Verschieben der 0in die cumsum.

Notjagan

5

Mathematica, 40 Bytes

Differences@Sort@Accumulate@Join[{1},#]&

J42161217
quelle

Differences@Sort@FoldList[+##&,1,#]&

Alephalpha

4

Gelee , 6 Bytes

0;+\ṢI

Probieren Sie es online!

Erik der Outgolfer
quelle

4

Schale , 4 Bytes

Ẋ-O∫

Probieren Sie es online!

Erklärung

      -- implicit input, e.g                               [2,1,-2,-1]
   ∫  -- cumulative sum                                    [0,2,3,1,0]
  O   -- sort                                              [0,0,1,2,3]
Ẋ     -- apply function to all adjacent pairs in the list  [(0,0),(0,1),(1,2),(2,3)]
 -    --   subtract                                        [0,1,1,1]

H.PWiz
quelle

Eine andere Sprache, die Undelta hat? Oder ein schicker eingebauter?

Mr. Xcoder

@Herr. Xcoder Es kommt vor, dass Cumsum dasselbe ist wie Undelta

H.PWiz

@ H.PWiz Eigentlich nennen wir das nicht Cumsum ... es sei denn, du berücksichtigst das leere Präfix.

Erik der Outgolfer

@EriktheOutgolfer Ja, genau das macht Hülsen wie scanl(+)0in Haskell.

H.PWiz

4

Pyth , 9 Bytes

-1 Byte dank @EriktheOutgolfer .

.+S+0sM._

Test Suite.

Pyth , 10 Bytes

.+S.u+YNQ0

Probieren Sie es online! oder Probieren Sie weitere Testfälle aus .

Mr. Xcoder
quelle

Wie in meiner (gelöschten) Antwort können Sie +0sM._anstelle von .u+YNQ0-1 verwenden.

Erik der Outgolfer

@EriktheOutgolfer Warum hast du es gelöscht?

Mr. Xcoder

Dachte, die Kernidee war deiner zu ähnlich.

Erik der Outgolfer

@EriktheOutgolfer Ok, danke dann

Mr. Xcoder

m=+Zist eine Variante mit der gleichen Länge für sM._, aber leider scheint es nicht so, als könnte sie kürzer sein.

FryAmTheEggman

4

JavaScript (ES6), 57 56 Bytes

1 Byte dank @ETHproductions eingespart

a=>a.map(n=>t-=n,p=t=0).sort((a,b)=>b-a).map(n=>p-(p=n))

Demo

Code-Snippet anzeigen

let f =

a=>a.map(n=>t-=n,p=t=0).sort((a,b)=>b-a).map(n=>p-(p=n))

console.log(JSON.stringify(f([2, 1, -2, -1])))

Expand snippet

Arnauld
quelle

.sort((a,b)=>a-b)Das ist der Weg, um Deltas zu bekommen? Durch Sortieren mit Subtraktion? : P

totalhuman

@totallyhuman Der erste map()gibt die Deltas. Dieser Code sortiert sie. Die 2. Karte baut die neuen Deltas wieder auf. Die JS- sort()Methode verwendet standardmäßig die lexikografische Reihenfolge. Wir brauchen diesen speziellen Rückruf für Nummern> 9 (leider).

Arnauld

Das macht -p+(p=n)mir zu schaffen, aber leider gibt es keinen besseren Weg ... es sei denn ...

ETHproductions

was zum Teufel, habe ich drücke nicht die Absenden - Button> _ <Aber wie auch immer, ich glaube , Sie einen Byte mit dem Bearbeiten speichern ...

ETHproductions

@ETHproductions Danke :-)

Arnauld

3

Java 8, 123 Bytes

Die Standardlösung: Summeneingabe kumulieren, sortieren, dann diff. Auch keine wesentlichen Implementierungstricks.

l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;)l[i]=d[i+1]-d[i];}

Besetzung für Consumer<int[]>. Ausgang ist mutierter Eingang.

Probieren Sie es online

Ungolfed Lambda

l -> {
    int
        s = l.length,
        d[] = new int[s + 1],
        i = 0
    ;
    while (i < s)
        d[i + 1] = d[i] + l[i++];
    for (java.util.Arrays.sort(d); i-- > 0; )
        l[i] = d[i + 1] - d[i];
}

Danksagung

-3 Bytes dank Olivier Grégoire , Meister der unheiligen Autoinkrementierung
-1 Byte danke an Nevay

Jakob
quelle

1

Sie können 3 Bytes Golf spielen, indem Sie die Positionen neu anordnen, an denen Sie Ihre Inkremente und Ihre Gesamtberechnungen durchführen:

l->{int s=l.length,d[]=new int[s+1],i=0;for(;i<s;)d[i+1]=d[i]+l[i++];java.util.Arrays.sort(d);for(i=0;i<s;)l[i]=-d[i]+d[++i];}

(Achten Sie beim Kopieren / Einfügen auf die unsichtbaren SE-Zeichen)

Olivier Grégoire,

1

Vielen Dank für meinen neuen Titel;) Hier ist noch mehr Unheil zu feiern for(;i>0;)l[i-1]=d[i]-d[--i];(letzte Runde)

Olivier Grégoire

Ich hatte gerade diese Schleife selbst überarbeitet und kam auf for(;i-->0;)l[i]=d[i+1]-d[i];die gleiche Länge. Update zu kommen.

Jakob

2

Sie können 1 Byte mit speichern

l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;l[i]=d[i+1]-d[i]);}

.

Nevay

Ach ja natürlich Vielen Dank!

Jakob

2

Brachylog , 15 Bytes

a₀ᶠ+ᵐ,0o{s₂↔-}ᶠ

Probieren Sie es online!

Erik der Outgolfer
quelle

2

R , 31 32 Bytes

-4 Bytes danke an @ user2390246 für diffinv

+5 Bytes von Jarko für cat

cat(diff(sort(diffinv(scan()))))

Liest von stdin, schreibt nach stdout. diffinvist eine Umkehrung vondiff für einen bestimmten Startwert (standardmäßig 0). Da es wieder diffbearbeitet wird, spielt es keine Rolle, wie hoch dieser Wert ist.

Wie Jarko Dubbeldam betonte, musste ich das Ergebnis auf Kosten von fünf Bytes korrekt ausgeben. Ach.

Probieren Sie es online!

Giuseppe
quelle

Das hatte ich auch im Sinn. Muss zwar den Druckvorgang abwickeln, da dies als vollständiges Programm (durch source) ausgeführt wird, wird nichts ausgegeben.

JAD

1

Wenn Sie diffinvanstelle von verwenden, müssen cumsumSie keine Null voranstellen.

user2390246

@ user2390246 wow, sehr schön! Bis etwa diffinv.

Giuseppe

Ich auch! Ich hatte gerade eine schnelle Suche, um zu sehen, ob es irgendwelche früheren Antworten gab, auf die ich sie anwenden konnte.

user2390246

1

Python 2 , 83 Bytes

l,r=input(),[1]
for i in l:r+=[r[-1]+i]
r.sort()
print[b-a for a,b in zip(r,r[1:])]

Probieren Sie es online!

Schreckliche Lösung.

total menschlich
quelle

Es ist in der Tat nicht so schrecklich

Mr. Xcoder

Der Python- +=Operator für Listen kann mit jedem iterablen Operator verwendet werden, sodass Sie r+=r[-1]+i,anstelle von r+=[r[-1]+i]ein Byte ein Byte speichern können.

Jonathan Frech

1

Perl 6 , 46 Bytes

{[\+](0,|@_).sort.rotor(2=>-1).flat.map(*R-*)}

Versuch es

Erweitert:

{  # bare block lambda with implicit signature :(*@_)

  [\+](         # triangle reduce using &infix:«+»
    0,          # start with 0
    |@_         # Slip in the arguments from the outer block
  )             #                  (0, 2, 3, 1, 0)

  .sort         # sort the results (0,0,1,2,3)
  .rotor(2=>-1) # group in twos    ((0,0),(0,1),(1,2),(2,3))
  .flat         # flatten          (0,0,0,1,1,2,2,3)
  .map(*R-*)    # grab 2 values at a time, and subtract first from second
                # (0, 1, 1, 1)
}

Brad Gilbert b2gills
quelle

1

Haskell , 74 Bytes

import Data.List
g=sort.scanl(+)0
h l|k<-g l=map(\(x,y)->x-y)$zip(tail$k)k

Probieren Sie es online!

Einfach.

jferard
quelle

3

=<<von der Funktion Monade kommt als nützlich: (zipWith(-)=<<tail).sort.scanl(+)0

nimi

@ Nimi Sehr schön. Ich bin kein Experte für Monaden, aber ich hätte darüber nachdenken sollen zipWith.

jferard

1

TI-Basic (TI-84 Plus CE), 23 Byte

Prompt X
augment({0},cumSum(_LX→X
SortA(_LX
ΔList(_LX

Fordert zur Eingabe durch den Benutzer auf. Die Liste muss mit einem vorangestellten {, durch Nummern getrennten ,und optionalem nachgestellten Zeichen eingegeben werden} .

TI-Basic ist eine Token-Sprache . ΔList(undcumSum( sind Zwei-Byte-Token, alle anderen verwendeten Token sind jeweils ein Byte.

Beispiellauf (mit NAMEals Programmname und {4,-2,7,-4,0}als Eingabe):

prgmNAME
X=?{4,-2,7,-4,0}
               {2 2 1 0 4}

Erläuterung:

Prompt X                  # 3 bytes, get list input, store in _LX
augment({0},cumSum(_LX→X   # 12 bytes, 
          # store the list ({0} prepended to the cumulative sum of _LX) to _LX
SortA(_LX                  # 4 bytes, sort _LX ascending
ΔList(_LX                  # 4 bytes, implicitly print the difference list of _LX

Pizzapants184
quelle

Benötigen Sie die L?

Zacharý

@ Zacharý Sie können sie weglassen, wenn Sie eine Liste speichern. Wenn Sie sie jedoch weglassen, wird statt der Liste die numerische Variable X verwendet

pizzapants184

1

C ++ (gcc) , 136 Bytes

Als unbenanntes generisches Lambda unter der Annahme, dass die Eingabe identisch ist std::listund über den Referenzparameter zurückgegeben wird.

[](auto&L){auto r=L.begin(),l=L.insert(r,0);while(r!=L.end())*r+++=*l++;for(L.sort(),l=r=--L.end();--l!=L.begin();*r---=*l);L.erase(l);}

Probieren Sie es online!

Ungolfed:

[](auto&L){
 auto r=L.begin(),
      l=L.insert(r,0); //adds a zero right in front
 while(r!=L.end())
   *r++ += *l++;       //sum left to right
 for(
  L.sort(),            //sorting invalidates the iterators
  l=r=--L.end();       //so, reinit
  --l!=L.begin();      //decrement l beforehand 
  *r-- -= *l           //diff right to left
 );
 L.erase(l);           //l==L.begin(), so this removes the temporary 0
}

Karl Napf
quelle

1

Pyth, 8 Bytes

.+S+M.uP

Demonstration

.+S+M.uP
.+S+M.uPNQ    Implicit variables
     .u  Q    Apply the following function to the input repeatedly until it
              stops changing, then output the list of values, including the
              starting value.
       PN     Remove the last element. No-op if the list is empty.
   +M         Sum each list. This gives the cumulative sums in reverse order,
              including a 0 at the end for the empty list.
  S           Sort
.+            Deltas

isaacg
quelle

+1 Dies ist eine ordentliche Problemumgehung mit kumulativem Fixpunkt. Daran habe ich persönlich gar nicht gedacht.

Mr. Xcoder

1

TI-Basic, 20 Bytes

cumSum(augment({0},Ans->L1
SortA(L1
ΔList(L1

Timtech
quelle

1

Perl 5 , 87 + 1 (-a) = 88 Bytes

$a[0]=1;push@a,$a[-1]+$_ for@F;@a=sort{$a<=>$b}@a;print$a[0]-$_,$"while($_=shift@a)&&@a

Probieren Sie es online!

Xcali
quelle

1

VB.NET (.NET 4.5), 109 Bytes

Sub A(n)
Dim c=n.count-1
For i=1To c
n(i)+=n(i-1)
Next
n.Sort()
For i=c To 1 Step-1
n(i)-=n(i-1)
Next
End Sub

Eine Funktion, die eine Liste als Eingabe erwartet und direkt ändert. Der ursprüngliche Parameter kann dann für die Ausgabe verwendet werden

Erstellt eine ursprüngliche Liste durch Vorwärtsaddieren durch die Liste neu (setzt eine implizite 0 als erstes Element voraus)
Sortiert die ursprüngliche Liste
Ruft die Unterschiede durch Rückwärtsgehen ab (damit ich keine andere Liste verfolgen muss) (das implizite erste Element von 0 bedeutet, dass der erste Unterschied mit dem kleinsten Element identisch ist).

Probieren Sie es online!

Brian J
quelle

Würde es Ihnen etwas ausmachen, den TIO-Link zu aktualisieren?

Taylor Scott

@ TaylorScott Update auf welche Weise?

Brian J

Ihr TIO-Link zeigt einen völlig anderen Code als in Ihrer Antwort

Taylor Scott

1

@ TaylorScott Ahh .... Ich verstehe. Ich musste einige Anpassungen vornehmen, da TIO Mono verwendet, aber ich verwendete den .NET 4.5-Compiler

Brian J

1

APL (Dyalog) , 15 14 Bytes

-1 Byte dank ngn .

(¯2-/⍋⊃¨⊂)0,+\

+\ kumulative Summe

0, Stellen Sie eine Null voran

(… ) Wenden Sie dazu die folgende implizite Funktion an:

⊂ beifügen (damit wir mehrere Artikel auswählen können)

⍋⊃¨ Lassen Sie jeden der Indizes, die das Argument sortieren würden, davon auswählen

¯2-/ Umgekehrte paarweise Differenz

Probieren Sie es online!

Originelle Lösung, die die Teilnehmer des Code Golf Hackathon beim Dyalog '17 User Meeting gefunden haben :

¯2-/l[⍋l←+\0,⎕]

Probieren Sie es online!

⎕ Eingabeaufforderung

0, Stellen Sie eine Null voran

+\ kumulative Summe

l← speichern als l

⍋ Finden Sie die Indizes, die sortiert werden l

l[... ] benutze das um zu indexierenl

¯2-/ Umgekehrte paarweise Differenz

Adám
quelle

1

Ich weiß nicht, ob dies beim Hackathon erlaubt war, aber wenn Sie es in einem Punkt-freien Stil umschreiben, können Sie ein Zeichen sparen: (¯2- / ⍋⊃¨⍋⊃) 0, + \

ngn

@ngn In diesem Teil des Workshops wurde versucht, die Teilnehmer dazu zu bringen, mit PPCG zu beginnen. Daher galten hier die Regeln von PPCG. Vielen Dank.

Adám

1

MATL , 6 Bytes

0hYsSd

Probieren Sie es online!

0       # push 0
 h      # horizontal concatenate with implicit input
  Ys    # cumulative sum
    S   # sort
     d  # diff (implicit output)

Giuseppe
quelle

0

Gaia , 7 Bytes

1¤++⊣ȯọ

Probieren Sie es online!

Erläuterung

1¤+      Prepend 1
   +⊣    Cumulative sums
     ȯ   Sort
      ọ  Deltas

Geschäfts-Katze
quelle

0

k , 16 Bytes

1_-':{x@<x}@+\0,

Probieren Sie es online!

              0, /prepend a 0
            +\   /cumulative sum
     {x@<x}@     /sort
1_-':            /differences list

zgrep
quelle

0

Japt , 10 Bytes

iT å+ n än

Probier es aus

Zottelig
quelle

0

Röda , 42 Bytes

{i=0{[0];[i]if i+=_}|sort|slide 2|[_2-_1]}

Probieren Sie es online!

Dies ähnelt der Perl 6-Antwort . .sortist |sort, .rotor(2=>-1).flatist |slide 2 und .map(*R-*)ist|[_2-_1] .

Erläuterung:

{
  i=0 /* initialize variable i */
  /* the following block recreates the original list from differences: */
  {
    [0];       /* push 0 to the stream */
    [i]if i+=_ /* add every number in the stream to i and push i back */
  }|
  sort|    /* sort the numbers */
  slide 2| /* for values i1, i2, i3, ... in the stream
              push pairs i1, i2, i2, i3, ... */
  [_2-_1]  /* calculate difference of numbers in each pair in the stream */
}

Die Aussage [i]if i+=_ist äquivalent zu

for sfv do
  if i += sfv do
    push(i)
  done
done

Der +=Operator gibt keine Werte an den Stream weiter, es ist also wahr. Ich hätte auch eine Art Block (zB {|j|i+=j;[i]}_) verwenden können, um die Additions- und Push-Anweisungen zusammenzufügen, ist aber ifkürzer.

fergusq
quelle

0

Julia 0.6.0 (34 Bytes)

So ziemlich eine Kopie dessen, was in R und Python 3 gemacht wurde

x->diff(sort(cumsum(vcat([0],x))))

Goysa
quelle

0

J 10 Bytes

/:~&.(+/\)

Erläuterung

"sort under scan sum": In J &.wendet die Under-Konjunktion die Transformation nach rechts auf die Eingabe an, wendet dann das Verb nach links an (in diesem Fall sort /:~) und führt dann die umgekehrte Transformation durch. Das heißt, J versteht es, eine Scan-Summe zu invertieren, und genau das ist hier erforderlich: Die aufeinanderfolgenden Differenzen sind die Eingaben, die bei einer Scan-Summierung diese Scan-Summe erzeugen.

Probieren Sie es online!

Jona
quelle

Sortieren Sie eine Differenzliste

Antworten:

05AB1E , 4 Bytes

Erläuterung

Python 3 mit Numpy , 56 54 53 Bytes

Mathematica, 40 Bytes

Gelee , 6 Bytes

Schale , 4 Bytes

Erklärung

Pyth , 9 Bytes

Pyth , 10 Bytes

JavaScript (ES6), 57 56 Bytes

Demo

Java 8, 123 Bytes

Ungolfed Lambda

Danksagung

Brachylog , 15 Bytes

R , 31 32 Bytes

Python 2 , 83 Bytes

Perl 6 , 46 Bytes

Erweitert:

Haskell , 74 Bytes

TI-Basic (TI-84 Plus CE), 23 Byte

C ++ (gcc) , 136 Bytes

Pyth, 8 Bytes

TI-Basic, 20 Bytes

Perl 5 , 87 + 1 (-a) = 88 Bytes

VB.NET (.NET 4.5), 109 Bytes

APL (Dyalog) , 15 14 Bytes

MATL , 6 Bytes

Gaia , 7 Bytes

Erläuterung

k , 16 Bytes

Japt , 10 Bytes

Röda , 42 Bytes

Julia 0.6.0 (34 Bytes)

J 10 Bytes

Erläuterung