Generalised Array Riffle

Question

A simple golf to start the week! You're given three arrays: the base array B, the value array V and the index array I. You should produce another array where the values from V are inserted into B at the indices specified by I. Here is an example:

Base:    [5, 1, 4, 1, 3]
Values:  [0, 0, 7]
Indices: [5, 0, 3]

The indices point at the following positions in the base array:

[ 5, 1, 4, 1, 3 ]
 ^        ^    ^
 0        3    5

So inserting the corresponding elements from the value array, the result should be:

[0, 5, 1, 4, 7, 1, 3, 0]

Rules

You may write a program or function, taking input via STDIN (or closest alternative), command-line arguments or function arguments and output the result via STDOUT (or closest alternative), function return value, or by modifying the array given as the B parameter.

If your submission is a function, I and V can be modified in any way, as well as B if it isn't used for output.

You may make the following assumptions about the input:

• All elements of the base and value array will be non-negative integers.
• The value array will have at most one more element than the base array.
• The value array and index array will have the same number of elements.
• The index array will not contain repeated indices, and all indices will be in range.
• The base and value arrays may contain repeated elements.
• Any or all of the arrays may be empty.
• You must not assume that the indices are given in any particular order.
• You may receive input and produce output in any convenient, unambiguous string or list format. You may also choose to receive the three arrays in a different order.
• You may choose between 0-based and 1-based indexing.

This is code golf, so the shortest answer (in bytes) wins.

Test Cases

Given in the format B V I => Result for 0-based indexing. If you're using 1-based indexing, increment the elements of the third array by 1.

[] [] [] => []
[] [1] [0] => [1]
[1,2] [] [] => [1,2]
[1,2] [3] [0] => [3,1,2]
[1,2] [3] [1] => [1,3,2]
[1,2] [3] [2] => [1,2,3]
[0,0,0] [1,1,1,1] [0,1,2,3] => [1,0,1,0,1,0,1]
[5,1,4,1,3] [0,0,7] [5,0,3] => [0,5,1,4,7,1,3,0]
[1,2,3,4] [4,3,2,1] [4,0,3,1] => [3,1,1,2,3,2,4,4]

Let me know if you come across other interesting edge cases, and I'll add them.

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

var QUESTION_ID=50369;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:&lt;(?:s&gt;[^&]*&lt;\/s&gt;|[^&]+&gt;)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>

Answer 1

Python 2, 54

lambda B,*X:map(B.insert,*zip(*sorted(zip(*X))[::-1]))

Takes input as B,I,V. Modifies the input B when called (thanks to Martin Büttner for reminding me this is possible).

Uses map to call B.insert on each index/element pair. To avoid the issue of the list indices shifting as elements are inserted, sorts the pairs in decreasing order of index by an ugly zip/sort/unzip. If not for the shifting issue, we could just do map(B.insert,*X).

Old method (65):

B,V,I=input()
for i,v in sorted(zip(I,V))[::-1]:B[i:i]=v,
print B

Answer 2

Pyth, 14 bytes

s.icFPQmedSCtQ

Demonstration.

This program takes the inputs as a 3-tuple of lists in the order Base, Indices, Values.

Explanation on the example [5, 1, 4, 1, 3], [5, 0, 3], [0, 0, 7]:

1. Take the input: implicit, Q is the input.

2. Make the index, value pairs: CtQ = [(5, 0), (0, 0), (3, 7)]

3. Sort the pairs into increasing index order: SCtQ = [(0, 0), (3, 7), (5, 0)]

4. Take the value out of each pair: medSCtQ = [0, 7, 0]

5. Split the base list at the location of the indicies: cFPQ = [[], [5, 1, 4], [1, 3], []]

6. Interleave 3 and 4: .icFPQmedSCtQ = [[], 0, [5, 1, 4], 7, [1, 3], 0, []]

7. Combine into one list: s.icFPQmedSCtQ = [0, 5, 1, 4, 7, 1, 3, 0]

Answer 3

Haskell, 62 bytes

import Data.List
f b v i=map snd$sort$zip[0.5,1.5..]b++zip i v

Usage example: f [5,1,4,1,3] [0,0,7] [5,0,3] -> [0,5,1,4,7,1,3,0].

How it works: augment the base list with "and-a-half" indices starting at 0.5 (e.g. [(0.5,5),(1.5,1),(2.5,4),(3.5,1),(4.5,3)]) and concatenate it with the index-value pairs. Sort and discard the index.

Remark: don't know if I'm cheating here. From a mathematical point of view it's fine, but a programmer might argue that the list of indices [5,0,3] is not a list of Integers as requested, but a list of Fractionals (to be exact, the type is polymorphic, but must belong to the Fractional class, e.g. Float or Double).

Answer 4

Ruby, 60 59 53 bytes

->a,b,c{c.zip(b).sort.reverse.map{|i,v|a.insert i,v}}

And the ungolfed version

def riffle(array, values, indices)
    indices.zip(values).sort.reverse.each do |index, value|
        array.insert(index, value)
    end
end

Answer 5

CJam, 34 23 18 bytes

{.\2/\ee+{0=}$1f=}

My first CJam submission. Advices are welcome, I'm sure there is a lot to golf.

16 bytes saved with the help of @MartinBüttner and @Dennis.

Function expecting input on the stack in order B V I (I is the topmost).

Example usage:

[5 1 4 1 3] [0 0 7] [5 0 3] {.\2/\ee+{0=}$1f=}~

Method:

• pair the array's ith element with i+0.5
• pair insert values with insert positions
• merge the resulting two arrays
• sort array based on position elements
• keep value elements

Answer 6

K, 22 21 bytes

{,//+(y@<z;(z@<z)_ x)}

We define a 3 argument function {…} with the implicit variables x, y and z representing the starting list, the value list and the index list, respectively. The "cut" operator (_) is used to split the starting list apart at the sorted list of given indices ((z@<z)). We interleave values (after sorting them correspondingly) with the split up chunks of the original array by forming a list ((a;b)), taking its transpose (+) and flattening the result (,//).

Usage example:

  f:{,//+(y@<z;(z@<z)_ x)}
{,//+(y@<z;(z@<z)_ x)}

  f[1 2 3 4;4 3 2 1;4 0 3 1]
3 1 1 2 3 2 4 4

  f[5 1 4 1 3;0 0 7;5 0 3]
0 5 1 4 7 1 3 0

Spaces around the underscore are necessary because K allows underscores in identifiers. K5 removes this potential ambiguity. If we could count on the indices coming in ascending order and underscores were not valid identifiers, we could use the much nicer 13 byte program:

{,//+(y;z_x)}

(sigh.)

edit:

{,//+(y@<z;(z@<z)_ x)} / before
{,//+(y@<z;z[<z]_ x)}  / after

Breaks symmetry, but we can save a byte by using bracket-indexing ([…]) instead of the infix @ indexing operator. Usually this makes programs longer, but in this case we needed parens anyway to sort z before performing the cut.

Answer 7

Pyth, 17 bytes

ssC,cFPQamedSCtQ]

@isaacg beat my solution already. But since I had my documentation finished, I'm just gonna post it anyways.

This takes the input in the format B, I, V. You can try it here: Demonstration or Test Suite

Explanation:

I'm using the example B = [5,1,4,1,3], I = [5,0,3], V = [0,0,7] from the OP.

                    implicit: Q = input()
      PQ            all elements but last of Q   => [[5,1,4,1,3], [5,0,3]]
    cF              split B it the indices in I  => [[], [5,1,4], [1,3], []]

              tQ    all elements but first of Q  => [[5,0,3], [0,0,7]]
             C      zip                          => [(5,0), (0,0), (3,7)]
            S       sort                         => [(0,0), (3,7), (5,0)]
         med        extract the end of each pair => [0,7,0]
        a       ]   append an empty list         => [0,7,0,[]]

   ,                create a pair => ([[], [5,1,4], [1,3], []], [0,7,0,[]])
  C                 zip           => [([],0), ([5,1,4],7), ([1,3],0), ([],[])]
 s                  sum           => ([],0,[5,1,4],7,[1,3],0,[],[])
s                   sum           => [0,5,1,4,7,1,3,0]

Answer 8

JavaScript (ES6), 75

A function with 3 array parameters, returnning an array. Weirdly, this function modifies its i parameter (as kindly allowed by OP)

Test running the snippet, Firefox only as usual.

f=(b,v,i,j=0)=>b.concat(v).map(p=>(p=i.indexOf(j))<0?b[j++]:(i[p]=-1,v[p]))

// TEST
out=x=>O.innerHTML+=x+'\n'

test=[
{ b:[], v:[], i:[], k:[] },
{ b:[], v:[1], i:[0], k:[1] },
{ b:[1,2], v:[], i:[], k:[1,2] },
{ b:[1,2], v:[3], i:[0], k:[3,1,2] },
{ b:[1,2], v:[3], i:[1], k:[1,3,2] },
{ b:[1,2], v:[3], i:[2], k:[1,2,3] },
{ b:[0,0,0], v:[1,1,1,1], i:[0,1,2,3], k:[1,0,1,0,1,0,1] },
{ b:[5,1,4,1,3], v:[0,0,7], i:[5,0,3], k:[0,5,1,4,7,1,3,0] },
{ b:[1,2,3,4], v:[4,3,2,1], i:[4,0,3,1], k:[3,1,1,2,3,2,4,4] }
];

test.forEach(x=>{
  r = f(x.b,x.v,x.i.slice(0)) // pass a copy of i, as the function will alter it
  ok = ''+r==''+x.k
  s='Test ' + (ok?'OK':'FAIL')
  +'\n B ['+x.b
  +']\n V ['+x.v
  +']\n I ['+x.i
  +']\n Result ['+r
  +']\n Check  ['+x.k
  +']\n'
  out(s)
  
})

<pre id=O></pre>

Answer 9

Mathematica, 52 51 bytes

Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&

Example:

In[1]:= f = Last/@(Tr@#2->#&~MapIndexed~#⋃Thread[#3+.5->#2])&;

In[2]:= f[{5, 1, 4, 1, 3}, {0, 0, 7}, {5, 0, 3}]

Out[2]= {0, 5, 1, 4, 7, 1, 3, 0}

Explanation:

Using the example above.

• Tr@#2->#&~MapIndexed~# => {1 -> 5, 2 -> 1, 3 -> 4, 4 -> 1, 5 -> 3}
• Thread[#3+.5->#2] => {5.5 -> 0, 0.5 -> 0, 3.5 -> 7}
• Then take the (sorted) union of these two lists. (=> {0.5 -> 0, 1 -> 5, 2 -> 1, 3 -> 4, 3.5 -> 7, 4 -> 1, 5 -> 3, 5.5 -> 0})
• And then take the last element of each pair. (=> {0, 5, 1, 4, 7, 1, 3, 0})

Answer 10

CJam, 30 29 bytes

q~.\2/$z~0@+2ew@f{\~@<>}.\e_p

This is tooo long. I feel like this is not a golfing language submission :|

Try it online here

Answer 11

R, 75 bytes

function(b,v,i){n=b;j=0;for(g in v)n=append(n,g,i[j<-j+1]+sum(i<i[j])-1);n}

This creates an unnamed function. To call it, give it a name, e.g. f=function.... Note that the arrays must be 1-indexed because that's just how R rolls.

Ungolfed + explanation:

f <- function(b, v, i) {
    # Initialize the output vector to b
    n <- b

    # Initialize an index over the indices
    j <- 0

    # Loop over the values to insert
    for(g in v) {
        # Get the index of the next given insertion index
        j <- j + 1

        # Insert g into n.
        # The position at which to insert the value is determined by
        # adding the number of indices less than the current one and
        # subtracting 1. The subtraction is because we're using the
        # `after` argument in the `append` function.

        n <- append(n, g, i[j] + sum(i < i[j]) - 1)
    }

    # Return n
    n
}

Examples:

> f(c(), c(), c())
[1] NULL

> f(c(0, 0, 0), c(1, 1, 1, 1), c(1, 2, 3, 4))
[1] 1 0 1 0 1 0 1

> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(6, 1, 4))
[1] 0 5 1 4 7 1 3 0

Suggestions are welcome as always!

Answer 12

CJam, 19 bytes

l~_,)N*q~.{t}~.\N-p

This is a full program that the reads the arrays B, I and V (one per line, in that order) from STDIN.

Try it online in the CJam interpreter.

How it works

l~    e# Evaluate the first line of input.
_,)   e# Compute the array length and add 1.
N*    e# Push a string of that many linefeeds.
q~    e# Evaluate the remaining input.
.{t}~ e# Vectorized array set: for each index in the array from line 2, replace the
      e# LF at that index by the corresponding element of the array from line 3.
.\    e# Interleave the two arrays on the stack.
N-    e# Remove the linefeeds.
p     e# Print.

---

CJam, 20 bytes

{Qa+@@.{a2$2$=+t}e_}

This is an anonymous function that pops B, V and I (top to bottom) from the stack and leaves a single array on the stack in return.

Try it online in the CJam interpreter.

How it works

Qa+      e# Append [[]] to B.
@@       e# Rotate V and I on top of B.
.{       e# For each v in V and the corresponding i in I:
   a     e#     Push [v].
   2$2$= e#     Retrieve b := B[i].
   +     e#     Append to push [v b].
         e#     The stack now consists of: B i [v b]
   t     e#     Set B[i] := [v b].
}        e#
e_       e# Flatten B.

Answer 13

Ruby, 48 bytes

I think this complies with the rules, but please check.

->b,v,i{l=-1;i.map{|j|b[j]=[v[l+=1],b[j]]};b*?:}

Unnamed function taking the three arrays as input. Outputs a string that can be parsed unambiguously into an array of numbers with the ruby expression x.split(/:+/).map(&:to_i).

Test cases on ideone.

I could save 3 more bytes, but the output format [1,2,[nil,5]] is stretching the rules a bit too mych imo, although it is unambiguous.

Answer 14

R, 60

As an unnamed function that takes b, v and i

function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}

Expands b with NAs Fills the gaps where required with v Returns the vector without NAs

> f=function(b,v,i){e=c(NA,rbind(b,NA));e[i*2+1]=v;e[!is.na(e)]}
> f(c(), c(), c())
logical(0)
> f(c(0, 0, 0), c(1, 1, 1, 1), c(0, 1, 2, 3))
[1] 1 0 1 0 1 0 1
> f(c(5, 1, 4, 1, 3), c(0, 0, 7), c(5, 0, 3))
[1] 0 5 1 4 7 1 3 0

Answer 15

Java, 253, 226, 219, 209

not exactly a winner, but oh well.

Assuming that B, V, and I are not null. v (lowercase v) is the length of the Values/Indicies arrays. R is the returned array. r is the length of the returned array. x, y, and i are all temporary ints.

int[]f(int[]B,int[]V,int[]I){int v=V.length,r=B.length+v,x,y,i;int[]R=java.utils.Arrays.copyOf(B,r);for(x=0;x<v;x++){i=I[x];for(y=0;y<x;y++)if(I[x]>I[y])i++;for(y=r-2;y>=i;y--)R[y+1]=R[y];R[i]=V[x];}return R;}

expanded:

int[]f( int[] B, int[] V, int[] I ) {
    int v = V.length, //length of Values
        r = B.length + v, //length of the result
        x, y, i; //temps
        int[] R = java.utils.Arrays.copyOf( B, r );       
        for( x = 0; x < v; x++ ) {
        i = I[x];
        for( y = 0; y < x; y++ )
            if( I[x] > I[y] )
                i++;
        for( y = r - 2; y >= i; y-- )
            R[y+1] = R[y];
        R[i] = V[x];
    }
    return R;
}

Answer 16

APL, 22 bytes

{(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}

In ⎕IO←0 to match the test cases.

It's a standard algorithm: the index vector of the first argument is appended to the given indexes (3rd argument). ⍋ computes the permutation that would sort the indexes in ascending order. Since APL's sorting algorithm is stable by definition, the permutation computed puts the element of the catenation of the second and first argument in the right place.

For instance:

    {(∊⌽2↑⍵)[⍋(2⊃⍵),⍳≢⊃⍵]}(5 1 4 1 3)(0 0 7)(5 0 3)
0 5 1 4 7 1 3 0