# Circularly moving sum

Inspired by a question at Stack Overflow.

Given a non-empty array of integers x and a positive integer n, compute the sum of each sliding block of length n along the array x, circularly filling the missing values at the left with values from the right as follows:

• the first block contains the first entry of x, preceded by n-1 circularly shifted entries;
• the second block has the first and second entries of x, preceded by n-2 circularly shifted entries; and so on.

The output array y has the same size as x. It is possible for n to exceed the length of x, and then the values of x are circularly reused several times.

# Examples

### Example 1 (values are reused only once)

x = [2, 4, -3, 0, -4]
n = 3


give as output

y = [-2, 2, 3, 1, -7]


where

• -2 is the sum of the block [0, -4, 2] (the first two values come from the circular shifting)
• 2 is the sum of [-4, 2, 4] (the first value comes from the circular shifting)
• 3 is the sum of [2, 4, -3] (no circular shifting necessary anymore)
• 1 is the sum of [4, -3, 0]
• -7 is the sum of [-3, 0, -4].

### Example 2 (values are reused several times)

x = [1, 2]
n = 5


give

y = [7, 8]


where

• 7 is the sum of the block [1, 2, 1, 2, 1] (the first four values have been circularly reused)
• 8 is the sum of the block [2, 1, 2, 1, 2] (the first three values have been circularly reused)

• The algorithm should work for arrays of arbitrary size and for arbitrary integer values. It is acceptable if the program is limited by data type or memory restrictions; but positive as well as negative integer values must be handled.
• Input/output can be taken/produced by any reasonable means.
• Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
• Shortest code in bytes wins.

# Test cases

x, n, -> y

[2, 4, -3, 0, -4], 3          ->  [-2, 2, 3, 1, -7]
[1, 2], 5                     ->  [7, 8]
, 7                        ->  
[-5, 4, 0, 1, 0, -10, -4], 4  ->  [-19, -15, -5, 0, 5, -9, -13]
[-5, 4, 0, 1, 0, -10, -4], 1  ->  [-5, 4, 0, 1, 0, -10, -4]
[-2, -1, 0, 1, 2, 3], 5       ->  [4, 3, 2, 1, 0, 5]
[-10, 0, 10], 4               ->  [-10, 0, 10]

• Bah, why did you have to use preceding entries? – Neil Aug 27 '17 at 10:54

# Jelly, 5 bytes

ṙC€}S


Try it online!

### How it works

ṙC€}S  Main link. Arguments: A (array), n (positive integer)

}   Apply the link to the left to the right argument (n).
C€      Complement each; map (z -> 1-z) over [1, ..., n], yielding [0, ..., 1-n].
ṙ      Rotate A 0, ..., 1-n units to the left (i.e., 0, ..., n-1 units to the
right), yielding a 2D array.
S  Take the sum of the rows.


# MATL, 11109 7 bytes

3 Bytes saved thanks to @Luis!

:gyn&Z+


The first input is the size of the window and the second input is the array

Try it at MATL Online

Explanation

       % Implicitly grab the first input (n)
%     STACK: { 3 }
:      % Create the array [1...n]
%     STACK: { [1, 2, 3] }
g      % Convert it to a logical array, yielding an array of 1's of length n
%     STACK: { [1, 1, 1] }
y      % Implicitly grab the second input and duplicate it
%     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], [2, 4, -3, 0, -4]}
n      % Determine the length of the array
%     STACK: { [2, 4, -3, 0, -4], [1, 1, 1], 5}
&Z+    % Perform circular convolution
%     STACK: { [-2, 2, 3, 1, -7] }
% Implicitly display the result


# Mathematica, 29 bytes

RotateLeft[#,1-n]~Sum~{n,#2}&


Or the same length:

ListConvolve[1~Table~#2,#,1]&


## CJam (16 bytes)

{_2$*ew1fb\,~)>}  Online test suite. This is an anonymous block (function) which takes the array and the length on the stack and leaves an array on the stack. ### Dissection { e# Declare a block _2$*  e#   Repeat the array n times: this guarantees having enough windows even
e#   if x is only a single element
ew    e#   Take each window of n elements
1fb   e#   Sum each of the windows
\,~)  e#   Compute -n
>     e#   Take the last n elements of the array of sums
}


a#n|l<-length a=[sum[a!!mod j l|j<-[i-n..i-1]]|i<-[1..l]]


Try it online!

Just some index looping and accessing the input list at indices modulo the length of the list.

r=reverse
s#n=r$init[sum$take n$x++cycle(r s)|x<-scanr(:)[]$r s]


Try it online! Example usage: [2, 4, -3, 0, -4] # 3.

Using n succeeding instead of preceding entries could be 50 46 bytes (getting rid of the reverse at the beginning and the end):

s#n=init[sum$take n$x++cycle s|x<-scanr(:)[]s]


Try it online!

# Japt, 12 bytes

ËVo rÈ+UgE-Z


Try it online!

TIO doesn't support the Ë, so the TIO link won't work. Instead, try it here.

# Pyth, 18 16 bytes

Saved 2 bytes thanks to @FryAmTheEggman!

JEms<.>*JQ-JhdJl


Try it here or Verify all the test cases.

Fixed all the flaws at a cost of -6 bytes! Thanks a lot to Luis for making me understand the task in chat.

# Explanation (to be updated)

KEms<>_*QhK-lQhdKU - Full program.

KE                 - Assign the second input to a variable K.
m              U - Map over the range [0...len(first input)).
*QhK        - First input * (Second input + 1).
_            - Reverse.
>     -lQhd   - All the elements of the above after len(x)-current element-1
<          K   - Up until the second input.
s               - Sum.

• Might be a better way before reversing, trying to golf soon. – Mr. Xcoder Aug 27 '17 at 12:40
• Got 16 bytes but I feel like there should still be something shorter. – FryAmTheEggman Aug 27 '17 at 15:10
• @FryAmTheEggman Thanks. I feel it should be shorter but I cannot figure out how – Mr. Xcoder Aug 27 '17 at 16:01

# Java 8, 102 bytes

Lambda (curried) from int[] to lambda from Integer to int[]. Assign to Function<int[], Function<Integer, int[]>>.

a->n->{int l=a.length,o[]=new int[l],i=0,j;for(;i<l;i++)for(j=i-n;j++<i;)o[i]+=a[(j%l+l)%l];return o;}


Try It Online

## Ungolfed lambda

a ->
n -> {
int
l = a.length,
o[] = new int[l],
i = 0,
j
;
for (; i < l; i++)
for (j = i - n; j++ < i; )
o[i] += a[(j % l + l) % l];
return o;
}


(j % l + l) % l computes a nonnegative remainder for any j. Taken from here.

# C, 91 bytes

i,j,k,s;f(a,l,n)int*a;{for(i=0;i<l;printf("%d ",s))for(j=n*l+i++,k=n,s=0;k--;)s+=a[j--%l];}


Try it online!

# Octave, 53 bytes

@(x,n)shift(imfilter(x,+!!(1:n),'circular'),fix(n/2))


Try it online!

• The imfilter function with option circular computes the circular convolution at the center of window so the result should be shifted.

# 05AB1E, 10 bytes

.×ŒùOR¹g£R


Try it online!

Explanation

.×           # repeat input_1 input_2 times
Œù         # push all sublists of size input_2
O        # sum each
R       # reverse the list
¹g£    # take the first len(input_1) items
R   # reverse the list


# Perl 6, 42 39 bytes

{@^a;[«+»] map {@a.rotate(-$_)},^$^b}


Try it online!

My first Perl 6 entry. Can probably be improved.

• Note that you can sometimes reduce the length by using a pointy block with sigilless variables rather than a block with placeholder parameters ->\a,\b{[«+»] map {a.rotate(-$_)},^b} Note that it doesn't in this case but it would if there was another instance of $b in the code. – Brad Gilbert b2gills Mar 20 '18 at 17:51

# Kotlin, 141140 138 bytes

Just a first go

## Submission

fun c(a:List<Int>,n:Int):List<Int>{
return (0..(a.size-1)).map{var t=0
for (o in 0..(n-1)){var i=it-o
while(i<0) {i+=a.size};t+=a[i]}
t}}


## Beautified

fun c(a: List<Int>, n: Int): List<Int> {
return (0..(a.size - 1)).map {    // Iterate over the items
var t = 0                     // Start the total at 0
for (o in 0..(n - 1)) {       // Start at the item, go over the window backwards
var i = it - o            // -------------------------
while (i < 0) {           //  Make the index in range
i += a.size           //
}                         // -------------------------
t += a[i]                 // Add the item to the total
}
t                             // Return the total
}
}


# Edits

• Removed newline on before last closing bracket

# Röda, 52 bytes

f a,n{(a*n)|slide n|tail#a*n|{head n|sum}while open}


Try it online!

Explanation:

f a,n{
(a*n)|    /* Push the items in a n times to the stream */
slide n|  /* Create a sliding block of length n */
tail#a*n| /* Push the last n*len(a) values in the stream to the stream */
{         /* While there are elements in the stream (stream is open): */
head n| /*   Pull n values from the stream */
sum     /*   Sum them and push the sum to the stream */
} while open
}


# JavaScript ES6 80 78 bytes

x=>n=>x.map((_,i)=>eval('for(L=x.length,N=0,j=++i-n;j<i;j++)N+=x[(j%L+L)%L]'))


2 bytes saved thanks to Neil

### Usage:

f=x=>n=>x.map((_,i)=>eval('for(L=x.length,N=0,j=++i-n;j<i;j++)N+=x[(j%L+L)%L]'))

f([2, 4, -3, 0, -4])(3)

• The ,N looks unnecessary to me... – Neil Aug 27 '17 at 15:16
• @Neil You're right, thanks – Bálint Aug 27 '17 at 16:51

# Perl 5, 66 + 1 (-a) = 67 bytes

$n=pop@F;$,=$";say map{$q=$c++;$t=0;$t+=$F[$q--%@F]for 1..$n;\$t}@F


Try it online!

# Python 2, 69 61 bytes

- 8 bytes Thanks a lot @muru

lambda x,n:[sum((x[-n+1:]+x*n)[i:i+n])for i in range(len(x))]


Try it online!

Explanation:

First we need to ensure there is enough numbers on the left of the original list, this is acheived by the x*n+x part.

For, example: [2,4,-3,0,4],5:

                   ,2,4,-3,0,-4
....-4,2,4,-3,0,-4,2,4,-3,0,-4


Then we shall reverse the list:

 <original->
-4,0,-3,4,2, -4,0,-3, 4........
<-2's block->


Next we obtain corresponding blocks for each element by [len(x)+~i:][:n]. The slice will be reverse i.e. 2 will gain a block: [2,-4,0,-3,4] which is reverse of the expected [4,-3,0,-4,2], but we need the sum after all. So, this works. :)

• Not sure why you have to reverse first? Can't you modify the slices later on in the reverse direction instead? – Mr. Xcoder Aug 27 '17 at 12:36
• @Mr.Xcoder I do think there is a way but this way was less tedious so I sticked with this... :D – officialaimm Aug 27 '17 at 12:38
• I think x[-n+1:]+x*n should give you the list with sufficient padding on either side, without having to reverse (lambda x,n:[sum((x[-n+1:]+x*n)[i:i+n])for i in range(len(x))]) – muru Aug 28 '17 at 10:43
• @muru Did you just edit it? Now, it works. Thanks a lot! – officialaimm Aug 28 '17 at 10:52

# R, 10193 89 bytes

function(x,n,w=sum(x|1)){for(j in 1:w)F=c(F,sum(c(tail(rep(x,n),n-1),x)[1:n+j-1]))
F[-1]}


Try it online!

# K (oK), 18 bytes

Solution:

{+/+y':(1-y+#x)#x}


Try it online!

Examples:

{+/+y':(1-y+#x)#x}[1 2;5]
7 8
{+/+y':(1-y+#x)#x}[-5 4 0 1 0 -10 -4;4]
-19 -15 -5 0 5 -9 -13
{+/+y':(1-y+#x)#x}[-10 0 10;4]
-10 0 10


Explanation:

Was about to post a 31 byte solution then I remembered that oK has a built-in for sliding windows...

{+/+y':(1-y+#x)#x} / the solution
{                } / lambda with implicit x and y parameters
#x  / take (#) from list x
(    #x)    / length of x
y+       / add y (window size)
1-         / subtract from 1 to give a negative
y':            / sliding window of size y
+               / flip
+/                / sum


Bonus:

The 31 byte solution that also works in K4:

q)k){+/+x#y#'|+(:':\|(1-y+x:#x)#x)}[2 4 -3 0 -4;3]
-2 2 3 1 -7