Sort and Re-apply Deltas of an Array

Question

It seems that any Simple Modification of deltas using a consistent function can almost always be done some other shorter way, Dennis. Thus, the only solution I can imagine to make this harder, is to introduce some sort of inconsistent function.

Sorting.

Your task is to take an array of integers, sort their deltas, and recompile that to give the new array of integers.

EG.

For the input:

1  5 -3  2  9

Get the following Deltas:

  4 -8  5  7

Then, sort these Deltas, Yielding:

 -8  4  5  7

And reapply them, which gives:

1 -7 -3  2  9

Input/Output

You will be given a list/array/table/tuple/stack/etc. of signed integers as input through any standard input method.

You must output the modified data once again in any acceptable form, following the above delta sorting method.

You will receive N inputs where 0 < N < 10 where each number falls within the range -1000 < X < 1000

Test Cases

1 5 -3 2 9   -> 1 -7 -3 2 9
-5 -1 -6 5 8 -> -5 -10 -7 -3 8
-8 1 -7 1 1  -> -8 -16 -16 -8 1
8 -9 3 0 -2  -> 8 -9 -12 -14 -2
-5 -2 -5 5 0 -> -5 -10 -13 -10 0
-1 9 -1 -7 9 -> -1 -11 -17 -7 9

Notes

As stated in above, you will always receive at least 1 input, and no more than 9.
The first and last number of your output, will always match that of the input.
Only Standard Input Output is accepted
Standard loopholes apply
This is code-golf, so the lowest byte-count wins!
Have fun!

IMO you should remove the second header (the one in the body of the post itself). It's kinda ugly and just takes up space, and it's a copy of the title (which is like 20 px above it). — Riker, Mar 29, 2017 at 0:10

Luis Mendo · Accepted Answer · 2017-03-28 23:46:55Z

5

MATL, 8 bytes

1)GdShYs

Try it online!

1)   % Implicit input. Get its first entry
G    % Push input again
d    % Differences
S    % Sort
h    % Concatenate
Ys   % Cumulative sum. Implicit display

answered Mar 28, 2017 at 23:46

Luis Mendo

104k9 gold badges132 silver badges365 bronze badges

Add a comment |

Dennis · Accepted Answer · 2017-03-29 04:14:30Z

4

Jelly, 7 bytes

IṢ;@Ḣ+\

Try it online!

How it works

IṢ;@Ḣ+\  Main link. Argument: A (array)

I        Increments; compute the deltas.
 Ṣ       Sort them.
    Ḣ    Head; pop and yield the first element of A.
  ;@     Concatenate with swapped arguments.
     +\  Take the cumulative sum.

answered Mar 29, 2017 at 4:14

Dennis

210k41 gold badges368 silver badges819 bronze badges

Add a comment |

Greg Martin · Accepted Answer · 2017-03-29 00:26:13Z

Mathematica, 40 bytes

FoldList[Plus,#&@@#,Sort@Differences@#]&

Pure function taking a list of (anythings) as input and returning a list. FoldList[Plus starts with a number (in this case, #&@@#, the first element of the input) and repeatedly adds elements of the self-explanatory list Sort@Differences@#. This mimics the behavior of the built-in Accumulate, but the first number would need to be prepended to the list of differences by hand, which makes the byte-count higher (as far as I can tell).

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

05AB1E, 9 bytes

-4 thanks to Emigna

¬=s¥{vy+=

Try it online!

¬         # Get the head
 =        # Print
  s¥{     # Get sorted Deltas
     vy   # For each
       += # Add to the previous value and print

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 29, 2017 at 2:04

Riley

11.7k1 gold badge21 silver badges53 bronze badges

\$\begingroup\$ You could save 4 bytes with ¬=s¥{vy+= \$\endgroup\$
– Emigna
Mar 29, 2017 at 7:05

Add a comment |

orlp · Accepted Answer · 2017-03-29 00:52:10Z

2

Python 2, 92 bytes

l=input();p=0;d=[]
r=l[0],
for e in l:d+=e-p,;p=e
for e in sorted(d[1:]):r+=r[-1]+e,
print r

answered Mar 29, 2017 at 0:52

orlp

39k7 gold badges78 silver badges194 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Haskell, 59 Bytes

import Data.List
f l@(a:b)=scanl1(+)$a:(sort$zipWith(-)b l)

Breakdown:

f l@(a:b) =           --we create a function f that takes as input a list l with head a and tail b
zipWith(-)b l        --we make a new list with the deltas
sort$                    --sort it
a:                          --prepend a to the list
scanl1(+)$          --create a new list starting with a and adding the deltas to it cumulatively

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 29, 2017 at 0:13

Generic Display Name

3551 silver badge8 bronze badges

2

\$\begingroup\$ scanl(+)a$sort... \$\endgroup\$
– nimi
Mar 29, 2017 at 5:05

Add a comment |

Community · Accepted Answer · 2017-04-13 12:39:16Z

2

JavaScript (ES6), 68 bytes

([p,...a])=>[s=p,...a.map(e=>p-(p=e)).sort((a,b)=>b-a).map(e=>s-=e)]

In JavaScript it turns out to be golfier to compute the Inverse Deltas of an Array. These are then sorted in descending order and cumulatively subtracted from the first element.

edited Apr 13, 2017 at 12:39

CommunityBot

1

answered Mar 29, 2017 at 8:50

Neil

166k12 gold badges69 silver badges273 bronze badges

Add a comment |

Keerthana Prabhakaran · Accepted Answer · 2017-03-30 04:01:30Z

2

Python 2,

90 bytes

~~x=input() print[sum(sorted(map(int.__sub__,x[1:],x[:-1]))[:i])+x[0]for i in range(len(x))]~~

84 bytes

Saved 6 bytes on using lambda. Thanks to ovs!

lambda x:[sum(sorted(map(int.__sub__,x[1:],x[:-1]))[:i])+x[0]for i in range(len(x))]

Try it online!

Breaking down the code,

>>> x
[1, 5, -3, 2, 9]
>>> map(int.__sub__,x[1:],x[:-1]) #delta
[4, -8, 5, 7]
>>> sorted(map(int.__sub__,x[1:],x[:-1])) #sorted result
[-8, 4, 5, 7]
>>> [sorted(map(int.__sub__,x[1:],x[:-1]))[:i]for i in range(len(x))]
[[], [-8], [-8, 4], [-8, 4, 5], [-8, 4, 5, 7]]
>>> [sum(sorted(map(int.__sub__,x[1:],x[:-1]))[:i])+x[0]for i in range(len(x))]
[1, -7, -3, 2, 9]

Happy Coding!

edited Mar 30, 2017 at 4:01

answered Mar 29, 2017 at 7:48

Keerthana Prabhakaran

7393 silver badges9 bronze badges

\$\begingroup\$ i was trying to find a way to do it like that! \$\endgroup\$
– quintopia
Mar 29, 2017 at 8:01
1

\$\begingroup\$ You can save some bytes by converting this into a function: lambda x:[sum(sorted(map(int.__sub__,x[1:],x[:-1]))[:i])+x[0]for i in range(len(x))] \$\endgroup\$
– ovs
Mar 29, 2017 at 9:31

Add a comment |

Razetime · Accepted Answer · 2021-02-21 06:11:04Z

2

Husk, 7 bytes

∫:←¹OẊ-

Try it online!

answered Feb 21, 2021 at 6:11

Razetime

27k3 gold badges26 silver badges71 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

JavaScript (ES6), 93 bytes

(p,M=[p[0]])=>p.map((a,b)=>p[b+1]-a).sort((a,b)=>a-b).map((a,b)=>M=[...M,M[b]+a])[p.length-2]

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 29, 2017 at 0:43

R. Kap

4,9182 gold badges14 silver badges37 bronze badges

Add a comment |

Rod · Accepted Answer · 2017-03-29 01:45:20Z

1

Python 2, 97 bytes

p=input()
d=[p[i+1]-p[i] for i in range(len(p)-1)]
o=p[:1]
for n in sorted(d):o+=o[-1]+n,
print o

Try it online!

edited Mar 29, 2017 at 1:45

Rod

18.4k4 gold badges30 silver badges89 bronze badges

answered Mar 29, 2017 at 0:04

user67482

\$\begingroup\$ You can delete a space in the list comprehension for 96 bytes: [p[i+1]-p[i]for i in range(len(p)-1)] \$\endgroup\$
– sagiksp
Mar 30, 2017 at 7:05

Add a comment |

quintopia · Accepted Answer · 2017-03-29 04:25:16Z

1

Pyth, 11 bytes

.u+NYS.+QhQ

This just does the obvious thing described in the statement.

Try It Online

      .+Q    Take the deltas of the input
     S       sort it
.u           Cumulative reduce
  +NY        using addition
         hQ  starting with the first element of the input

Suggestions for further golfing welcome.

answered Mar 29, 2017 at 4:25

quintopia

4,08720 silver badges35 bronze badges

Add a comment |

Dennis · Accepted Answer · 2017-03-29 06:40:43Z

1

Julia 0.5, 30 bytes

!x=[x[];x|>diff|>sort]|>cumsum

Try it online!

answered Mar 29, 2017 at 6:40

Dennis

210k41 gold badges368 silver badges819 bronze badges

Add a comment |

aross · Accepted Answer · 2017-03-29 14:12:14Z

PHP, 89 bytes

for($a=$argv;n|$i=$a[++$x+1];)$d[]=$i-$a[$x];for(sort($d);$x-$y++;)echo$a[1]+=$d[$y-2],_;

Run like this:

php -nr 'for($a=$argv;n|$i=$a[++$x+1];)$d[]=$i-$a[$x];for(sort($d);$x-$y++;)echo$a[1]+=$d[$y-2],",";' 1  5 -3  2  9;echo
> 1_-7_-3_2_9_

Explanation

for(
  $a=$argv;          # Set input to $a.
  n | $i=$a[++$x+1]; # Iterate over input.
)
  $d[] = $i-$a[$x];  # Add an item to array $d, with the difference between
                       the current and previous item.

for(
  sort($d);          # Sort the delta array.
  $x-$y++;           # Loop as many times as the previous loop.
)
  echo
    $a[1]+=$d[$y-2], # Print the first input item with the delta applied
                     # cumulatively. First iteration takes $d[-1], which
                     # is unset, so results in 0.
    _;               # Print underscore as separator.

quintopia · Accepted Answer · 2017-03-29 17:21:54Z

1

Python 2 with numpy, 67 56 bytes

from numpy import*
lambda l:cumsum(l[:1]+sorted(diff(l)))

Let numpy compute the deltas, sort them, prepend the first element, and let numpy compute the cumulative sums. Pretty cheap?

edited Mar 29, 2017 at 17:21

answered Mar 29, 2017 at 8:17

quintopia

4,08720 silver badges35 bronze badges

1

\$\begingroup\$ Save 3 bytes by changing the import to from numpy import* and n.cumsum to cumsum and n.diff to diff \$\endgroup\$
– ovs
Mar 29, 2017 at 9:37
\$\begingroup\$ Thanks. You can tell its been a while since I golfed python, forgetting all the standard tricks. \$\endgroup\$
– quintopia
Mar 29, 2017 at 17:22

Add a comment |

FlipTack · Accepted Answer · 2022-10-22 15:14:29Z

1

Pushy, 17 bytes

@ZL:&v+;Fg@Lt:K-#

Try it online!

@ZL:&v+;F           \ Calculate cumulative sum
         g          \ Sort
          @Lt:K-#   \ Calculate and print deltas

answered Oct 22, 2022 at 15:14

FlipTack

14.6k3 gold badges53 silver badges101 bronze badges

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2017-03-29 02:57:41Z

Perl 6, 31 bytes

{[\+] @_[0],|sort @_[1..*]Z-@_}

Try it

Expanded:

{
  [\+]            # triangle produce values using &infix<+>
    @_[0],        # starting with the first argument
    |             # slip the following into this list
      sort        # sort the following

         # generate the list of deltas

         @_[1..*] # the arguments starting with the second one
         Z[-]     # zipped using &infix:<->
         @_       # the arguments
}

Neil · Accepted Answer · 2017-03-29 09:10:42Z

0

Batch, 197 bytes

@set n=%1
@set s=
:l
@set/ad=5000+%2-%1
@set s=%s% %d%
@shift
@if not "%2"=="" goto l
@echo %n%
@for /f %%a in ('"(for %%b in (%s%)do @echo %%b)|sort"') do @set/an+=%%a-5000&call echo %%n%%

sort doesn't sort numerically, so I bias all the differences by 5000.

answered Mar 29, 2017 at 9:10

Neil

166k12 gold badges69 silver badges273 bronze badges

Add a comment |

Neil · Accepted Answer · 2017-03-29 09:37:08Z

0

bash + sort, 102 bytes

echo $1
n=$1
shift
for e in $*
do
echo $((e-n))
n=$e
done|sort -n|while read e
do
echo $((n+=e))
done

sh + sort + expr, 106 bytes

echo $1
n=$1
shift
for e in $*
do
expr $e - $n
n=$e
done|sort -n|while read e
do
n="$n + $e"
expr $n
done

answered Mar 29, 2017 at 9:37

Neil

166k12 gold badges69 silver badges273 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2017-03-29 13:19:41Z

0

Clojure, 46 bytes

#(reductions +(first %)(sort(map -(rest %)%)))

One day I'm going to make Cljr language which has shorter function names than Clojure.

answered Mar 29, 2017 at 13:19

NikoNyrh

2,6319 silver badges8 bronze badges

Add a comment |

Stack Exchange Network

Sort and Re-apply Deltas of an Array

EG.

Input/Output

Test Cases

Notes

20 Answers 20

MATL, 8 bytes

Jelly, 7 bytes

How it works

Mathematica, 40 bytes

05AB1E, 9 bytes

Python 2, 92 bytes

Haskell, 59 Bytes

JavaScript (ES6), 68 bytes

Python 2,

90 bytes

84 bytes

Husk, 7 bytes

JavaScript (ES6), 93 bytes

Python 2, 97 bytes

Pyth, 11 bytes

Julia 0.5, 30 bytes

PHP, 89 bytes

Explanation

Python 2 with numpy, 67 56 bytes

Pushy, 17 bytes

Perl 6, 31 bytes

Expanded:

Batch, 197 bytes

bash + sort, 102 bytes

sh + sort + expr, 106 bytes

Clojure, 46 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
integer
or ask your own question.

Linked

Hot Network Questions

Sort and Re-apply Deltas of an Array

EG.

Input/Output

Test Cases

Notes

20 Answers 20

MATL, 8 bytes

Jelly, 7 bytes

How it works

Mathematica, 40 bytes

05AB1E, 9 bytes

Python 2, 92 bytes

Haskell, 59 Bytes

JavaScript (ES6), 68 bytes

Python 2,

90 bytes

84 bytes

Husk, 7 bytes

JavaScript (ES6), 93 bytes

Python 2, 97 bytes

Pyth, 11 bytes

Julia 0.5, 30 bytes

PHP, 89 bytes

Explanation

Python 2 with numpy, 67 56 bytes

Pushy, 17 bytes

Perl 6, 31 bytes

Expanded:

Batch, 197 bytes

bash + sort, 102 bytes

sh + sort + expr, 106 bytes

Clojure, 46 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
integer
or ask your own question.