12
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

Pyth, 28 27 bytes

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Input given like:

3
[2, 10, 15]

Demonstration. Test harness.

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I never thought of using rF<seq> to unpack two-element tuples. \$\endgroup\$ – orlp Apr 22 '15 at 4:09
  • \$\begingroup\$ @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. \$\endgroup\$ – isaacg Apr 22 '15 at 4:14
  • \$\begingroup\$ You can shave off a character, you don't need the U. \$\endgroup\$ – orlp Apr 22 '15 at 4:31
  • \$\begingroup\$ @orlp Thanks. Actually, yvz fails when vz = 0, but hvz does the trick. \$\endgroup\$ – isaacg Apr 22 '15 at 4:36
  • \$\begingroup\$ 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. \$\endgroup\$ – randomra May 10 '15 at 10:04
8
\$\begingroup\$

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.

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

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.