Column-wise summation of overlapping slices

Question

Task

Given a list of integers L and another integer s, the goal is to compute the column-wise sums of all s-length (potentially overlapping) slices of L, while pertaining their positions relative to L (see below).

Definitions

The s-length (overlapping) slices of the list L are all the contiguous subsequences (without wrapping) of L that are of length s.

In order to pertain the positions of the slices s relative to L, you can imagine building a "ladder", where each slice s_i has an offset of i positions from the beginning.

---

Specs

• s is an integer higher than 1 and strictly smaller than the length of L.
• L will always contain at least 3 elements.
• You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (in bytes) for every language wins.

Examples and Test Cases

Here is a worked example:

[1, 2, 3,  4,  5,  6,  7,  8, 9], 3

[1, 2, 3]
   [2, 3,  4]
      [3,  4,  5]
          [4,  5,  6]
              [5,  6,  7]
                  [6,  7,  8]
                      [7,  8, 9]
-------------------------------- (+)  | column-wise summation
[1, 4, 9, 12, 15, 18, 21, 16, 9]

And some more test cases:

[1, 3, 12, 100, 23], 4         -> [1, 6, 24, 200, 23]
[3, -6, -9, 19, 2, 0], 2       -> [3, -12, -18, 38, 4, 0]
[5, 6, 7, 8, 2, -4, 7], 3      -> [5, 12, 21, 24, 6, -8, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9], 3 -> [1, 4, 9, 12, 15, 18, 21, 16, 9]
[1, 1, 1, 1, 1, 1, 1], 6       -> [1, 2, 2, 2, 2, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9], 6 -> [1, 4, 9, 16, 20, 24, 21, 16, 9]

Answer 1

J, 11, 9 8 bytes

-1 byte thanks to miles!

[:+//.]\

How it works?

The left argument is s, the right one - L

]\ - splits L into sublists with length s

/. - extracts the oblique diagonals (anti-diagonals)

+/ - adds them up

[: - makes a fork from the above verbs

Here's an example J session for the first test case:

   a =. 1 2 3 4 5 6 7 8 9

   ] 3 ]\ a 
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9

   ] </. 3 ]\ a 
┌─┬───┬─────┬─────┬─────┬─────┬─────┬───┬─┐
│1│2 2│3 3 3│4 4 4│5 5 5│6 6 6│7 7 7│8 8│9│
└─┴───┴─────┴─────┴─────┴─────┴─────┴───┴─┘

   ] +//. 3 ]\ a 
1 4 9 12 15 18 21 16 9

Try it online!

Answer 2

Haskell, 59 56 bytes

s#n=[x*minimum[n,i,length s+1-max i n]|(i,x)<-zip[1..]s]

Try it online!

Defines a function (#) which takes a list s and and a number n as arguments.

This is based on the observation that for s = [1, 2, 3, 4, 5, 6, 7, 8, 9] and n = 3

[1, 2, 3]
   [2, 3, 4]
      [3, 4, 5]
         [4, 5, 6]
            [5, 6, 7]
               [6, 7, 8]
                  [7, 8, 9]
---------------------------- (+)
[1, 4, 9,12,15,18,21,16, 9]

is the same as

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 3, 3, 3, 3, 2, 1]
---------------------------- (*)
[1, 4, 9,12,15,18,21,16, 9]

To generate this initially increasing, then constant and finally decreasing list, we can start with

[minimum[i, length s + 1 - i] | i<-[1..length s]]

which yields [1, 2, 3, 4, 5, 4, 3, 2, 1]. Adding n as additional constraint into the minimum expression yields the correct list [1, 2, 3, 3, 3, 3, 3, 2, 1]answer for n = 3, though for n = 6 (or in general any n > lengths s/2) the additional constraint length s + 1 - n is needed:

[minimum[i, n, length s + 1 - i, length s + 1 - n] | i<-[1..length s]]

or shorter:

[minimum[i, n, length s + 1 - max i n] | i<-[1..length s]]

For the pairwise multiplication [1..length s] is zipped with s, and because zip truncates the longer list to the length of the shorter one the infinite list [1..] can be used:

[x * minimum[i, n, length s + 1 - max i n] | (i,x)<-zip[1..]s]

Answer 3

APL (Dyalog Unicode), 19 14 bytes^SBCS

-5 thanks to ngn.

Anonymous tacit infix function taking s as left argument and L as right argument. Assumes ⎕IO (Index Origin) to be 0 as is default on many systems.

+⌿∘↑((0,⊢)\,/)

Try it online!

Explanation with example case [1,3,12,100,23]

(…) apply the following anonymous tacit function:

 ,/ overlapping windows of that size; [[1,3,12],[3,12,100],[12,100,23]]

 (…)\ cumulatively apply this tacit the following anonymous tacit function:

  ⊢ the right(most) argument

  0, with a zero on the left

Cumulative reduction means that we insert the function into every "space" between successive terms, working our way from right to left. For each "space", the function will discard the left argument but append an additional zero. Effectively, this appends as many zeros to each term as there are "spaces" to its left, so the first term gets zero spaces, the second gets one, and the third gets two: [[1,3,12],[0,3,12,100],[0,0,12,100,23]]

↑ up the rank by combining the lists into a single matrix, padding with zeros;
 ┌ ┐
 │1 3 12 0 0│
 │0 3 12 100 0│
 │0 0 12 100 23│
 └ ┘
∘ then
+⌿ sum vertically; [1,6,36,200,23]

Answer 4

JavaScript (ES6), 65 62 58 bytes

Saved 4 bytes thanks to @Shaggy

Takes input in currying syntax (a)(n).

a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i)))

Test cases

let f =

a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i)))

console.log(JSON.stringify(f([1, 3, 12, 100, 23]        )(4))) // [1, 6, 24, 200, 23]
console.log(JSON.stringify(f([3, -6, -9, 19, 2, 0]      )(2))) // [3, -12, -18, 38, 4, 0]
console.log(JSON.stringify(f([5, 6, 7, 8, 2, -4, 7]     )(3))) // [5, 12, 21, 24, 6, -8, 7]
console.log(JSON.stringify(f([1, 2, 3, 4, 5, 6, 7, 8, 9])(3))) // [1, 4, 9, 12, 15, 18, 21, 16, 9]
console.log(JSON.stringify(f([1, 1, 1, 1, 1, 1, 1]      )(6))) // [1, 2, 2, 2, 2, 2, 1]
console.log(JSON.stringify(f([1, 2, 3, 4, 5, 6, 7, 8, 9])(6))) // [1, 4, 9, 16, 20, 24, 21, 16, 9]

Answer 5

MATL, 8 bytes

YCPT&Xds

Try it online! Or verify all test cases.

Explanation

Consider inputs [1, 3, 12, 100, 23] and 4.

YC     % Implicit inputs: row vector L and number s. Create matrix of 
       % overlapping blocks of L with length s, where each block is a column
       % STACK: [  1   3;
                   3  12;
                  12 100;
                 100  23]
P      % Flip vertically
       % STACK: [100  23;
                  12 100;
                   3  12;
                   1   3]
&TXd   % Extract all diagonals, starting from bottom-left, and arrange them as
       % columns of a matrix, with zero padding
       % STACK: [1   3  12 100   0;
                 0   3  12 100  23]
s      % Sum of each column. Since s is less than the length of L, there are
       % at least two rows. Thus function `s` can be used instead of `Xs`.
       % Implicit display
       % STACK: [1   6  24 200  23]

Answer 6

Java 8, 83 bytes

L->s->{for(int i=0,l=L.length+1,t,u;++i<l;u=l-(s>i?s:i),L[i-1]*=t<u?t:u)t=i<s?i:s;}

That first test case (and the last two I've added) screwed me over multiple times, but it finally works now.. :D

Modifies the input array instead of returning a new one.

Explanation:

Try it online.

L->s->{                  // Method with int-array and int parameters, and no return-type
  for(int i=0,           //  Index-integer, starting at 0
      l=L.length+1,      //  The length of the input-array + 1
      t,u;               //  Two temp integers
      ++i<l              //  Loop `i` from 1 to the length (inclusive)
      ;                  //    After every iteration:
       u=l               //     Set temp integer `u` to the length plus 1,
          -(s>i?s:i),    //     minus the highest of `s` and `i`
       L[i-1]*=t<u?t:u)  //     And replace the item with the lowest of `t` and `u`
    t=i<s?i:s;}          //   Set temp integer `t` to the lowest of `i` or `s`

Answer 7

05AB1E, 12 bytes

)IŒIùvyNÅ0ì+

Try it online!

Answer 8

Jelly, 6 bytes

JṡṬS×ḷ

Try it online!

How it works

JṡṬS×ḷ  Main link. Left argument: A (array). Right argument: n (integer)

J       Indices; yield [1, ..., len(A)].
 ṡ      Split the indices into overlapping slices of length n.
  Ṭ     Untruth; map each array of indices to a Boolean vector, with 1's at the
        specified indices and 0's elsewhere.
        For example, [3, 4, 5] maps to [0, 0, 1, 1, 1].
   S    Sum the rows, essentially counting how many times each index appears in
        the arrays returned by the ṡ atom.
     ḷ  Left; yield A.
    ×   Multiply the counts to the left with the integers to the right.

Answer 9

Husk, 4 bytes

mΣ∂X

Try it online!

Uses the idea from Galen Ivanov's J answer.

Explanation

     -- implicit input number n and list s, e.g. s = [1,2,3,4,5,6] and n = 4 
   X -- get sublists of length n of list s           [[1,2,3,4],[2,3,4,5],[3,4,5,6]]
  ∂  -- anti-diagonals                               [[1],[2,2],[3,3,3],[4,4,4],[5,5],[6]]
mΣ   -- get the sum of each of the lists             [1,4,9,12,10,6]

Answer 10

Japt, 13 bytes

It took far too long to get this working when s > L/2!

Ë*°EmVUÊÄ-EwV

Try it

---

Explanation

                 :Implicit input of array U and integer V
Ë                :Map over each element at 0-based index E in U
 *               :  Multiply by
    m            :  The minumum of
  °E             :    E incremented,
     V           :    V,
          EwV    :    and the maximum of E & V
         -       :    subtracted from
      UÊÄ        :    the length of U plus 1

Answer 11

Wolfram Language (Mathematica), 42 bytes

Min[i,#2,l+1-{i,#2}]~Table~{i,l=Tr[1^#]}#&

Try it online!

Answer 12

Julia, 41 bytes

a\n=(a[L=end];a.*min(1:L,L:-1:1,n,L-n+1))

Try it online!

• Redefine \ operator.
• a[L=end] is a shorter alternative to L=length(a).
• Uses Laikoni's method.

Answer 13

Japt, 13 12 bytes

-1 byte thanks to @ETHproductions

ãV
ËEÆÃcDÃyx

Try it online!

Answer 14

Python 2, 68 66 bytes

-2 bytes thanks to Laikoni

lambda l,n:[v*min(n,i+1,len(l)-max(i,n-1))for i,v in enumerate(l)]

Try it online!

Answer 15

R, 52 51 bytes

function(l,s)l*pmin(s,x<-seq(l),y<-rev(x),y[1]+1-s)

Try it online!

This is equivalent to Laikoni's answer.

seq(l) produces the indices 1...length(l) since length(l)>1 (otherwise it would produce 1...l[1]). I save it as x, save its reverse as y, and take the first element of y (length(l)) to neatly port Laikoni's answer and save a byte!

Original answer, 52 bytes

function(l,s,L=sum(l|1)+1)l*pmin(s,x<-2:L-1,L-x,L-s)

Try it online!

The output is l elementwise multiplied by the minimum of s, the 1-based index of the element x, length(l)-x+1, and length(L)-s+1.

This is also equivalent to Laikoni's answer, using L-x instead of rev(x) as it's shorter.

Answer 16

APL+WIN, 25 bytes

Prompts for screen input of L followed by s

+/(1-⍳⍴z)⌽¨(⍴L)↑¨s←⎕,/L←⎕

Explanation:

L←⎕ prompt for screen input of L

s←⎕,/ prompt for screen input of s and create nested vector of successive s elements of L

(⍴L)↑¨ pad each element of the nested vector with zeros to the length of L

(1-⍳⍴z)⌽¨ incrementally rotate each element of the nested vector

+/ sum the elements of the nested vector

Answer 17

K (oK), 30 bytes

Solution:

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

Try it online!

Example:

{+/t,'(y':x),'|t:(!1-y-#x)#'0}[3 -6 -9 19 2 0;2]
3 -12 -18 38 4 0

Explanation:

Don't think I can compete with J on this one. Generate a list of zeros to be appended and prepended to the sliding-window list, then sum up:

{ t,'(y':x),'|t:(!(#x)+1-y)#'0 }[1 2 3 4 5 6 7 8 9;3]
(1 2 3 0 0 0 0 0 0
 0 2 3 4 0 0 0 0 0
 0 0 3 4 5 0 0 0 0
 0 0 0 4 5 6 0 0 0
 0 0 0 0 5 6 7 0 0
 0 0 0 0 0 6 7 8 0
 0 0 0 0 0 0 7 8 9)

Breakdown is as follows... though this still feels clumsy.

{+/t,'(y':x),'|t:(!1-y-#x)#'0} / the solution
{                            } / lambda taking x and y implicitly
                          #'0  / take (#) each (') zero
                 (       )     / do this together
                       #x      / count (#) length of x
                     y-        / take count away from length y
                   1-          / take that result from 1
                  !            / til, generate range to that number
               t:              / save in variable t
              |                / reverse it
            ,'                 / join with each
      (y':x)                   / sliding window size y over x
    ,'                         / join with each
   t                           / prepend t
 +/                            / sum up

Answer 18

Ruby, 62 bytes

->a,l{a.map.with_index{|x,i|x*[i+1,l,a.size-[l-1,i].max].min}}

Try it online!

Essentially a port of Arnauld's javascript answer, except that needing with_index is a lot more painful.

In the time it took for me to decide to actually submit this, I golfed down from this 70-byte version, which is closer to Dennis's algorithm.

->a,l{c=a.map{0};(0...a.size).each_cons(l){|h|h.map{|i|c[i]+=a[i]}};c}

Answer 19

Uiua, 14 bytes

⬚0/+⊐≡(⊂⊚)⇡⧻.◫

Try it!

⬚0/+⊐≡(⊂⊚)⇡⧻.◫
             ◫  # windows
          ⇡⧻.   # range of length
    ⊐≡(  )      # apply function to each row of both arrays, boxing as required
        ⊚       # where (n zeros)
       ⊂        # join
⬚0/+            # sum columns, filling missing elements with zero

Answer 20

Uiua, 8 bytes

×°⊚♭◫⊙°⊏

Try it: Uiua pad

The formatter automatically changes the deprecated ◫ to the newer ⧈∘, but still works as of Uiua 0.14.0. Explanation:

• ◫⊙°⊏ - We get the N-wise windows of the length-range of the input.

• °⊚♭ - Count how many times each integer appears in this array.

• × - Multiply this array by the input array.

Variations:

⊕/+⊞+∩⇡°⊟⊸△⧈∘
⊕/+/+°⍉°⊡⧈∘   # with thanks to janMakoso
⊕/+∩⌞⧈∘⊙°⊏
×°⊚♭⧈∘⊙°⊏
×°⊚♭◫⊙°⊏

Answer 21

Perl 5, 63 bytes

$b=<>;map{say$_*=$n+$b>@F?$n-$b<0?$i:--$i:$i<$b?++$i:$i;++$n}@F

Try it online!

Answer 22

C (gcc), 83 81 79 bytes

There are basically three "phases" to the manipulation of the list: ramp-up, sustain, and cool-off. As we go along the list, we will increase our factor until we reached some maximum. If a full run of slices can fit into the list, this maximum will be the same as the length of the slices. Otherwise, it will be the same as the number of slices that fit. At the other end, we will decrease the factor again, to land at 1 on the last element.

The length of the ramp-up and cool-down phases that bookend this plateau is one less than that maximum factor.

The ungolfed loops before combining them hopefully makes it clearer (R = length of ramp-up phase):

for (r = 1; r <= R; r++) L[r - 1] *= r;
for (; r < n - R; r++)   L[r - 1] *= R + 1;
for (; r < n; r++)       L[r - 1] *= n - r + 1;

Three loops is much too much, so deciding the factor based on r gives us the one loop (using s for R to save some bytes):

r;f(L,n,s)int*L;{for(r=0,s=2*s-1>n?n-s:s-1;r++<n;)*L++*=r>s?r<n-s?s+1:n-r+1:r;}

Try it online!

Answer 23

Perl, 45 44 bytes

Includes +4 for -ai Also notice that this code gives 2 perl warnings on startup. You can suppress these at the cost of one stroke by adding the X option

Give the mask length after the -i option and the array on one line on STDIN:

perl -ai4 -E 'say$_*grep$_~~[$^I..@F],$a..$^I+$a++for@F' <<< "1 3 12 100 23"

Just the code:

say$_*grep$_~~[$^I..@F],$a..$^I+$a++for@F

Answer 24

Clojure, 72 bytes

#(let[R(range 1(inc(count %)))](map *(map min(repeat %2)R(reverse R))%))

Answer 25

Pyt, 106 bytes

ĐŁĐ←⇹řĐ↔Đ04ȘĐ04Ș>Đ04Ș03Ș¬*07ȘážÁ*+04Ș⇹Đ3ȘĐ3Ș-⁺Đ4Ș⇹ŕĐ3Ș<Ь3Ș*3Ș*+⇹ĐŁ⑴04Ș3Ș⇹04Ș*Đ04ȘĐ04Ș<Đ04Ș*06ȘážÁ03Ș¬*++*

Takes L on the first line as an array, and takes s on the second line

Explanation:

                     Implicit input (L)
Đ                    Duplicate L
ŁĐ                   Get length of L (len) and push it twice
←                    Get s
⇹ř                   Push [1,2,...,len]
Đ↔Đ                  Push [len,...,2,1] twice
04ȘĐ                 Push 0, flip top 4 on stack, and duplicate top [1,2,...,len]
04Ș>                 Is [len,...,2,1]>[1,2,...,len] (element-wise) [boolean array]
Đ                    Duplicate top of stack                   
04Ș03Ș¬*             Pushes [1,2,...,ceil(len/2),0,...,0]
07ȘážÁ               Push 0, flip top seven on stack, and remove all 0s from stack
*                    Pushes [0,0,...,0,floor(len/2),floor(len/2)-1,...,1]
+                    Adds top two on stack element-wise

The top of the stack is now:
     [1,2,...,ceil(len/2),floor(len/2),...,2,1] (let's call it z)

04Ș                  Push zero and swap top four on stack
⇹                    Swap top two on stack
Đ3ȘĐ3Ș-⁺Đ4Ș⇹ŕĐ3Ș<Ь3Ș*3Ș*+     Pushes min of (len-s+1,s) [let's call it m]
⇹ĐŁ⑴04Ș3Ș⇹04Ș*                Pushes an array [m,m,...,m] with length len
Đ04ȘĐ04Ș<Đ04Ș*06ȘážÁ03Ș¬*++    Pushes element-wise min of [m,m,...,m] and z
*                              Element-wise multiplication of above with L

Try it online!

Answer 26

Python + numpy, 64 bytes

from pylab import *
lambda l,N:convolve(*ones((2,len(l)-N-1)))*l

Call this with l as the list, and N as the length.

Answer 27

C (gcc), 100 89 bytes, using -lm

• Saved eleven bytes thanks to ceilingcat.

j;f(L,l,s)int*L;{for(j=l;j--;L[j]*=j<s&j<l-s?1+j:j>s&j>l-s?l-j:fmin(s<l-j?s:l-j,l+1-s));}

Try it online!