22
\$\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\$
  • \$\begingroup\$ Are solutions guaranteed to be unique? \$\endgroup\$ – H.PWiz Aug 11 '17 at 16:23
  • \$\begingroup\$ @H.PWiz Yes they are. \$\endgroup\$ – Wheat Wizard Aug 11 '17 at 16:23
  • \$\begingroup\$ Related. \$\endgroup\$ – totallyhuman Aug 11 '17 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 '17 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 '17 at 10:14

27 Answers 27

16
\$\begingroup\$

05AB1E, 4 bytes

.¥{¥

Try it online!

Explanation

.¥{¥
.¥   # Undelta the input list
  {  # Sort it
   ¥ # And get the deltas
\$\endgroup\$
  • \$\begingroup\$ Undelta 05AB1E has the most niche built-ins. o0 \$\endgroup\$ – totallyhuman Aug 11 '17 at 16:30
  • 2
    \$\begingroup\$ Ahh crap, beat me to it. I've always wanted to use undelta. \$\endgroup\$ – Magic Octopus Urn Aug 11 '17 at 16:41
  • 16
    \$\begingroup\$ Undelta ಠ___ಠ \$\endgroup\$ – Business Cat Aug 11 '17 at 16:41
  • 1
    \$\begingroup\$ "Undelta" is simply cumulative sum, right? \$\endgroup\$ – Zgarb Aug 11 '17 at 16:45
  • 2
    \$\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\$ – Magic Octopus Urn Aug 11 '17 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\$
  • 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 '17 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 '17 at 17:59
  • \$\begingroup\$ Duty fulfilled! \$\endgroup\$ – Mr. Xcoder Aug 12 '17 at 12:44
  • \$\begingroup\$ -1 byte by moving the 0 into the cumsum. \$\endgroup\$ – notjagan Aug 14 '17 at 2:54
5
\$\begingroup\$

Mathematica, 40 bytes

Differences@Sort@Accumulate@Join[{1},#]&
\$\endgroup\$
  • \$\begingroup\$ Differences@Sort@FoldList[+##&,1,#]& \$\endgroup\$ – alephalpha Aug 12 '17 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\$
  • \$\begingroup\$ Another language that has undelta? Or some fancier built-in? \$\endgroup\$ – Mr. Xcoder Aug 11 '17 at 16:46
  • \$\begingroup\$ @Mr. Xcoder It happens that cumsum is the same as undelta \$\endgroup\$ – H.PWiz Aug 11 '17 at 16:46
  • \$\begingroup\$ @H.PWiz Actually that's not what we call cumsum...unless you take the empty prefix into account. \$\endgroup\$ – Erik the Outgolfer Aug 11 '17 at 16:48
  • \$\begingroup\$ @EriktheOutgolfer Yes, that is what husk does, as it is scanl(+)0 in Haskell. \$\endgroup\$ – H.PWiz Aug 11 '17 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\$
  • \$\begingroup\$ As in my (deleted) answer, you can use +0sM._ instead of .u+YNQ0 for -1. \$\endgroup\$ – Erik the Outgolfer Aug 11 '17 at 17:04
  • \$\begingroup\$ @EriktheOutgolfer Why did you delete it? \$\endgroup\$ – Mr. Xcoder Aug 11 '17 at 17:04
  • \$\begingroup\$ Thought the core idea was too similar to yours. \$\endgroup\$ – Erik the Outgolfer Aug 11 '17 at 17:05
  • \$\begingroup\$ @EriktheOutgolfer Ok, thanks then \$\endgroup\$ – Mr. Xcoder Aug 11 '17 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\$ – FryAmTheEggman Aug 11 '17 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\$
  • \$\begingroup\$ .sort((a,b)=>a-b) That's the way to get deltas? By sorting with subtraction? :P \$\endgroup\$ – totallyhuman Aug 11 '17 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 '17 at 16:59
  • \$\begingroup\$ That -p+(p=n) grinds my gears, but sadly there's no better way... unless... \$\endgroup\$ – ETHproductions Aug 11 '17 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\$ – ETHproductions Aug 11 '17 at 17:12
  • \$\begingroup\$ @ETHproductions Thanks :-) \$\endgroup\$ – Arnauld Aug 11 '17 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\$
  • 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\$ – Olivier Grégoire Aug 12 '17 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\$ – Olivier Grégoire Aug 12 '17 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 '17 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 '17 at 15:13
  • \$\begingroup\$ Ah yes, of course. Thanks! \$\endgroup\$ – Jakob Aug 14 '17 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\$
  • \$\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 '17 at 10:56
  • 1
    \$\begingroup\$ If you use diffinv rather than cumsum you don't need to prepend zero. \$\endgroup\$ – user2390246 Sep 14 '17 at 13:37
  • \$\begingroup\$ @user2390246 wow, very nice! TIL about diffinv. \$\endgroup\$ – Giuseppe Sep 14 '17 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\$ – user2390246 Sep 14 '17 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\$
  • \$\begingroup\$ It's not that terrible, in fact \$\endgroup\$ – Mr. Xcoder Aug 11 '17 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\$ – Jonathan Frech Sep 19 '17 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\$
  • 3
    \$\begingroup\$ =<< from the function monad comes in handy: (zipWith(-)=<<tail).sort.scanl(+)0 \$\endgroup\$ – nimi Aug 11 '17 at 18:08
  • \$\begingroup\$ @nimi Very nice. I'm not expert in monads, but I should have thought of zipWith. \$\endgroup\$ – jferard Aug 11 '17 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\$
  • \$\begingroup\$ Do you need the L's? \$\endgroup\$ – Zacharý Aug 12 '17 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\$ – pizzapants184 Aug 12 '17 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\$
  • \$\begingroup\$ +1 This is a neat workaround with cumulative fixed point. I personally didn't even think of this. \$\endgroup\$ – Mr. Xcoder Aug 12 '17 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\$
  • \$\begingroup\$ Would you mind updating the TIO link? \$\endgroup\$ – Taylor Scott Aug 12 '17 at 15:44
  • \$\begingroup\$ @TaylorScott Update in what way? \$\endgroup\$ – Brian J Aug 13 '17 at 19:21
  • \$\begingroup\$ Your TIO link shows completely different code than in your answer \$\endgroup\$ – Taylor Scott Aug 13 '17 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 '17 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\$
  • 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 '17 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 '17 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\$
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\$

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\$

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.