23
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Are solutions guaranteed to be unique? \$\endgroup\$
    – H.PWiz
    Aug 11, 2017 at 16:23
  • \$\begingroup\$ @H.PWiz Yes they are. \$\endgroup\$
    – Wheat Wizard
    Aug 11, 2017 at 16:23
  • \$\begingroup\$ Related. \$\endgroup\$ Aug 11, 2017 at 16:48
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – CR Drost
    Aug 12, 2017 at 22:53
  • 1
    \$\begingroup\$ Could you add a few more test cases? I notice some solutions giving differing outputs for [-2, 100, -2, -1], for example. \$\endgroup\$
    – Shaggy
    Aug 14, 2017 at 10:14

29 Answers 29

16
\$\begingroup\$

05AB1E, 4 bytes

.¥{¥

Try it online!

Explanation

.¥{¥
.¥   # Undelta the input list
  {  # Sort it
   ¥ # And get the deltas
\$\endgroup\$
5
  • \$\begingroup\$ Undelta 05AB1E has the most niche built-ins. o0 \$\endgroup\$ Aug 11, 2017 at 16:30
  • 2
    \$\begingroup\$ Ahh crap, beat me to it. I've always wanted to use undelta. \$\endgroup\$ Aug 11, 2017 at 16:41
  • 16
    \$\begingroup\$ Undelta ಠ___ಠ \$\endgroup\$ Aug 11, 2017 at 16:41
  • 2
    \$\begingroup\$ "Undelta" is simply cumulative sum, right? \$\endgroup\$
    – Zgarb
    Aug 11, 2017 at 16:45
  • 3
    \$\begingroup\$ @Zgarb Undelta is adding a 0 as the first element of the list, then exactly as you've said, cumulative sum or reverse delta. \$\endgroup\$ Aug 11, 2017 at 16:45
9
\$\begingroup\$

Python 3 with Numpy, 56 54 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!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Mr. Xcoder
    Aug 11, 2017 at 17:36
  • \$\begingroup\$ @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) \$\endgroup\$
    – Luis Mendo
    Aug 11, 2017 at 17:59
  • \$\begingroup\$ Duty fulfilled! \$\endgroup\$
    – Mr. Xcoder
    Aug 12, 2017 at 12:44
  • \$\begingroup\$ -1 byte by moving the 0 into the cumsum. \$\endgroup\$
    – notjagan
    Aug 14, 2017 at 2:54
5
\$\begingroup\$

Mathematica, 40 bytes

Differences@Sort@Accumulate@Join[{1},#]&
\$\endgroup\$
1
  • \$\begingroup\$ Differences@Sort@FoldList[+##&,1,#]& \$\endgroup\$
    – alephalpha
    Aug 12, 2017 at 3:41
4
\$\begingroup\$

Jelly, 6 bytes

0;+\ṢI

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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

Pyth, 9 bytes

-1 byte thanks to @EriktheOutgolfer.

.+S+0sM._

Test Suite.

Pyth, 10 bytes

.+S.u+YNQ0

Try it online! or Try more test cases.

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

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

\$\endgroup\$
7
  • \$\begingroup\$ .sort((a,b)=>a-b) That's the way to get deltas? By sorting with subtraction? :P \$\endgroup\$ Aug 11, 2017 at 16:52
  • \$\begingroup\$ @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). \$\endgroup\$
    – Arnauld
    Aug 11, 2017 at 16:59
  • \$\begingroup\$ That -p+(p=n) grinds my gears, but sadly there's no better way... unless... \$\endgroup\$ Aug 11, 2017 at 17:10
  • \$\begingroup\$ what the heck, I didn't press the submit button >_< But anyway, I think you can save a byte with that edit... \$\endgroup\$ Aug 11, 2017 at 17:12
  • \$\begingroup\$ @ETHproductions Thanks :-) \$\endgroup\$
    – Arnauld
    Aug 11, 2017 at 17:26
3
\$\begingroup\$

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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ Aug 12, 2017 at 14:33
  • 1
    \$\begingroup\$ Thanks for my new title ;) Here's more decrement unholiness to celebrate for(;i>0;)l[i-1]=d[i]-d[--i]; (last loop) \$\endgroup\$ Aug 12, 2017 at 17:36
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jakob
    Aug 12, 2017 at 18:10
  • 2
    \$\begingroup\$ 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]);}. \$\endgroup\$
    – Nevay
    Aug 14, 2017 at 15:13
  • \$\begingroup\$ Ah yes, of course. Thanks! \$\endgroup\$
    – Jakob
    Aug 14, 2017 at 15:18
2
\$\begingroup\$

Brachylog, 15 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – JAD
    Aug 14, 2017 at 10:56
  • 1
    \$\begingroup\$ If you use diffinv rather than cumsum you don't need to prepend zero. \$\endgroup\$ Sep 14, 2017 at 13:37
  • \$\begingroup\$ @user2390246 wow, very nice! TIL about diffinv. \$\endgroup\$
    – Giuseppe
    Sep 14, 2017 at 13:39
  • \$\begingroup\$ Me too! I was just having a quick search to see if there were any previous answers I could have applied it to. \$\endgroup\$ Sep 14, 2017 at 13:40
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ It's not that terrible, in fact \$\endgroup\$
    – Mr. Xcoder
    Aug 11, 2017 at 16:41
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 19, 2017 at 1:46
1
\$\begingroup\$

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:«+»
    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)
}
\$\endgroup\$
1
\$\begingroup\$

Haskell, 74 bytes

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

Try it online!

Straightforward.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ =<< from the function monad comes in handy: (zipWith(-)=<<tail).sort.scanl(+)0 \$\endgroup\$
    – nimi
    Aug 11, 2017 at 18:08
  • \$\begingroup\$ @nimi Very nice. I'm not expert in monads, but I should have thought of zipWith. \$\endgroup\$
    – jferard
    Aug 11, 2017 at 18:43
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Do you need the L's? \$\endgroup\$
    – Adalynn
    Aug 12, 2017 at 22:04
  • \$\begingroup\$ @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 \$\endgroup\$ Aug 12, 2017 at 22:05
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ +1 This is a neat workaround with cumulative fixed point. I personally didn't even think of this. \$\endgroup\$
    – Mr. Xcoder
    Aug 12, 2017 at 7:34
1
\$\begingroup\$

TI-Basic, 20 bytes

cumSum(augment({0},Ans->L1
SortA(L1
ΔList(L1
\$\endgroup\$
1
\$\begingroup\$

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ Would you mind updating the TIO link? \$\endgroup\$ Aug 12, 2017 at 15:44
  • \$\begingroup\$ @TaylorScott Update in what way? \$\endgroup\$
    – Brian J
    Aug 13, 2017 at 19:21
  • \$\begingroup\$ Your TIO link shows completely different code than in your answer \$\endgroup\$ Aug 13, 2017 at 19:25
  • 1
    \$\begingroup\$ @TaylorScott Ahh....I see. I had to make some adjustments because TIO uses Mono, but I was using the .NET 4.5 compiler \$\endgroup\$
    – Brian J
    Aug 13, 2017 at 19:33
1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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,+\ \$\endgroup\$
    – ngn
    Sep 18, 2017 at 18:49
  • \$\begingroup\$ @ngn This part of the workshop was attempting to get the participants started with PPCG, so the rules here were those of PPCG. Thanks. \$\endgroup\$
    – Adám
    Sep 18, 2017 at 19:19
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 6 bytes

ÞRs¯0p

Try it Online!

\$\endgroup\$
0
\$\begingroup\$

Gaia, 7 bytes

1¤++⊣ȯọ

Try it online!

Explanation

1¤+      Prepend 1
   +⊣    Cumulative sums
     ȯ   Sort
      ọ  Deltas
\$\endgroup\$
0
\$\begingroup\$

k, 16 bytes

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

Try it online!

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

Japt, 10 bytes

iT å+ n än

Test it

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.