# Sort a difference list

The difference list of a list of integers is the list differences of consecutive members.

For example the difference list of

1, 3, 2 ,4


is

2, -1, 2


Your task is to take as input a difference list and output what the difference list would look like if the original list were sorted.

For example the difference list

2, 1, -2, -1


Might represent a list

2 4 5 3 2


Which when sorted is

2 2 3 4 5


Which has a difference list of

0 1 1 1


This is so answers will be scored in bytes with less bytes being better.

• Are solutions guaranteed to be unique? Commented Aug 11, 2017 at 16:23
• @H.PWiz Yes they are. Commented Aug 11, 2017 at 16:23
• Related. Commented Aug 11, 2017 at 16:48
• @H.PWiz Quick proof: a list is perfectly reconstructable from a difference list (DL) combined with a first element value, so there's a one-to-one conversion from L to (FV, DL). Increasing the FV by any amount is the same as adding that amount to every element of the L and therefore it cannot change the sorting of L if that comparison is suitably monotonic. (In other words, it doesn't affect sorting unless the number you're adding causes integer overflow). Commented Aug 12, 2017 at 22:53
• Could you add a few more test cases? I notice some solutions giving differing outputs for [-2, 100, -2, -1], for example. Commented Aug 14, 2017 at 10:14

# 05AB1E, 4 bytes

.¥{¥


Try it online!

### Explanation

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

• Undelta 05AB1E has the most niche built-ins. o0 Commented Aug 11, 2017 at 16:30
• Ahh crap, beat me to it. I've always wanted to use undelta. Commented Aug 11, 2017 at 16:41
• Undelta ಠ___ಠ Commented Aug 11, 2017 at 16:41
• "Undelta" is simply cumulative sum, right? Commented Aug 11, 2017 at 16:45
• @Zgarb Undelta is adding a 0 as the first element of the list, then exactly as you've said, cumulative sum or reverse delta. Commented Aug 11, 2017 at 16:45

# Python 3 with Numpy, 5654 53 bytes

2 bytes off thanks to @Artyer (Numpy's sort instead of standard sorted). 1 byte off thanks to @notjagan (moving 0 into cumsum)

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


The code defines an anonymous function that inputs a list or a Numpy array and outputs a Numpy array.

Try it online!

• Woah, you taught me something new today. My approach with numpy was much longer. I'll come back tomorrow to upvote this, because I see you capped already. Very nice! Commented Aug 11, 2017 at 17:36
• @Mr.Xcoder Thanks! I'm no expert in Numpy, I just followed what I'd have done in Matlab: diff(sort([0 cumsum(x)])) (in Matlab,[ ] is concatenation) Commented Aug 11, 2017 at 17:59
• Duty fulfilled! Commented Aug 12, 2017 at 12:44
• -1 byte by moving the 0 into the cumsum. Commented Aug 14, 2017 at 2:54

# Mathematica, 40 bytes

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

• Differences@Sort@FoldList[+##&,1,#]& Commented Aug 12, 2017 at 3:41

# Jelly, 6 bytes

0;+\ṢI


Try it online!

# Husk, 4 bytes

Ẋ-O∫


Try it online!

### Explaination

      -- 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]

• Another language that has undelta? Or some fancier built-in? Commented Aug 11, 2017 at 16:46
• @Mr. Xcoder It happens that cumsum is the same as undelta Commented Aug 11, 2017 at 16:46
• @H.PWiz Actually that's not what we call cumsum...unless you take the empty prefix into account. Commented Aug 11, 2017 at 16:48
• @EriktheOutgolfer Yes, that is what husk does, as it is scanl(+)0 in Haskell. Commented Aug 11, 2017 at 16:51

# Pyth, 9 bytes

-1 byte thanks to @EriktheOutgolfer.

.+S+0sM._


Test Suite.

# Pyth, 10 bytes

.+S.u+YNQ0

• As in my (deleted) answer, you can use +0sM._ instead of .u+YNQ0 for -1. Commented Aug 11, 2017 at 17:04
• @EriktheOutgolfer Why did you delete it? Commented Aug 11, 2017 at 17:04
• Thought the core idea was too similar to yours. Commented Aug 11, 2017 at 17:05
• @EriktheOutgolfer Ok, thanks then Commented Aug 11, 2017 at 17:05
• m=+Z is a same length variant for sM._, but sadly it doesn't seem like it can be any shorter. Commented Aug 11, 2017 at 17:24

## JavaScript (ES6), 57 56 bytes

Saved 1 byte thanks to @ETHproductions

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


### Demo

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])))

• .sort((a,b)=>a-b) That's the way to get deltas? By sorting with subtraction? :P Commented Aug 11, 2017 at 16:52
• @totallyhuman The first map() gives the deltas. This code sorts them. The 2nd map rebuild the new deltas. The JS sort() method uses lexicographical order by default. So, we need this specialized callback for numbers > 9 (sadly). Commented Aug 11, 2017 at 16:59
• That -p+(p=n) grinds my gears, but sadly there's no better way... unless... Commented Aug 11, 2017 at 17:10
• what the heck, I didn't press the submit button >_< But anyway, I think you can save a byte with that edit... Commented Aug 11, 2017 at 17:12
• @ETHproductions Thanks :-) Commented Aug 11, 2017 at 17:26

# Java 8, 123 bytes

The standard solution: cumulative sum input, sort, then diff. No substantial implementation tricks either.

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


Cast to Consumer<int[]>. Output is mutated input.

Try It 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];
}


## Acknowledgments

• -3 bytes thanks to Olivier Grégoire, master of unholy autoincrementation
• -1 byte thanks to Nevay
• You can golf 3 bytes by rearranging the positions where you do your increments and your overall computations: 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];} (beware SE's invisible characters when copy/pasting) Commented Aug 12, 2017 at 14:33
• Thanks for my new title ;) Here's more decrement unholiness to celebrate for(;i>0;)l[i-1]=d[i]-d[--i]; (last loop) Commented Aug 12, 2017 at 17:36
• I had just reworked that loop myself, arriving at for(;i-->0;)l[i]=d[i+1]-d[i]; of the same length. Update to come. Commented Aug 12, 2017 at 18:10
• You can save 1 byte by using 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]);}. Commented Aug 14, 2017 at 15:13
• Ah yes, of course. Thanks! Commented Aug 14, 2017 at 15:18

# Brachylog, 15 bytes

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


Try it online!

# R, 31 32 bytes

-4 bytes thanks to @user2390246 for diffinv

+5 bytes from Jarko for cat

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


Reads from stdin, writes to stdout. diffinv is an inverse of diff for a given starting value (0 by default). Since it's diffed again, it doesn't matter what that value is.

As pointed out by Jarko Dubbeldam, I needed to properly output the result, at the cost of five bytes. Alas.

Try it online!

• That's what I had in mind as well. Does need to handle printing though, as running this as a full program (through source) this doesn't output anything.
Commented Aug 14, 2017 at 10:56
• If you use diffinv rather than cumsum you don't need to prepend zero. Commented Sep 14, 2017 at 13:37
• @user2390246 wow, very nice! TIL about diffinv. Commented Sep 14, 2017 at 13:39
• Me too! I was just having a quick search to see if there were any previous answers I could have applied it to. Commented Sep 14, 2017 at 13:40

# 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:])]


Try it online!

Horrible solution.

• It's not that terrible, in fact Commented Aug 11, 2017 at 16:41
• Python's += operator on lists works with any iterable, so you can use r+=r[-1]+i, instead of r+=[r[-1]+i] and save one byte. Commented Sep 19, 2017 at 1:46

# Perl 6, 46 bytes

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


Try it

## Expanded:

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

[\+](         # triangle reduce using &infix:«+»
|@_         # 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)
}


import Data.List
g=sort.scanl(+)0
h l|k<-g l=map($$x,y)->x-y)zip(tailk)k  Try it online! Straightforward. • =<< from the function monad comes in handy: (zipWith(-)=<<tail).sort.scanl(+)0 – nimi Commented Aug 11, 2017 at 18:08 • @nimi Very nice. I'm not expert in monads, but I should have thought of zipWith. Commented Aug 11, 2017 at 18:43 # TI-Basic (TI-84 Plus CE), 23 bytes Prompt X augment({0},cumSum(LX→X SortA(LX ΔList(LX  Prompts for user input. The list must be input with a leading {, with numbers separated by ,, and with an optional trailing }. TI-Basic is a tokenized language; ΔList( and cumSum( are two-byte tokens, all other tokens used are one byte each. Example run (with NAME as the program name and {4,-2,7,-4,0} as the input): prgmNAME X=?{4,-2,7,-4,0} {2 2 1 0 4}  Explanation: 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  • Do you need the L's? Commented Aug 12, 2017 at 22:04 • @Zacharý you can omit them when storing a list, but omitting them when referencing would refer to the numerical variable X instead of the list Commented Aug 12, 2017 at 22:05 # C++ (gcc), 136 bytes As unnamed generic lambda, assuming input to be like std::list and returning via reference parameter. [](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);}  Try it 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 }  # 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  • +1 This is a neat workaround with cumulative fixed point. I personally didn't even think of this. Commented Aug 12, 2017 at 7:34 # TI-Basic, 20 bytes cumSum(augment({0},Ans->L1 SortA(L1 ΔList(L1  # Perl 5, 87 + 1 (-a) = 88 bytes a[0]=1;push@a,a[-1]+_ for@F;@a=sort{a<=>b}@a;printa[0]-_,"while(_=shift@a)&&@a  Try it online! # 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  A function that expects a list as input and modifies it directly. The original parameter can then be used for output 1. Recreates an original list by adding forwards through the list (assumes an implicit 0 as the first element) 2. Sorts the original list 3. Gets the differences by going backwards (so I don't need to keep track of a different list) (the implicit first element of 0 means the first difference is the same as the smallest element) Try it online! • Would you mind updating the TIO link? Commented Aug 12, 2017 at 15:44 • @TaylorScott Update in what way? Commented Aug 13, 2017 at 19:21 • Your TIO link shows completely different code than in your answer Commented Aug 13, 2017 at 19:25 • @TaylorScott Ahh....I see. I had to make some adjustments because TIO uses Mono, but I was using the .NET 4.5 compiler Commented Aug 13, 2017 at 19:33 # APL (Dyalog), 15 14 bytes -1 byte thanks to ngn. (¯2-/⍋⊃¨⊂)0,+\  +\ cumulative sum 0, prepend a zero () apply the following tacit function on that: ⊂ enclose (so we can pick multiple items) ⍋⊃¨ let each of the indices that would sort the argument pick from that ¯2-/ reversed pairwise difference Try it online! Original solution found by the Code Golf Hackathon participants at the Dyalog '17 User Meeting: ¯2-/l[⍋l←+\0,⎕]  Try it online! ⎕ prompt for input 0, prepend a zero +\ cumulative sum l← store as l ⍋ find the indices that will sort l l[] use that to index into l ¯2-/ reversed pairwise difference • I don't know if this was allowed at the hackathon but if you rewrite it in point-free style you could save a char: (¯2-/⍋⊃¨⊂)0,+\ – ngn Commented Sep 18, 2017 at 18:49 • @ngn This part of the workshop was attempting to get the participants started with PPCG, so the rules here were those of PPCG. Thanks. – Adám Commented Sep 18, 2017 at 19:19 # MATL, 6 bytes 0hYsSd  Try it online! 0 # push 0 h # horizontal concatenate with implicit input Ys # cumulative sum S # sort d # diff (implicit output)  # J, 10 bytes /:~&.(+/$$


# explanation

"sort under scan sum": In J, the Under conjunction &. applies the transformation to its right to the input, then applies the verb to its left (in this case sort /:~) and then does the reverse transformation. That is, J understands how to invert a scan sum, which is exactly what's needed here: the successive differences are the input that, when scan-summed, will produce that scan-sum.

Try it online!

# Vyxal, 6 bytes

ÞRs¯0p


Try it Online!

# Gaia, 7 bytes

1¤++⊣ȯọ


Try it online!

### Explanation

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


# k, 16 bytes

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


Try it online!

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


# Japt, 10 bytes

iT å+ n än


Test it

# Röda, 42 bytes

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


Try it online!

This is similar to the Perl 6 answer. .sort is |sort, .rotor(2=>-1).flat is |slide 2 and .map(*R-*) is |[_2-_1].

Explanation:

{
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 */
}


The statement [i]if i+=_ is equivalent to

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


The += operator does not push values to the stream, so it is truthy. I could also have used some kind of block (eg. {|j|i+=j;[i]}_) to tie the addition and pushing statements together, but if is shorter.

## Julia 0.6.0 (34 bytes)

Pretty much a copy of what has been done in R and Python 3

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

# Factor, 45 bytes

[ 0 prefix cum-sum natural-sort differences ]


Try it online!

Add a 0 to the start of the input, cumulative sum, sort, differences.