24
\$\begingroup\$

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)

Additional rules

  • 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]
[2], 7                        ->  [14]
[-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]
\$\endgroup\$
  • 6
    \$\begingroup\$ Bah, why did you have to use preceding entries? \$\endgroup\$ – Neil Aug 27 '17 at 10:54

20 Answers 20

3
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

MATL, 11 10 9 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
\$\endgroup\$
6
\$\begingroup\$

Mathematica, 29 bytes

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

Or the same length:

ListConvolve[1~Table~#2,#,1]&
\$\endgroup\$
6
\$\begingroup\$

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
}
\$\endgroup\$
4
\$\begingroup\$

Haskell, 57 bytes

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.

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

Haskell, 69 65 64 bytes

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!

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

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.

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

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.
\$\endgroup\$
  • \$\begingroup\$ Might be a better way before reversing, trying to golf soon. \$\endgroup\$ – Mr. Xcoder Aug 27 '17 at 12:40
  • \$\begingroup\$ Got 16 bytes but I feel like there should still be something shorter. \$\endgroup\$ – FryAmTheEggman Aug 27 '17 at 15:10
  • \$\begingroup\$ @FryAmTheEggman Thanks. I feel it should be shorter but I cannot figure out how \$\endgroup\$ – Mr. Xcoder Aug 27 '17 at 16:01
2
\$\begingroup\$

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.

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

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!

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

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.
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 42 39 bytes

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

Try it online!

My first Perl 6 entry. Can probably be improved.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Brad Gilbert b2gills Mar 20 '18 at 17:51
2
\$\begingroup\$

Kotlin, 141 140 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
    }
}

TryItOnline

Edits

  • Removed newline on before last closing bracket
\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ The ,N looks unnecessary to me... \$\endgroup\$ – Neil Aug 27 '17 at 15:16
  • \$\begingroup\$ @Neil You're right, thanks \$\endgroup\$ – Bálint Aug 27 '17 at 16:51
1
\$\begingroup\$

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!

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

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. :)

\$\endgroup\$
  • \$\begingroup\$ Not sure why you have to reverse first? Can't you modify the slices later on in the reverse direction instead? \$\endgroup\$ – Mr. Xcoder Aug 27 '17 at 12:36
  • \$\begingroup\$ @Mr.Xcoder I do think there is a way but this way was less tedious so I sticked with this... :D \$\endgroup\$ – officialaimm Aug 27 '17 at 12:38
  • 1
    \$\begingroup\$ 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))]) \$\endgroup\$ – muru Aug 28 '17 at 10:43
  • 1
    \$\begingroup\$ @muru Did you just edit it? Now, it works. Thanks a lot! \$\endgroup\$ – officialaimm Aug 28 '17 at 10:52
1
\$\begingroup\$

R, 101 93 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!

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

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
\$\endgroup\$

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.