20
\$\begingroup\$

Objective

Generate the original scrambled list, from the movements that an Insertion Sort would do to sort it. The original list will have all numbers from 0 to N-1(inclusive) where N is the size of the input.

Input

A list containing the necessary moves to sort the list. Each value represents the amount of slots displaced by the original (scrambled) number to be in his right position , keep in mind that this process is from the left to the right.
The value at (0-indexed) position i in the input list will be between 0 and i inclusive.
You don't need to handle invalid inputs, any behaviour is acceptable in this case (crash, infinite loop, etc).

Output

The scrambled list

Step-by-step to generate the moves

Scrambled List | Moves to sort
[4,0,2,1,3,5]  | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5]  | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5]  | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5]  | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5]  | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5]  | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]

So, for the input [0,1,1,2,1,0] your program need to output [4,0,2,1,3,5].
Keep in mind that the movements aren't to the position in the (final) sorted list, but in the sorted segment(the bolded section)

Test Cases

[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]

Winning

This is , so the shortest answer wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ May the program also take the length of the list as input? \$\endgroup\$ – mbomb007 Feb 17 '17 at 19:18
  • \$\begingroup\$ @mbomb007 nope. \$\endgroup\$ – Rod Feb 17 '17 at 20:40
  • \$\begingroup\$ Can we use (n-1) steps instead? The first one is unnecessary, since it's always zero. \$\endgroup\$ – G B Feb 21 '17 at 10:50
  • \$\begingroup\$ @GB sure, as long the output is right, you can use any algorithm \$\endgroup\$ – Rod Feb 21 '17 at 11:03
14
\$\begingroup\$

Jelly, 12 bytes

L!_UÆ¡$œ?J’U

Try it online!

Explanation

We can basically see the two lists (the input and the output) as encoding an integer; the input encodes an integer in factorial base, and the output encodes an integer as a permutation. Luckily, Jelly has builtins that are already very close to both of these encodings, so it's simply a matter of writing small pieces of code to convert to an integer, then back to the other encoding.

L!_UÆ¡$œ?J’U
   U           Reverse {the input}
    Æ¡         and convert from base factorial to integer;
  _   $        subtract that from
L!             the factorial of the length of {the input};
       œ?      then take the nth permutation of
         J     [1,2,...,l], where l is the length of {the input},
          ’    subtract 1 from every elevent,
           U   and reverse it

In the case of base factorial, we can observe that the first element of the list must be 0, the second can be 0 or 1, the third must be 0/1/2, and so on. Thus, we have to reverse the input in order to get its elements into the normal writing order for base conversion.

Additionally, for the relative orders of the factorial conversion and the permutation conversion to match up with the operation that insertion sort uses, we need to make two adjustments: reversing the sequence of the permutations, and reversing the order of the output list. Reversing the output list is easy enough, needing only a U at the end of the program. To reverse the sequence of permutations, we subtract from the factorial of the input length (this works because the base factorial produces a number in the range 0 to (length!-1), whereas the permutations are numbered by Jelly from 1 to length!, producing an implicit off-by-one that cancels out the off-by-one that you normally get when subtracting a permutation index from a factorial).

Jelly, 9 bytes, in collaboration with @JonathanAllan

UÆ¡Nœ?J’U

This version of the program is very similar, but uses a different method of reversing the sequence of permutations; simply negating the input with N is enough to make œ? treat the order in reverse. Apart from that, it works identically to the previous program.

Try it online!

| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ O_O What sorcery is this? \$\endgroup\$ – DLosc Feb 17 '17 at 19:43
  • \$\begingroup\$ Oh nice - I knew my Æ¡ and œ? atoms would work for this (I had already started trying to use them for this challenge earlier - I was so close, just needed the L! in there). \$\endgroup\$ – Jonathan Allan Feb 17 '17 at 19:55
  • \$\begingroup\$ Excellent code! \$\endgroup\$ – Greg Martin Feb 17 '17 at 22:23
  • 1
    \$\begingroup\$ In fact, you can do it in 9 bytes with UÆ¡Nœ?L’U because I implemented œ? (and similar) to act modularly (as if they were using Jelly lists). The N just indexes in with the negative value. Note: I changed J to L - this is just because given a number it makes a range under-the-hood anyway). \$\endgroup\$ – Jonathan Allan Feb 19 '17 at 0:35
6
\$\begingroup\$

Mathematica, 92 bytes

Permute[Range[l=Length@#]-1,(c=Cycles@{#}&)@{}©##&@@c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]&

Pure function taking a list of nonnegative integers as input and returning a list of nonnegative integers. The above code contains a ©, which is incorrect: it's a placeholder for the 3-byte symbol U+F3DE, which Mathematica represents by a circle with a dot in it, and which represents composition of permutations.

c=Cycles@{#}& defines a function that converts a list of integers into a Cycles object representing a permutation; for example, c[{3,4}] is the transposition swapping elements 3 and 4 of a list. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}] takes the input list and generates the permutations necessary to undo the insertion sort. Then c@{}©##&@@ composes all of these permutations together, starting with the identity permutation c@{}. Finally, Permute[Range[l=Length@#]-1,...] applies this permutation to the 0-indexed list of appropriate length.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ What no built-in?! Surely... \$\endgroup\$ – Jonathan Allan Feb 17 '17 at 21:19
  • 3
    \$\begingroup\$ @{#}&)@{}©##&@@ looks scary. \$\endgroup\$ – Yytsi Feb 18 '17 at 6:49
6
\$\begingroup\$

Python 2, 79 68 bytes

Thanks to Krazor for saving 10 bytes

Thanks to TuukkaX for saving 1 byte

a=input();b=range(len(a));print[b.pop(j-a[j])for j in b[::-1]][::-1]

Works by generating the moves in reverse

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Make that 66! How about: a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. List comprehensions ftw! \$\endgroup\$ – FMaz Feb 18 '17 at 13:23
  • 1
    \$\begingroup\$ @Krazor You have a space that could be removed before for, so make that 65 I guess :D \$\endgroup\$ – Yytsi Feb 18 '17 at 15:28
  • \$\begingroup\$ @Krazor Turns out the list comprehension didn't quite work, but I liked the idea of using b[::-1] ! \$\endgroup\$ – math junkie Feb 18 '17 at 18:01
  • \$\begingroup\$ No way? I commented with mobile, maybe I mistyped something. Which part does not work? For me, it interpreted correctly and fulfilled all test cases. \$\endgroup\$ – FMaz Feb 18 '17 at 18:27
  • \$\begingroup\$ @Krazor Oh whoops, no you're right. I'm the one who mistyped it while testing. \$\endgroup\$ – math junkie Feb 18 '17 at 18:35
5
\$\begingroup\$

JavaScript (ES6), 69 65 63 bytes

a=>a.reverse(b=[...a.keys()]).map(o=>+b.splice(~o,1)).reverse()

Annoyingly both input and output are in the wrong order. Edit: Saved 4 bytes thanks to @Arnauld. Saved 2 bytes thanks to @ETHproductions.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I was still trying to find a better way but you were much faster. Nice one! \$\endgroup\$ – Arnauld Feb 17 '17 at 23:46
  • 1
    \$\begingroup\$ You don't need i, do you? \$\endgroup\$ – Arnauld Feb 17 '17 at 23:52
  • \$\begingroup\$ @Arnauld Apparently not. I started by trying to understand the Python answer, and I've only just noticed that it doesn't actually use i... \$\endgroup\$ – Neil Feb 18 '17 at 0:33
  • 1
    \$\begingroup\$ Easy -2: o=>+b.splice(~o,1) \$\endgroup\$ – ETHproductions Feb 18 '17 at 2:53
3
\$\begingroup\$

JavaScript (ES6), 73 71 bytes

Saved 2 bytes thanks to ETHproductions

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

Test cases

let f =

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

console.log(JSON.stringify(f([0,0,0])));       // -> [0,1,2]
console.log(JSON.stringify(f([0,1,0,1])));     // -> [1,0,3,2]
console.log(JSON.stringify(f([0,0,0,0,0,5]))); // -> [1,2,3,4,5,0]
console.log(JSON.stringify(f([0,1,2,3])));     // -> [3,2,1,0]
console.log(JSON.stringify(f([0,1,1,1])));     // -> [3,0,1,2]
console.log(JSON.stringify(f([0,1,1,2,1,0]))); // -> [4,0,2,1,3,5]

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice way of getting the length and the range at the same time. I was gonna suggest a=m.map(_=>j++,j=0), but that's the same length and I'm sure you've already tried it. \$\endgroup\$ – ETHproductions Feb 17 '17 at 22:50
  • \$\begingroup\$ @ETHproductions You're right: I've tried it as well. :-) (It may be worth noting that this is not equivalent: this would set j to a.length rather than a.length-1 and would require a.splice(--j,0,a.splice(j-m[j],1)[0])) \$\endgroup\$ – Arnauld Feb 17 '17 at 23:07
  • \$\begingroup\$ Heh, I thought of that too, but I didn't think it was worth mentioning because it's the same length \$\endgroup\$ – ETHproductions Feb 18 '17 at 0:03
  • 1
    \$\begingroup\$ Easy -2: +a.splice(j-m[j--],1) \$\endgroup\$ – ETHproductions Feb 18 '17 at 2:54
2
\$\begingroup\$

Haskell, 85 bytes

f x|n<-length x-1=reverse x#[n,n-1..0]
(n:r)#l=r#(take n l++drop(n+1)l)++[l!!n]
x#l=x

Try it online! Example usage: f [0,1,1,2,1,0] yields [4,0,2,1,3,5].

f x calls the function # with list x reversed and a list [length x - 1, length x - 2, ... , 0]. (n:r)#l performs the reverse insertion sort by recursively taking the nth element out of l, where l!!n yields the nth element and take n l++drop(n+1)l yields the list l with the nth element removed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Haskell, so beautiful. \$\endgroup\$ – FMaz Feb 18 '17 at 21:16
1
\$\begingroup\$

perl, 61 bytes

@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p

Output ends up in array @o. Example with input array as command line arguments:

perl -le'@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p;print@o' 0 1 1 2 1 0
402135
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby, 49 bytes

->l{(w=l.size).times{l.insert(l.shift+w-=1,w)};l}

Performs the "reverse insertion" in place inside the list, starting with the largest number.

| improve this answer | |
\$\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.