Smoothing out a list

You should write a program or function which takes a non-negative integer k and a sorted integer list Las input and outputs or returns a smoothed list M.

M is created from the ascending list L by inserting at most k integer elements while keeping the list sorted. The inserted integers should be chosen in a way that the maximum forward difference of M will be as small as possible. We will call this smallest value "smoothness".

The forward differences of the list -1 3 8 11 15 are 4 5 3 4 and the maximum forward difference is 5.

With 2 insertions the smoothness of 2 10 15 is 4 and a possible output is 2 6 10 11 15 with forward differences 4 4 1 4.

Input

• A non-negative integer k.
• An ascending integer list L with at least 2 elements.

Output

• The ascending integer list M.
• If multiple correct answers exists output exactly one of them (any one is sufficient).
• Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).

Examples

Input (k, L) => A possible output and the maximum forward difference (which is not part of the output) in parentheses

0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)


This is code-golf so the shortest entry wins.

Pyth, 28 27 bytes

S+Qu?smt%hHrFdC,QtQ>GvzGhvz


Input given like:

3
[2, 10, 15]


Note: At the time the question was asked, there was a small bug in Pyth related to using rFd inside u, which I just fixed. The bug rendered it impossible to ever use F inside u, which was definitely not intended.

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Implicit:
z is the number of insertions, in string form.
Q is the input list.
C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
rFd                 d = (a, b) -> range(a, b)
%hH                    Take every H+1th element of that range
t                       And throw out the first one.
m                        Perform this process for each element pair
s                         And combine the results into one list.

The above is a minimal set of additional elements
To reduce the maximal difference to H+1.

u                     hvz    Repeat until the result stops changing, where
the prior result is G, H starts at 0 and
increases by 1 each repetition, and
G is initialized to eval(z)+1.
?               >GvzG       If not G[eval(z):], return G. In other words,
if the prior result was short enough, stop.
Also, this is always false on the initial call.
smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.


Here's a version which would have worked with the interpreter at the time the question was asked. It's 28 bytes, and works exactly the same way:

S+Qu?smt%hHr.udC,QtQ>GvzGhvz


Demonstration.

Git commit of the appropriate version, f6b40e62

• I never thought of using rF<seq> to unpack two-element tuples. – orlp Apr 22 '15 at 4:09
• @orlp It's a great trick, and I've used it way back in the day when u worked differently and e didn't exist, urGHd was shorter than rhd@d1. I'll put it on the Pyth tricks page. – isaacg Apr 22 '15 at 4:14
• You can shave off a character, you don't need the U. – orlp Apr 22 '15 at 4:31
• @orlp Thanks. Actually, yvz fails when vz = 0, but hvz does the trick. – isaacg Apr 22 '15 at 4:36
• As the code wouldn't work with the Pyth version which was available when the question was asked I chose not to accept this solution. If you give an answer which doesn't rely on the bugfix, ping me and I will accept it. – randomra May 10 '15 at 10:04

Python 2, 104

def f(L,k,d=1):
M=[];p=L[0]
for x in L:M+=range(p+d,x,d);p=x
return M[k:]and f(L,k,d+1)or sorted(L+M)


Tries different maximum increments d, starting from 1 and counting up. Fills in gaps of each pair (p,x) of successive elements by taking every d'th number in the gap. If M is longer than the quota allows, recurses to try a higher d. Otherwise, returns a list of the added and original elements, sorted.

This does all the test cases without delay on my machine.

• Did you try something like 1, 1000000000? – edc65 Apr 22 '15 at 5:30
• @edc65 That would take this algorithm really, really long, but I run of stack depth way before that. – xnor Apr 22 '15 at 5:39