Substring Sum Set

Question

Introduction

Let's observe this array: [3, 2, 4, 1, 1, 5, 1, 2].

Each element displays the length of the substring which must be summed up. Let's take a look at the first element of the above array:

[3, 2, 4, 1, 1, 5, 1, 2]
 ^

The element at the first index is 3, so we now take a substring of length three with the same index as the starting position:

[3, 2, 4]

When summed up, this results into 9, so the first element of the substring sum set is 9.

We do this for all the elements in the array:

3 -> [3, 2, 4]
2 -> [2, 4]
4 -> [4, 1, 1, 5]
1 -> [1]
1 -> [1]
5 -> [5, 1, 2]
1 -> [1]
2 -> [2]

You can see that the number 5 is a bit of a weird case. That number exceeds the length of the array:

[3, 2, 4, 1, 1, 5, 1, 2]
                ^  ^  ^  ^  ^

We'll ignore everything that exceeds the array, so we just use [5, 1, 2].

The last step is to sum everything up:

[3, 2, 4]     -> 9
[2, 4]        -> 6
[4, 1, 1, 5]  -> 11
[1]           -> 1
[1]           -> 1
[5, 1, 2]     -> 8
[1]           -> 1
[2]           -> 2

And that is the array that needs to be outputted:

[9, 6, 11, 1, 1, 8, 1, 2]

The Task

Given an non-empty array with positive (non-zero) integers, output the substring sum set. This is code-golf, so the submission with the smallest number of bytes wins!

Test cases

[1, 2, 3, 4, 5] -> [1, 5, 12, 9, 5]
[3, 3, 3, 3, 3, 3, 3, 3] -> [9, 9, 9, 9, 9, 9, 6, 3]
[5, 1, 2, 4, 1] -> [13, 1, 6, 5, 1]
[1] -> [1]

Answer 1

Jelly, 6 bytes

ṫJḣ"ḅ1

Try it online! or verify all test cases.

How it works

ṫJḣ"ḅ1  Main link. Argument: A (array)

 J      Index; yield the 1-based indices of A.
ṫ       Tail; map k to the postfix of A that begins with the k-th element.
  ḣ"    Vectorized head; for each k in A, truncate the corr. postfix to length k.
    ḅ1  Convert the resulting slices from base 1 to integer.

Answer 2

Python, 40 bytes

f=lambda x:x and[sum(x[:x[0]])]+f(x[1:])

Test it on Ideone.

Answer 3

Excel, 21 bytes

=SUM(OFFSET(A1,,,A1))

Open a new spreadsheet, put the test values in column A. Enter the formula in B1 and double click the cell handle to ride the range.

Answer 4

Python 3, 47 bytes

lambda X:[sum(X[i:i+k])for i,k in enumerate(X)]

Pretty straightforward implementation. Python's default behavior for slices that go past the end of the list was very convenient here.

Answer 5

Haskell, 34, 33 bytes

f l@(x:y)=sum(take x l):f y
f x=x

One byte saved by nimi.

Answer 6

JavaScript ES6, 50 bytes

a=>a.map((e,i)=>a.slice(i,i+e).reduce((a,b)=>a+b))

Pretty self-explanatory. It maps over each element in the array, getting the slice from that index through the index plus that element's value, and reduceing by adding.

f=
  a=>a.map((e,i)=>a.slice(i,i+e).reduce((a,b)=>a+b))

;[
  [3, 2, 4, 1, 1, 5, 1, 2],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3, 3, 3, 3, 3,],
  [5, 1, 2, 4, 1],
  [1]
].forEach(function(test){
  document.getElementById('p').textContent += test + ' => ' + f(test) + '\n';
});

<pre id="p"></pre>

Answer 7

J, 11 bytes

+/@{."_1]\.

Usage

   f =: +/@{."_1]\.
   f 3 2 4 1 1 5 1 2
9 6 11 1 1 8 1 2
   f 1 2 3 4 5
1 5 12 9 5

Explanation

+/@{."_1]\.  Input: A
        ]\.  Get each suffix of A from longest to shortest
   {."_1     For each value in A, take that many values from its corresponding suffix
+/@          Sum that group of values taken from that suffix
             Return the sums

Answer 8

JavaScript (ES6), 45

reduce beaten again!

a=>a.map((v,i)=>eval(a.slice(i,v+i).join`+`))

F=
a=>a.map((v,i)=>eval(a.slice(i,v+i).join`+`))

;[[3, 2, 4, 1, 1, 5, 1, 2],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3, 3, 3, 3, 3,],
  [5, 1, 2, 4, 1],
  [1]].forEach(t=>console.log(t+' -> '+F(t)))

Answer 9

Retina, 38 bytes

Byte count assumes ISO 8859-1 encoding.

\d+
$*
M!&`\b1(1)*(?<-1>,1+)*
M%`1
¶
,

Input and output are comma-separated lists.

Try it online! (The first line enables a linefeed-separated test suite.)

Answer 10

Mathematica 60 55 bytes

Tr@Take[#,UpTo@#&@@#]&/@Drop[#,t-1]~Table~{t,Length@#}&

eg

f = %; f /@ {{1, 2, 3, 4, 5}, {3, 3, 3, 3, 3, 3, 3, 3}, {5, 1, 2, 4, 1}, {1}}

(*    {{1, 5, 12, 9, 5}, {9, 9, 9, 9, 9, 9, 6, 3}, {13, 1, 6, 5, 1}, {1}}    *)

Thanks @MartinEnder for shaving off 5 bytes :)

Answer 11

05AB1E, 11 8 bytes

[D¬£Oˆ¦Ž

Explanation

[         # infinite loop
 D        # duplicate current list
  ¬       # get head of list
   £      # get that many elements from list
    O     # sum
     ˆ    # add to global array
      ¦   # remove first element of list
       Ž  # break if stack is empty
          # implicitly push and print global array

Try it online

Answer 12

Pyth, 8 bytes

.es:Qk+b

Test suite.

Translation of El's answer in Python.

Answer 13

Erlang, 69 bytes

f(A)->put(1,1),L=lists,[L:sum(L:sublist(A,put(1,get(1)+1),X))||X<-A].

Erlang's higher-order functions for lists do not receive the index of the current element. This uses the process dictionary to set the index of the current element.

Answer 14

Pyke, 12 7 bytes

FKo>i<s

Try it here!

        - o = 0
F       - for i in input:
  o     -    o+=1
   >    -    input[o:]
    i<  -   ^[:i]
      s -  sum(^)

Answer 15

VBA, 160 bytes

Function e(g())
Dim h()
k=LBound(g)
l=UBound(g)
ReDim h(k To l)
On Error Resume Next
For i=k To l
For j=i To i+g(i)-1
h(i)=h(i)+g(j)
Next
Next
e=h
End Function

Answer 16

Matricks, 25 bytes

Yay, finally a challenge I don't need new features for!

md{z:l-g:c;+c;q:c;};:1:l;

Run with: python matricks.py substring.txt [[<input>]] 0

Explanation:

m                  :1:l;   #loop over entire input
                           #set each value to...
 d{               }        #the sum of...
   z:l-g:c:+c;q:c;         #the input cropped to
                           #the length of the value in the cell

Answer 17

Pyth, 6 bytes

ms<~tQ

Test suite

This is a different solution from any others so far. It loops over the input, slicing an summing the initial values, then removing the first element of the stored input, and repeat.

Explanation:

ms<~tQ
ms<~tQdQ    Implicit variable introduction
            Implicit: Q = eval(input())
m      Q    Map d over the input, Q
  <  Qd     Take the first d elements of Q
 s          Sum them
   ~tQ      Afterwards, set Q to the tail of Q, removing the first element.

Answer 18

Julia, 39 bytes

!x=x!=[]?[take(x,x[])|>sum;!x[2:end]]:x

Try it online!

Answer 19

F#, 84 82 bytes

let f(A:int[])=[for i in 0..A.Length-1->Seq.skip i A|>Seq.truncate A.[i]|>Seq.sum]

Answer 20

JavaScript (ES6) - 79 Bytes

A recursive solution that does not use any of the Array methods:

f=([a,...t],n)=>a&&n?a+f(t,n-1):0;g=([a,...t],r=[])=>a?g(t,[...r,a+f(t,a-1)]):r

Testing:

f=([a,...t],n)=>a&&n?a+f(t,n-1):0;
g=([a,...t],r=[])=>a?g(t,[...r,a+f(t,a-1)]):r;

[
  [3, 2, 4, 1, 1, 5, 1, 2],
  [1, 2, 3, 4, 5],
  [3, 3, 3, 3, 3, 3, 3, 3,],
  [5, 1, 2, 4, 1],
  [1]
].forEach(a=>console.log(''+g(a)));

Answer 21

C#, 89 bytes

int[]s(List<int>a)=>a.Select((n,i)=>a.GetRange(i,Math.Min(n,a.Count-i)).Sum()).ToArray();

pretty straight forward

improvement ideas appreciated

Answer 22

Brachylog, 27 bytes

.v|h~l(A:Tc?;A?)b:0&~b.h~+A

Try it online! or verify all test cases.

Explanation

  .v           Input = Output = []
|            Or
  h~l          A is a list, its length is the value of the first element of the Input
  (
    A:Tc?        The concatenation of A with another list T results in the Input
  ;            Or
    A?           A = Input
  )
  b:0&         Call recursively on Input minus the first element
  ~b.          Output is the output of that call with an extra element at the beginning
  h~+A         That extra element is the sum of the elements of A

Answer 23

Dyalog APL, 15 bytes

{+/¨⍵↑∘⌽¨⌽,\⌽⍵}

or

{⌽+/¨(-↑¨,\)⌽⍵}

Answer 24

PHP program, 72 Bytes

<?foreach($a=$_GET[a]as$i=>$v)echo array_sum(array_slice($a,$i,$v)),"
";

call with php-cgi -f <filename> 'a[]=3&a[]=2&a[]=4...

+11 as a function:

function f($a){foreach($a as$i=>$v)$r[]=array_sum(array_slice($a,$i,$v));return$r;}

+9 without builtins:

function p($a){foreach($c=$r=$a as$i=>$v)for($k=$i;$k--;)if(--$a[$k]>0)$r[$k]+=$v;return$r;}

($c keeps the original values, $a counts down for each index, $r gets the sums)

-3 as program:

<?foreach($a=$r=$c=$_GET[a]as$i=>$v)for($k=$i;$k--;)if(--$c[$k]>0)$r[$k]+=$v;print_r($r);

Answer 25

q (37 bytes)

{sum each(til[count x],'x)sublist\:x}

Example:

q){sum each(til[count x],'x)sublist\:x}3 2 4 1 1 5 1 2
9 6 11 1 1 8 1 2

Answer 26

Javascript (using External Library) (66 bytes)

n=>_.From(n).Select((v,i)=>_.From(n).Slice(i,i+v).Sum()).ToArray()

Link to lib: https://github.com/mvegh1/Enumerable

Code explanation: _.From is loading the input array into the library, which is basically LINQ for js. Then each item in the array is mapped according to the following predicate: Take the input, and slice it from current item index and take that index plus the current item's value. Then Sum up that subsequence. Convert the result to a native JS array and return it

Answer 27

Clojure, 63 bytes

(defn f[[b & r]](concat[(apply + b(take(dec b)r))](if r(f r))))

Uses pattern matching to decompose input argument in to the first and the rest of the arguments.

Answer 28

MATL, 17 14 13 bytes

fGy+!-R0<G*!s

Explanation

Try it online! Or verify all test cases (code modified to handle several inputs).

f     % Take input implicitly. Indices of nonzero elements: this gives [1 2 ... n]
      % where n is input size
G     % Push input again
y     % Push a copy of [1 2 ... n]
+     % Add. Gives [a+1 b+2...] where [a b...] is the input
!     % Transpose into a column vector
-     % Subtraction with broadcast. Gives 2D array
R     % Keep upper triangular part, making the rest of entries 0
0<    % True for negative entries. Each row corresponds to a substring sum.
      % For each row, this gives true for the entries of the input that make up
      % that substring sum. Each row is thus a mask to select entries of the input
G     % Push input again
*     % Multiply with broadcast. This multiplies the input times each row
!s    % Sum of each row. Implicitly display

Answer 29

R, 47 bytes

\(a)Map(\(j,n)sum(a[0:n+j],na.rm=T),seq(a),a-1)

Attempt This Online!

A function which inputs an array and outputs the list of the partial sums. Turned out that the straightforward implementation is also the shortest one.

The subsetting and summation functions are mapped to the input array. If the end of the subsetting range is greater than the last index, NA values will be generated and they will be removed thanks to na.rm argument.

Answer 30

C#, 94 bytes

Console.Write(String.Join(",",a.Select((v,i)=>a.Skip(i).Take(v).Sum().ToString()).ToArray()));

Where a is an int[] that represents the input to be solved.