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>

• Alex A.: How do you feel about NULL for an empty array for languages where an empty array is NULL?
• Martin Ender: @AlexA. If it's a common / the representation of the empty array in said language(s), I'm fine with that.
• Dennis: A simple golf? That's the most difficult thing I did in CJam all week. :P

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]

• Jakube: Damn. Since when do we have an interleave method? Just wanted to post ssC,cFPQamedSCtQ].
• orlp: @Jakube isaac sneakily committed it in 6 days ago.
• izzyg: @Jakube Since github.com/isaacg1/pyth/commit/…
• sentiao: @Jakube since Pyth can grow to solve any problem. That's the problem with golfing languages. Esoteric languages exist for the sake of esoteric languages; as they are designed *afterwards.
• user45941: @sentiao To be fair, the host language (Python) has had interleaving under a different name for a while.

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

• Martin Ender: You can shorten this by making it a unnamed function instead: ->a,b,c{...}. Also chances are insert doesn't need parentheses.
• Dylan Frese: @MartinBüttner I did know about the unnamed function with the lambda, but I didn't feel that was in the spirit of the challenge (which usually asks for a named function). Thanks for spotting the parens, though.
• Martin Ender: Unless the challenge specifically asks for a named function, unnamed functions are always acceptable. And I didn't ask for a named function (I never do ;)).

Answer 5

CJam, (削除) 34 (削除ここまで) (削除) 23 (削除ここまで) 18 bytes

{.2円/\ee+{0=}1ドルf=}

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=}1ドルf=}~

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

• Dennis: That floating point approach is very clever and (sadly) better than mine. You can get down to 19 bytes with q~.5fm.2円/\ee+1ドルf=p and to 18 bytes by using an anonymous function: {.5fm.2円/\ee+1ドルf=}
• Dennis: Same idea without the floating-point trick: {.2円/\ee+{0=}1ドルf=} (still 18 bytes)
• randomra: @Dennis Thanks, I couldn't find the get array element operator for 1f=. I will leave it as a full program though.
• Dennis: Your call. Do you mind me asking why you're opposed to posting a function?
• randomra: @Dennis I just started CJam and wasn't sure how to use the functions. Now I figured it out so I changed the answer to that.

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>

• Alex A.: Out of curiosity, what about the code makes it specific to Firefox? Is it because it's ES6?
• edc65: @AlexA.it's because it's ES6, yes. Particularly the fat arrow function is not implemented even in developer version of Chrome (AFAIK)
• DocMax: Indeed, not even the Canary build of Chrome supports it.

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+@@.{a22ドル$=+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].
 22ドル$= 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.

• Martin Ender: I think the current format is okay. Nested arrays with interleaving nil values are a bit of stretch. But in either case this isn't winning the contest, so I'm not really worried about it either way.

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