22
\$\begingroup\$

Background

Programmers these days can't seem to keep their buffers straight! A common source of error is trying to use an array index that is too large for the buffer. Your task is to implement a buffer where large indices are reduced to a size that the buffer can handle. Because I decide exactly what's best for everyone, you will implement this buffer to my precise specifications.

Overview

You have a insert-only buffer that grows in size as elements are added to it. The buffer is zero-indexed, and also indexed modulo its current size. The special rule for this challenge is this:

  • To insert an item at index i means to compute j, j = i % buffer.length() and insert the new item after the jth item in the list.

The only special case is if the buffer is empty, as arithmetic modulo zero doesn't work. Thus, if the buffer is currently empty, the new item will be index 0.

If the buffer has only one item, then you are always inserting after the 0th item. This is just one instance of the general case.

If the buffer contains 6 items: [4, 9, 14, 8, 5, 2] and you are told to insert a new item 10 at index 15, you find that 15 % 6 == 3, and then insert the new 10 after the 8 at index 3 which gives a resulting buffer of [4, 9, 14, 8, 10, 5, 2]

Problem

Write a function or program that takes in an ordered list of positive integers, and positive integer indices at which to insert them.

Start with an empty buffer, and add the specified integers to the buffer at the corresponding indices.

Output the ordered list of integers that are in the buffer after all the specified insertions have been made.

This is a code-golf challenge, so shortest code wins.

Input guidelines

You may take the input lists however you see fit. Examples:

  • List of pairs: [ [1,1], [2,4], [3,9], [4,16], [5,25]...]
  • Item list and index list: [1, 2, 3, 4, 5...], [1, 4, 9, 16, 25]
  • Flattened: [1, 1, 2, 4, 3, 9, 4, 16, 5, 25 ...]
  • etc.

You may assume the input always contains at least one item and corresponding index.

Test cases

Squares case from above:

[(1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64)] -> [1, 2, 8, 7, 6, 5, 4, 3]

I generated these randomly:

[(11, 9), (13, 14)] -> [11, 13]
[(1, 18), (11, 7), (3, 35), (16, 22)] -> [1, 11, 16, 3]
[(3, 16), (16, 37), (0, 28), (18, 24)] -> [3, 18, 0, 16]
[(7, 26), (8, 20), (11, 39), (1, 23), (17, 27)] -> [7, 8, 11, 1, 17]
[(15, 35), (17, 7), (16, 15), (1, 13), (2, 6), (11, 34)] -> [15, 17, 1, 2, 16, 11]
[(2, 13), (1, 20), (16, 25), (8, 21), (5, 2), (16, 37), (3, 0)] -> [2, 3, 8, 1, 16, 5, 16]
[(6, 20), (15, 15), (12, 26), (10, 27), (17, 13), (7, 18), (4, 16)] -> [6, 10, 17, 12, 7, 4, 15]
[(18, 9), (5, 34), (15, 4), (12, 29), (2, 5), (7, 0), (7, 10), (16, 38)] -> [18, 7, 15, 2, 16, 5, 7, 12]
[(0, 12), (12, 0), (4, 16), (15, 12), (6, 28), (8, 10), (11, 24), (0, 25)] -> [0, 11, 8, 6, 15, 0, 4, 12]
[(6, 12), (14, 13), (10, 33), (11, 35), (1, 3), (0, 28), (15, 27), (8, 10), (1, 2)] -> [6, 14, 10, 1, 11, 8, 15, 0, 1]
[(2, 29), (19, 30), (18, 17), (13, 3), (0, 21), (19, 19), (11, 13), (12, 31), (3, 25)] -> [2, 13, 3, 11, 0, 12, 19, 18, 19]

Python3 reference implementation

def f(inputs):
    # `inputs` is a list of pairs
    buff = []
    for item, index in inputs:
        if len(buff) == 0:
            buff.insert(0, item)
        else:
            insert_after = index % len(buff)
            buff.insert(insert_after+1, item)
    return buff
\$\endgroup\$
2
  • \$\begingroup\$ Can the input be taken in reverse? \$\endgroup\$
    – FlipTack
    Jan 17, 2017 at 21:22
  • \$\begingroup\$ Yeah I think the input can be more-or-less as flexible as you want. \$\endgroup\$ Jan 17, 2017 at 21:24

13 Answers 13

8
\$\begingroup\$

Perl, 37 bytes

35 bytes of code + 2 bytes for -lp flags.

splice@F,1+<>%(@F||1),0,$_}{$_="@F"

Try it online!

The implementation is quite straight forward, splice inserts in array @F at index 1+<>%(@F||1) (note that @F||1 handles the case of the array being empty).

Just a few words about the (seemingly) unmatched braces }{ (because I had a comment about it, and I think it's quite weird for people who don't know Perl), and it's a quite common trick in Perl golfings:
-p flag surrounds the code with (roughly) while(<>){ CODE } continue { print }, (the continue is executed after each iteration). So with those unmatched }{, I change my code to while(<>) { CODE}{ } continue { print }. So it creates an empty block right after my code (but that's not a problem), and the continue is executed only once, after the while (ie. when the all the input has been read).

\$\endgroup\$
4
  • 3
    \$\begingroup\$ That }{ is driving me nuts... \$\endgroup\$ Jan 17, 2017 at 21:18
  • \$\begingroup\$ @ETHproductions I'm used to it but I love to show it to other people, they always think something is wrong! :) (the downside is that is messes with my emacs indentation..) \$\endgroup\$
    – Dada
    Jan 17, 2017 at 21:19
  • 1
    \$\begingroup\$ That }{ reminds me of this illusion \$\endgroup\$
    – Luis Mendo
    Jan 17, 2017 at 22:08
  • \$\begingroup\$ Yes, I did. :-) \$\endgroup\$
    – Dennis
    Jan 17, 2017 at 22:10
5
\$\begingroup\$

ES6 (Javascript), 58,57,53, 50 bytes

Golfed

a=>a.map((e,i)=>b.splice(1+e[1]%i,0,e[0]),b=[])&&b

Takes an array of index-value pairs, as input.

EDITS

  • Use && to return value, -1 byte
  • Removed |0 (as splice apparently can handle NaN just well), -2 bytes
  • Made b=[] a second "argument" to map(), -2 bytes (Thx @ETHproductions !)
  • Replaced b.length with map() index (i), -3 bytes (Thx @Patrick Roberts !)

Test

F=a=>a.map((e,i)=>b.splice(1+e[1]%i,0,e[0]),b=[])&&b

F([[11, 9], [13, 14]])
[ 11, 13 ]

F([[2, 29], [19, 30], [18, 17], [13, 3], [0, 21], [19, 19], [11, 13], [12, 31], [3, 25]])
[ 2, 13, 3, 11, 0, 12, 19, 18, 19 ]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice, I should've tried non-recursive approaches. I think you can do a=>a.map(e=>...,b=[])&&b \$\endgroup\$ Jan 17, 2017 at 22:38
  • 2
    \$\begingroup\$ You can subtract 3 bytes by changing e=> to (e,i)=> and using i instead of b.length \$\endgroup\$ Jan 18, 2017 at 16:51
  • \$\begingroup\$ @PatrickRoberts That's a nice idea ! Thank you ! \$\endgroup\$
    – zeppelin
    Jan 18, 2017 at 19:13
5
\$\begingroup\$

Haskell, 70 69 bytes

b!(x,i)|b==[]=[x]|j<-1+i`mod`length b=take j b++x:drop j b
foldl(!)[]

Try it online! Usage: foldl(!)[] [(1,5),(2,4),(3,7)]. Saved one byte thanks to @nimi!

Explanation:

b!(x,i)                         -- b!(x,i) inserts x into list b at position i+1
 | b==[] = [x]                  -- if b is empty return the list with element x
 | j <- 1 + i `mod` length b    -- otherwise compute the overflow-save insertion index j
     = take j b ++ x : drop j b -- and return the first j elements of b + x + the rest of b
foldl(!)[]                      -- given a list [(1,2),(3,5),...], insert each element with function ! into the initially empty buffer

Solution without computing the modulus: (90 bytes)

f h t(x,-1)=h++x:t
f h[]p=f[]h p
f h(c:t)(x,i)=f(h++[c])t(x,i-1)
g((x,_):r)=foldl(f[])[x]r

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ j<-1+i`mod`length b saves a byte. \$\endgroup\$
    – nimi
    Jan 18, 2017 at 17:47
4
\$\begingroup\$

MATL, 24 22 bytes

"N?@2)yn\Q:&)@1)wv}@1)

Input is a matrix (with ; as row separator) containing the values in the first row and the indices in the second.

Output is a column array, displayed as numbers separated by newlines.

Try it online! Or verify all test cases, with each result displayed on a single line.

Explanation

"          % Input matrix (implicit). For each column 
  N        %   Number of elements in the stack
  ?        %   If nonzero (true for all iterations but the first)
    @2)    %     Push second element of current column: new index
    yn     %     Duplicate current buffer; push its number of elements
    \      %     Modulo
    Q      %     Add 1
    :&)    %     Split buffer at that point. This gives two pieces, one
           %     of which may be empty
    @1)    %     Push first element of current column: new value
    wv     %     Swap; concatenate all stack. This places the new value
           %     between the two pieces of the buffer
  }        %   Else (this is executed only in the first iteration)
    @1)    %     Push first element of current column: new value
           %   End (implicit)
           % End (implicit)
           % Display (implicit)
\$\endgroup\$
4
\$\begingroup\$

Python 2, 64 62 58 56 bytes

x=[]
for n,i in input():x[i%(len(x)or 1)+1:0]=n,
print x

Thanks to @xnor for golfing off 2 bytes!

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Can you do (len(x)or 1) instead of initializing the length? \$\endgroup\$
    – xnor
    Jan 18, 2017 at 0:11
  • \$\begingroup\$ Looking for a shorter way. Both len(x or[0]) and -~len(x[1:]) tie. \$\endgroup\$
    – xnor
    Jan 18, 2017 at 1:06
4
\$\begingroup\$

Python 2, 62 60 bytes

Takes input as a list of pairs, prints the result. Edit: Outgolfed by Dennis

b=[]
for x,y in input():b.insert(1+y%(len(b)or 1),x)
print b

Try it online!

This is quite simple - loop through the input, inserting the items into the correct place, and then print the result. Deciding which index to insert into is done with 1+y%(len(b)or 1). This is the standard way to do modular indexing, with the or 1 to handle the edge case of an empty list.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 60 bytes

f=([[q,r],...a],z=[])=>z.splice(r%z.length+1,0,q)+a?f(a,z):z

Test snippet

f=([[q,r],...a],z=[])=>z.splice(r%z.length+1,0,q)+a?f(a,z):z

I.textContent = I.textContent.replace(/(.+) -> (.+)/g, (_,a,b) => _ + " (" + (f(eval(a.replace(/\(/g, "[").replace(/\)/g, "]"))) + "" == eval(b) + "") + ")")
<pre id=I>[(11, 9), (13, 14)] -> [11, 13]
[(1, 18), (11, 7), (3, 35), (16, 22)] -> [1, 11, 16, 3]
[(3, 16), (16, 37), (0, 28), (18, 24)] -> [3, 18, 0, 16]
[(7, 26), (8, 20), (11, 39), (1, 23), (17, 27)] -> [7, 8, 11, 1, 17]
[(15, 35), (17, 7), (16, 15), (1, 13), (2, 6), (11, 34)] -> [15, 17, 1, 2, 16, 11]
[(2, 13), (1, 20), (16, 25), (8, 21), (5, 2), (16, 37), (3, 0)] -> [2, 3, 8, 1, 16, 5, 16]
[(6, 20), (15, 15), (12, 26), (10, 27), (17, 13), (7, 18), (4, 16)] -> [6, 10, 17, 12, 7, 4, 15]
[(18, 9), (5, 34), (15, 4), (12, 29), (2, 5), (7, 0), (7, 10), (16, 38)] -> [18, 7, 15, 2, 16, 5, 7, 12]
[(0, 12), (12, 0), (4, 16), (15, 12), (6, 28), (8, 10), (11, 24), (0, 25)] -> [0, 11, 8, 6, 15, 0, 4, 12]
[(6, 12), (14, 13), (10, 33), (11, 35), (1, 3), (0, 28), (15, 27), (8, 10), (1, 2)] -> [6, 14, 10, 1, 11, 8, 15, 0, 1]
[(2, 29), (19, 30), (18, 17), (13, 3), (0, 21), (19, 19), (11, 13), (12, 31), (3, 25)] -> [2, 13, 3, 11, 0, 12, 19, 18, 19]</pre>

\$\endgroup\$
2
\$\begingroup\$

V, 38 40 35 bytes

This answer bends the definition of list, and isn't normally a language you'd use for list manipulation, but I wanted to use [count]/{regex} which I recently added to V. The input is taken like [index] [num] [index] [num] ... and returned like [num] [num] [num].

Í ¨ä«© ½/¯ÜdÜ+òhea ±^
Hdd2xdG@"
X

Try it online!

Hexdump for 2 hidden characters:

00000000: cd20 a8e4 aba9 20bd 2faf dc64 dc2b f268  . .... ./..d.+.h
00000010: 6561 20b1 161b 5e0a 4864 6432 7864 4740  ea ...^.Hdd2xdG@
00000020: 220a 58                                  ".X

Explanation

The code up to dG@" formats all \d+ \d+ pairs so that a list 1 2 3 4 5 6 would end up like

a 2^[^3/\d\+
hea 4^[^5/\d\+
hea 6^[^

and then the dG@" executes all of that as V code like the following:

a 2^[                 | insert " 2" and return to command mode
     ^                | LOOP: go to the first number
      3/\d\+          | find the 3rd number (0 indexed)
h                     | move one character left
 e                    | go to the end of the next word
  a 4^[               | append " 4" and return to command mode
       ^5/\d\+        | basically the same as LOOP on, just with different numbers
\$\endgroup\$
0
2
\$\begingroup\$

PHP, 72 92 bytes

for($b=[];++$i<$argc;)array_splice($b,$b?$argv[$i]%count($b)+1:0,0,$argv[++$i]);print_r($b);

takes input flattened from command line arguments. Run with -nr.

\$\endgroup\$
3
  • \$\begingroup\$ I'm fairly certain this answer is invalid: I got a Fatal error: Uncaught DivisionByZeroError: Modulo by zero, fixed that, then tried 1 1 1 2 1 3 and got [1=>null] as output instead of [1,3,2] \$\endgroup\$
    – user59178
    Jan 18, 2017 at 16:43
  • \$\begingroup\$ It still overwrites j+1 rather than inserting after j, no? 18 1 7 11 35 3 22 16 => [1,11,16] rather than [1,11,16,3] \$\endgroup\$
    – user59178
    Jan 19, 2017 at 9:23
  • \$\begingroup\$ @user59178: Oh I had missed the insert keyword. Thanks; fixed. \$\endgroup\$
    – Titus
    Jan 19, 2017 at 11:26
2
\$\begingroup\$

Java 7, 125 124 bytes

import java.util.*;List z(int[]a){List r=new Stack();for(int i=0,q=a.length/2;i<q;)r.add(i<1?0:a[i+q]%i+1,a[i++]);return r;}

Accepts a flat list of values followed by indexes. For the squares test case the input would be new int[] {1, 2, 3, 4, 5, 6, 7, 8, 1, 4, 9, 16, 25, 36, 49, 64}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 62 bytes

Fold[Insert[#,#2[[1]],Mod[Last@#2,Tr[1^#]]+2/.0/0->-1]&,{},#]&

Pure function with first argument # expected to be a list of pairs. Starting with the empty list {}, left Fold the input list # with the following function:

Insert[                                            Insert
       #,                                          into the first argument
         #2[[1]],                                  the first element of the second argument
                 Mod[                              at the position given by the modulus of
                     Last@#2,                      the second element of the second argument
                             Tr[1^#]               with respect to the length of the first argument
                                    ]+2            plus 2 (plus 1 to account for 1-indexing, plus 1 because we are inserting after that position)
                                       /.          then replace
                                         0/0       Indeterminate
                                            ->     with
                                              -1   negative 1
                                                ]& End of function
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 51 bytes

{my @a;.map:{splice @a,(@a??$^b%@a+1!!0),0,$^a};@a}

Takes the flattened input.

\$\endgroup\$
1
\$\begingroup\$

Clojure, 87 bytes

#(reduce(fn[r[v i]](let[[b e](split-at(+(mod i(max(count r)1))1)r)](concat b[v]e)))[]%)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.