11
\$\begingroup\$

Let's consider a list \$L\$ (initially empty) and a pointer \$p\$ into this list (initialized to \$0\$).

Given a pair of integers \$(m,n)\$, with \$m\ge 0\$ and \$n>0\$:

  1. We set all uninitialized values in \$L\$ up to \$p+m+n\$ (excluded) to \$0\$.
  2. We advance the pointer by adding \$m\$ to \$p\$.
  3. We create a vector \$[1,2,...,n]\$ and 'add' it to \$L\$ at the position \$p\$ updated above. More formally: \$L_{p+k} \gets L_{p+k}+k+1\$ for each \$k\$ in \$[0,..,n-1]\$.

We repeat this process with the next pair \$(m,n)\$, if any.

Your task is to take a list of pairs \$(m,n)\$ as input and to print or return the final state of \$L\$.

Example

Input: [[0,3],[1,4],[5,2]]

  • initialization:

    p = 0, L = []
    
  • after [0,3]:

    p = 0, L = [0,0,0]
             + [1,2,3]
             = [1,2,3]
    
  • after [1,4]:

    p = 1, L = [1,2,3,0,0]
             +   [1,2,3,4]
             = [1,3,5,3,4]
    
  • after [5,2]:

    p = 6, L = [1,3,5,3,4,0,0,0]
             +             [1,2]
             = [1,3,5,3,4,0,1,2]
    

Rules

  • Instead of a list of pairs, you may take the input as a flat list \$(m_0,n_0,m_1,n_1,...)\$ or as two separated lists \$(m_0,m_1,...)\$ and \$(n_0,n_1,...)\$.

  • You may assume that the input is non-empty.

  • The output must not contain any trailing \$0\$'s. However, all intermediate or leading \$0\$'s must be included (if any).

  • This is .

Test cases

Input:

[[0,3]]
[[2,3]]
[[0,4],[0,5],[0,6]]
[[0,3],[2,2],[2,1]]
[[0,1],[4,1]]
[[0,3],[1,4],[5,2]]
[[3,4],[3,4],[3,4]]
[[0,1],[1,2],[2,3],[3,4]]
[[2,10],[1,5],[2,8],[4,4],[6,5]]

Output:

[1,2,3]
[0,0,1,2,3]
[3,6,9,12,10,6]
[1,2,4,2,1]
[1,0,0,0,1]
[1,3,5,3,4,0,1,2]
[0,0,0,1,2,3,5,2,3,5,2,3,4]
[1,1,2,1,2,3,1,2,3,4]
[0,0,1,3,5,8,11,14,11,14,17,20,12,0,0,1,2,3,4,5]
\$\endgroup\$
  • 2
    \$\begingroup\$ @KevinCruijssen Given that I usually try to avoid edge cases and given that another answer is already doing something special with the empty list, supporting it is now optional. \$\endgroup\$ – Arnauld Oct 25 at 7:39
  • \$\begingroup\$ Thanks, that saves me a bit of trouble fixing it, since my program was outputting 0 due to the sum at the end. \$\endgroup\$ – Kevin Cruijssen Oct 25 at 7:40

18 Answers 18

4
\$\begingroup\$

J, 27 bytes

[:+/[(>:@i.@[,~0$~])"0+/\@]

Try it online!

Takes two separate lists for m an n - the list for n is the left argument of the function, the list for m - the right one.

K (ngn/k), 42 bytes

{+/{x,'((|/#'x)-#'x)#'0}((+\x)#'0),'1+!'y}

Try it online!

Takes two separate lists for m an n

It's too long currently, I'll try to golf it.

\$\endgroup\$
  • 1
    \$\begingroup\$ I tried solving this independently and came up with something very similar, but 25 bytes. Kind of fun 3 nested dyadic hooks +/@(((,~#&0)~1+i.)"0~+/\): Try it online! \$\endgroup\$ – Jonah Oct 26 at 3:42
  • \$\begingroup\$ @Jonah Great! I don't mind if you post it separately. \$\endgroup\$ – Galen Ivanov Oct 26 at 4:08
4
\$\begingroup\$

Jelly,  10  9 bytes

Ä0ẋżR}F€S

A dyadic Link accepting a list of integers on each side, \$M\$ on the left \$N\$ on the right, which yields a list of integers.

Try it online! Or see the test-suite.

How?

Ä0ẋżR}F€S - Link: list of integers, M; list of integers, N
Ä         - cumulative sums (M) = [m1, m1+m2, m1+m2+m3, ...]
 0ẋ       - zero repeated = [[0]*m1,[0]*(m1+m2),[0]*(m1+m2+m3), ...]
    R}    - range (right=N) = [[[1,2,3,...,n1]],[[1,2,3,...n2]],[[1,2,3,...,n3]], ...]
   ż      - zip together = [[[0]*m1,[[1,2,3,...,n1]]],[[0]*(m1+m2),[[1,2,3,...,n2]]],[[0]*(m1+m2+m3),[[1,2,3,...,n3]]], ...]
      F€  - flatten each = [[0,0,...,0,1,2,3,...,n1],[0,0,...,0,1,2,3,...,n2],[0,0,...,0,1,2,3,...,n3], ...]
        S - sum
\$\endgroup\$
  • \$\begingroup\$ Nice. I’d missed the fact that two lists were acceptable input. \$\endgroup\$ – Nick Kennedy Oct 25 at 18:28
4
\$\begingroup\$

Jelly, 12 11 bytes

+ɼ0x;R}ʋ/€S

Try it online!

A full program that takes a list of lists of integers as its argument and returns a list of integers. Can be adapted to work as a link by resetting the register to zero after each call (as implemented in the footer on TIO).

Saved a byte now list can be non-empty.

\$\endgroup\$
4
\$\begingroup\$

Java 8, 148 147 bytes

N->M->{int l=M.length,s=M[l-1],p=0,L[],i=0,j;for(int n:N)s+=n;for(L=new int[s];i<l;i++)for(p+=N[i],j=s;j-->0;)L[j]-=j<p|j>=p+M[i]?0:~j+p;return L;}

-1 byte thanks to @ceilingcat.

Takes both integer-arrays as separated inputs.

Try it online.

Explanation:

N->M->{            // Method with integer-array as two parameters as well as return-type
  int l=M.length,  //  Length of the input-arrays
      s=           //  Length of the output-array,
        M[l-1],    //  starting at the last pointer-item of array `M`
      p=0,         //  Position `p` as specified in the challenge, starting at 0
      L[],         //  Output list, starting uninitialized
      i=0,j;       //  Index integers
  for(int n:N)     //  Loop over the value-list `N`:
    s+=n;          //   And add all of them to the output-length
  for(L=new int[s];//  Now initialize the output-list of size `s`, filled with 0s by default
      i<l;i++)     //  Loop `i` in the range [0, `l`):
    for(p+=N[i],   //   Increase position `p` by the `i`'th pointer of `N`
        j=s;j-->0;)//   Inner loop `j` in the range (`s`,0]:
     L[j]-=        //    Decrease the `j`'th item of the output-list by:
       j<p         //     If `j` is smaller than position `p`
       |j>=        //     or `j` is larger than or equal to
        p+M[i]?    //     pointer `p` and the `i`'th value of `M` combined
         0         //      Leave the `j`'th item of output-array the same by adding 0
       :           //     Else:
        ~j+p;      //      Decrease the `j`'th item of the output-array by `-j-1+p`
                   //      (increase it by the difference between `j` and `p`, plus 1)
  return L;}       //  And after the nested loops: return the resulting array
\$\endgroup\$
3
\$\begingroup\$

Zsh, 59 56 54 bytes

-3 bytes by changing to my Bash strategy, -2 bytes by switching back to my original strategy, now that the rules specify the list is non-empty.

for m n;for ((i=0,p+=m;i<n;a[p+i]+=++i)):
<<<${a/#%/0}

Try it online: [Original strat handling empty case] [Adapted Bash strat] [Current]


Setting a[5]=1 causes a[1] through a[4] to be initialized empty. The final parameter expansion replaces all empty elements with 0.

for m n                                 # implicit 'in "$@"'
    for ((i=0, p+=m; i<n; a[p+i]+=++i)) # increment p by m, add to a[p,p+n-1]
        :                               # ':' is a no-op builtin
<<<${a/#%/0}                            # the glob #% matches empty elements
\$\endgroup\$
3
\$\begingroup\$

Haskell, 90 87 bytes

(foldl(%)[].).zipWith(\o p->(0<$[1..o])++[1..p]).scanl1(+)
(a:b)%(c:d)=a+c:b%d
b%d=b++d

Takes the input as two separate lists [m0,m1,...] and [n0,n1,...].

Try it online!

A variant (function % same as above), also 87 bytes:

(foldl(\l(o,p)->((0<$[1..o])++[1..p])%l)[].).zip.scanl1(+)
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 19 bytes

1⊥0⌈(↑(⍳+)¨-⊢)∘(+\)

Try it online!

Uses the algorithm described in my J answer.

How it works

1⊥0⌈(↑(⍳+)¨-⊢)∘(+\)  left = n's, right = m's
              ∘(+\)  m2 = cumulative sum of m's
      (⍳+)¨          Nested array of 1..(each element of n+m2)
           -⊢        Subtract each elem of m2 from each row
    (↑       )       Promote nested array to matrix
  0⌈                 Take max with 0 (change negatives to 0)
1⊥                   Sum in column direction

APL (Dyalog Unicode), 20 bytes

{1⊥↑⍺{(⍵⍴0),⍳⍺}¨+\⍵}

Try it online!

A dyadic dfn whose left argument is the ns and right argument is ms.

How it works

{1⊥↑⍺{(⍵⍴0),⍳⍺}¨+\⍵}
{                  }  ⍺ = n's, ⍵ = m's
                +\⍵   Cumulative sum of offsets (M)
    ⍺{        }¨      Zip with n's
      (⍵⍴0),⍳⍺        ... to create M zeros followed by 1..n
   ↑                  Promote to matrix, filling zeros where necessary
 1⊥                   Sum column-wise
\$\endgroup\$
  • \$\begingroup\$ Hey Bubbler can you improve this J solution +/@(((,~#&0)~1+i.)"0~+/\)? Try it online! \$\endgroup\$ – Jonah Oct 26 at 3:45
  • \$\begingroup\$ @Jonah I couldn't shorten that one specifically, but I could come up with a shorter solution using a different approach. \$\endgroup\$ – Bubbler Oct 30 at 7:46
  • \$\begingroup\$ full program: 1⊥0⌈↑a-⍨⍳¨⎕+a←+\⎕ \$\endgroup\$ – ngn Oct 31 at 23:05
  • \$\begingroup\$ 1⊥↑⎕{+\⍸⍵⍺}¨+\⎕ in some future version of dyalog, with ⎕io←0 \$\endgroup\$ – ngn Oct 31 at 23:08
2
\$\begingroup\$

05AB1E, 13 bytes

ηOÅ0s€L‚ø€˜0ζO

Takes two separated lists. The list of positions \$(m_0, m_1, m_2, ...)\$ as first input and list of values \$(n_0, n_1, n_2, ...)\$ as second input.

Try it online or verify all test cases.

Explanation:

η        # Get all prefixes of the (implicit) input-list of positions
         #  i.e. [0,1,5] → [[0],[0,1],[0,1,5]]
 O       # Sum each inner list
         #  → [0,1,6]
  Å0     # Convert each of the inner values into a list of 0s of that length
         #  → [[],[0],[0,0,0,0,0,0]]
s        # Get the second (implicit) input-list of values
 L       # And create a list in the range [1,n] of each value
         #  i.e. [3,4,2] → [[1,2,3],[1,2,3,4],[1,2]]
‚        # Pair the two lists together
         #  → [[[],[0],[0,0,0,0,0,0]],[[1,2,3],[1,2,3,4],[1,2]]]
 ø       # Zip/transpose, swapping rows/columns
         #  → [[[],[1,2,3]],[[0],[1,2,3,4]],[[0,0,0,0,0,0],[1,2]]]
  €˜     # Flatten each inner pair to a single inner list
         #  → [[1,2,3],[0,1,2,3,4],[0,0,0,0,0,0,1,2]]
    0ζ   # Zip/transpose, swapping rows/column, with 0 as trailing filler
         #  → [[1,0,0],[2,1,0],[3,2,0],[0,3,0],[0,4,0],[0,0,0],[0,0,1],[0,0,2]]
      O  # Take the sum of each inner list
         #  → [1,3,5,3,4,0,1,2]
         # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

PHP, 93 bytes

for(;$n=$argv[++$i+1];)for($p+=$argv[$i++];$$i<$p+$n;)$l[$$i]+=$$i++<$p?0:$$i-$p;print_r($l);

Try it online!

Input is a flat list of m0,n0,m1,n1,... passed by command arguments ($argv) and output is string representation of L.

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

Python 3, 144 119 118 111 110 106 bytes

def f(m,n):
 p=k=0;l=[]
 for i,j in zip(n,m):p+=j;l+=[0]*(p+i-len(l));exec("l[~k]+=i-k;k+=1;"*i)
 return l

Try it online!

Thanks to:
-@mypetlion for saving me 25 bytes

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

Wolfram Language (Mathematica), 62 60 56 53 50 bytes

Plus@@PadRight[a=0;Ramp[Range[(a+=#)+#2]-a]&@@@#]&

Try it online!

-3 with guarantee that input is non-empty.

Takes a list of pairs as the argument.

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

Ruby, 92 88 84 bytes

->x{n,l=0,[];x.map{|a,b|0.upto(b-1+n+=a){|i|l[i]||=0};1.upto(b){|i|l[-i]+=1+b-i}};l}

Input is a list of pairs, in the form [[m1, n1], [m2, m2], ...].

The approach is pretty much the algorithm as described.

Golfy tricks I've used include:

  • l[i]||=0 setting the value for L to 0 if it isn't already set
  • That's pretty much it.

Thanks to Value Ink for

Try it online!

Ruby can be pretty terse. When the version with numbered block parameters comes out, this can be reduced by a few bytes to this (note the @1 ins:

->x{n,l=0,[];x.map{|a,b|0.upto(b-1+n+=a){l[@1]||=0};1.upto(b){l[-@1]+=1+b-@1}};l}
\$\endgroup\$
  • \$\begingroup\$ Why are you ending your map block with returning l and then taking [-1], when you can just do ;l after the map? Like so. \$\endgroup\$ – Value Ink Oct 26 at 23:46
  • \$\begingroup\$ Two more things I thought up: n,*l=0 will initiate l to the empty array for -2 bytes, and you can wrap the n+=a into your upto call like so: 0.upto(b-1+n+=a) \$\endgroup\$ – Value Ink Oct 26 at 23:51
2
\$\begingroup\$

J, 20 bytes

+/@(0>.>:@i.@+-])+/\

Try it online!

I guess this is quite different from both Galen Ivanov's and Jonah's answers. A dyadic train that takes ns as left argument and ms as right.

One trick was to avoid (...)"0 (apply to each item) in favor of ...@+. The conjunction u@v has the effect of u@:v"v. The rank-forcing effect is usually not desirable when v is an arithmetic verb, but it works perfectly here.

How it works

+/@(0>.>:@i.@+-])+/\  Left(n): range generators ex) 3 4 2
                      Right(m): offsets ex) 0 1 5
                 +/\  cm: Cumulative sum of offsets ex) 0 1 6
             +        Add n and cm element-wise ex) 3 5 8
          i.@         Generate 0..x-1 for each x above
                      ex) 0 1 2;0 1 2 3 4;0 1 2 3 4 5 6 7
       >:@            Increment each value
                      ex) 1 2 3;1 2 3 4 5;1 2 3 4 5 6 7 8
                      (Implicit) Form a 2D array, padding with 0s where needed
              -]      Subtract each item of cm from each row of above
                      ex)  1  2  3  0  0  0  0  0
                           0  1  2  3  4 -1 -1 -1
                          -5 -4 -3 -2 -1  0  1  2
    0>.               Max with 0; Change negative numbers to 0s
+/@(            )     Take sum in column direction
\$\endgroup\$
  • \$\begingroup\$ very nice @Bubbler \$\endgroup\$ – Jonah Oct 30 at 11:51
1
\$\begingroup\$

Bash, 77 bytes

for N;{
b=($N)
for((i=0,p+=b;i<p+b[1];a[i]+=++i>p?i-p:0)){ :;}
}
echo ${a[@]}

Try it online!

I couldn't port my first Zsh answer directly, since ${a[@]/#%/0} doesn't work in Bash. So instead of fixing the empty elements at the end, I set all the elements with a[i]+=0 along the way. In the end, this strategy works out better for Zsh anyway!

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

C, 204 196 195 192 185 bytes

*c(m,n,q,x,p,z)int*m,*n;{int i,j,*a=malloc(4);for(i=p=z=0;m[i]+1;i++){q=n[i]+(p+=m[i]);a=realloc(a,8*((x=z)>q?z:(z=q)));bzero(a+x,(z-x)*8);for(j=p;j<q;j++)a[j]+=j-p+1;}a[z]--;return a;}

De-golfed version:

* count (m, n, size_of_array, pointer_into_array, previous_size_of_array, final_element_counted_to) //all but m and n are implicitly int - return type of function is implicitly int pointer
     int* m, * n;
{
  pointer_into_array = size_of_array = 0;
  int* array = malloc(sizeof(int)); //get a pointer so we can realloc later
  for (int i = 0; m[i] + 1; i++) { //iterate through m and n, stopping at -1 sentinel value
    final_element_counted_to = n[i] + (pointer_into_array += m[i]); //update pointer, get final element counted to on this pair
    array = realloc(array, sizeof(int) * 2 * ((previous_size_of_array = size_of_array) > final_element_counted_to ? size_of_array : (size_of_array = final_element_counted_to) + 1)); //reallocate array to size of max(size_of_array, final_element_counted_to+1) * sizeof(int) * 2 [multiplying by 2 for the final statement of a[z] = -1]
    bzero(array + previous_size_of_array, (size_of_array - previous_size_of_array) * sizeof(int) * 2); //initialises new memory to zero
    for(int j = pointer_into_array; j < final_element_counted_to; j++) //do the actual counting + adding
      array[j] += j - pointer_into_array + 1;
  }
  array[size_of_array]--; //make sure it's terminated by -1
  return array;
}

Try it online!

Function c takes two arguments (rest are for free declaration) m and n, both -1 terminated arrays corresponding respectively to the two separate lists for m and n. It returns a -1 terminated array.

Please note that this requires sizeof(int) to be 4, and also requires the non-standard and deprecated but widely-implemented function bzero.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Golf! You can use the header and footer sections of TIO to store boilerplate code: like this. They do not count towards your byte score. \$\endgroup\$ – Arnauld Oct 26 at 17:39
  • \$\begingroup\$ And it seems like you current score is actually 204. \$\endgroup\$ – Arnauld Oct 26 at 17:39
  • \$\begingroup\$ 171 bytes \$\endgroup\$ – ceilingcat Oct 30 at 8:00
1
\$\begingroup\$

K (ngn/k), 30 bytes

{+/0^(1+!'y)@'-n-\:!*|y+n:+\x}

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ i tried to beat this with "amend" but i couldn't. my best is: {@[&0|/y+j;i+j:+\x;+;1+i:!'y]} \$\endgroup\$ – ngn Oct 31 at 23:39
1
\$\begingroup\$

Clojure, 170 Bytes

(fn [a](reduce #(mapv +(concat %1(repeat 0))%2)(mapv (fn [[x y]](concat(repeat x 0)(range 1(+ 1 y))))(reduce #(conj %1(mapv +[(nth(last %1)0)0]%2))[(first a)](rest a)))))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Hello and welcome to PPCG! \$\endgroup\$ – Jonathan Frech Oct 30 at 19:20
0
\$\begingroup\$

Java, 642 Bytes

This I think is kind of awful, but doing it with Java who knows what I was expecting. If someone could help me make this better I would really appreciate that, a bunch of bytes are taken up dealing with the fact that combiner can get two different length lists and need to add them, and also with the fact that there is a type needed for the BiConsumer lambda. I think there are a few ways, but it's getting late...

Input is n, expected to be an array of arrays.

    IntStream.range(0, n.length).mapToObj((x) -> new int[] { n[x][0] + (x > 0 ? n[x - 1][0] : 0), n[x][1]})
            .map((v) -> IntStream.range(0, v[0] + v[1]).map((x) -> x >= v[0] ? 1 + x - v[0] : 0).toArray())
            .collect(Collector.of(
                () -> new ArrayList<>(),
                (BiConsumer<List<Integer>, int[]>) (l, v) -> IntStream.range(0, Math.max(l.size(), v.length)).forEach((i) -> {
                    if (i >= l.size()) l.add(0);
                    if (i < v.length) l.set(i, l.get(i) + v[i]);
                }),
                (a, b) -> {
                    while (a.size() > b.size()) b.add(0);
                    while (b.size() > a.size()) a.add(0);
                    return IntStream.range(0, a.size()).mapToObj((i) -> a.get(i) + b.get(i)).collect(Collectors.toList());
                },
                Characteristics.IDENTITY_FINISH
            ));

Improved and golf'd by Kevin Cruijssen:

n->IntStream.range(0,n.length).mapToObj(x->new int[]{n[x][0]+(x>0?n[x-1][0]:0),n[x][1]}).map(v->IntStream.range(0,v[0]+v[1]).map(x->x<v[0]?0:1+x-v[0]).toArray()).collect(Collector.of(()->new Stack<>(),(java.util.function.BiConsumer<List<Integer>,int[]>)(l,v)->IntStream.range(0,Math.max(l.size(),v.length)).forEach(i->{if(i>=l.size())l.add(0);if(i<v.length)l.set(i,l.get(i)+v[i]);}),(a,b)->{while(a.size()>b.size())b.add(0);while(b.size()>a.size())a.add(0);return IntStream.range(0,a.size()).mapToObj(i->a.get(i)+b.get(i)).collect(Collectors.toList());},Collector.Characteristics.IDENTITY_FINISH))
\$\endgroup\$
  • \$\begingroup\$ How does this receive input? And surely you can golf away pretty much all the whitespace at least \$\endgroup\$ – Jo King Oct 25 at 5:32
  • \$\begingroup\$ I'm not sure how you ended up with 581 bytes, because your current code above is 842 bytes and still missing required imports and n-> as input. Removing all whitespaces; parenthesis around the (L)-> everywhere; changing ArrayList to Stack; reversing some checks so we could use a<b?0:1 instead of a>=b?1:0; and some other basic golfs, I end up at 642 bytes. I'm sure this can be a lot shorter without the stream builtins, though. \$\endgroup\$ – Kevin Cruijssen Oct 25 at 9:56
  • 2
    \$\begingroup\$ Anyway, welcome to CGCC! If you haven't seen them yet tips for golfing in Java and tips for golfing in <all languages> might both be interesting to read through. Enjoy your stay! :) \$\endgroup\$ – Kevin Cruijssen Oct 25 at 9:57
  • \$\begingroup\$ To get 581 bytes I minified with codebeautify.org/javaviewer and pasted into mothereff.in/byte-counter . Should I be pasting the minified version into the code area when posting here? \$\endgroup\$ – Disco Mike Oct 25 at 16:42
  • \$\begingroup\$ I realize now that I excluded (n) -> though \$\endgroup\$ – Disco Mike Oct 25 at 16:43

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.