19
\$\begingroup\$

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 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]
\$\endgroup\$
  • 2
    \$\begingroup\$ 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]? \$\endgroup\$ – Kevin Cruijssen Feb 1 '18 at 8:53
  • 2
    \$\begingroup\$ @KevinCruijssen Can you please edit in for me? Those are some good test cases, but I am on mobile now ;) Thanks! \$\endgroup\$ – Mr. Xcoder Feb 1 '18 at 8:57

25 Answers 25

12
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is there any difference between an "oblique diagonal" and a "diagonal”? \$\endgroup\$ – Luis Mendo Feb 1 '18 at 15:01
  • \$\begingroup\$ @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. \$\endgroup\$ – Galen Ivanov Feb 1 '18 at 15:22
  • 1
    \$\begingroup\$ Ah, thanks. So that's what's usually called anti-diagonals \$\endgroup\$ – Luis Mendo Feb 1 '18 at 16:27
  • 2
    \$\begingroup\$ You could replace ,/\ with ]\ \$\endgroup\$ – miles Feb 1 '18 at 18:09
  • \$\begingroup\$ @miles Yes, of course! Thank you! \$\endgroup\$ – Galen Ivanov Feb 1 '18 at 18:19
9
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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]

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

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`
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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]

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

05AB1E, 12 bytes

)IŒIùvyNÅ0ì+

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Weird, no zipping? Neat. \$\endgroup\$ – Magic Octopus Urn Feb 2 '18 at 19:21
5
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "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! \$\endgroup\$ – Kevin Cruijssen Feb 1 '18 at 10:21
2
\$\begingroup\$

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

Japt, 13 12 bytes

-1 byte thanks to @ETHproductions

ãV
ËEÆÃcDÃyx

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ max(i,n-1) instead of [i,n-1][n>i]. \$\endgroup\$ – Laikoni Feb 1 '18 at 13:06
0
\$\begingroup\$

Perl 5, 63 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Clojure, 72 bytes

#(let[R(range 1(inc(count %)))](map *(map min(repeat %2)R(reverse R))%))
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech May 24 at 22:49

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.