Column-wise summation of overlapping slices

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 si 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 , 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]
• That first test case is annoying. ;) Simply because s is larger than L/2. Maybe add some more test cases where that is the case [1, 1, 1, 1, 1, 1, 1], 6 -> [1, 2, 2, 2, 2, 2, 1] or [1, 2, 3, 4, 5, 6, 7, 8, 9], 6 -> [1, 4, 9, 16, 20, 24, 21, 16, 9]? – Kevin Cruijssen Feb 1 '18 at 8:53
• @KevinCruijssen Can you please edit in for me? Those are some good test cases, but I am on mobile now ;) Thanks! – Mr. Xcoder Feb 1 '18 at 8:57

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)

[: - 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!

• Is there any difference between an "oblique diagonal" and a "diagonal”? – Luis Mendo Feb 1 '18 at 15:01
• @Luis Mendo - I think "oblique" means going from down-left to up-right in the case of the J adverb /., as opposed to the main diagonal going from up-left to down-right. – Galen Ivanov Feb 1 '18 at 15:22
• Ah, thanks. So that's what's usually called anti-diagonals – Luis Mendo Feb 1 '18 at 16:27
• You could replace ,/\ with ]\ – miles Feb 1 '18 at 18:09
• @miles Yes, of course! Thank you! – Galen Ivanov Feb 1 '18 at 18:19

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]

JavaScript (ES6), 6562 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]

• Does a=>n=>a.map((v,i)=>v*Math.min(++i,n,a.length+1-(n>i?n:i))) work for 58 bytes? – Shaggy Feb 1 '18 at 9:41
• @Shaggy Somehow, I knew there was something really stupid in my code but couldn't figure it out... Thanks a lot! – Arnauld Feb 1 '18 at 9:45

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

05AB1E, 12 bytes

)IŒIùvyNÅ0ì+

Try it online!

• Weird, no zipping? Neat. – Magic Octopus Urn Feb 2 '18 at 19:21

MATL, 8 bytes

YCPT&Xds

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]

APL (Dyalog Unicode), 19 14 bytesSBCS

-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]

• ⊢,⍨¨0⍴⍨¨⍳∘≢ -> {0,⍵}\ – ngn Feb 5 '18 at 23:51
• @ngn You always think of these clever reductions, but you really should post this separately. Btw, I find +⌿∘↑((0,⊢)\,/) more elegant. – Adám Feb 6 '18 at 6:08
• oh come on, this is a clear case of simplifying a part of a solution, not a new idea – ngn Feb 6 '18 at 7:28
• @ngn Meanwhile, solve this CMC! – Adám Feb 6 '18 at 7:46
• I'm not sure this is on-topic in the comments here, but why don't you use "each"? 2{(⊃⌽⍺),⊃⍵}/⊢ -> 2{⊃¨(⌽⍺)⍵}/⊢ – ngn Feb 6 '18 at 7:57

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.

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
• "It took far too long to get this working when s > L/2!" I had exactly the same. The other test cases are easy, but that first one (and the two I've added at the end) were annoying!.. +1 from me! – Kevin Cruijssen Feb 1 '18 at 10:21

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

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.

Japt, 13 12 bytes

-1 byte thanks to @ETHproductions

ãV
ËEÆÃcDÃyx

Try it online!

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!

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.

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

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

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]

C (gcc), 100 bytes

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

Try it online!

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!

• max(i,n-1) instead of [i,n-1][n>i]. – Laikoni Feb 1 '18 at 13:06

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}

Clojure, 72 bytes

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

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!

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.