# Substring Sum Set

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


Given an non-empty array with positive (non-zero) integers, output the substring sum set. This is , 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]

• I think you mean "sub-list", not "substring". There's no strings. – mbomb007 Jul 22 '16 at 13:32
• @mbomb007 I think substring has the same meaning here as in the longest common substring problem, i.e., a subsequence whose elements are adjacent. Data types aside, a string is just a finite sequence of elements of an alphabet set (in this case, the positive integers). – Dennis Jul 23 '16 at 0:19

# Jelly, 6 bytes

ṫJḣ"ḅ1


### 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.


# Python, 40 bytes

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


Test it on Ideone.

• I figured there would be a golfier recursive solution, but you beat me to it. – El'endia Starman Jul 22 '16 at 0:50

# 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.

• I'd give you a second upvote for teaching me about that double-click trick if I could. – Neil Jul 22 '16 at 8:15
• While it works it's a bit of cheating as execution requires manual input. – user3819867 Jul 22 '16 at 13:47
• @user3819867 not significantly more than most program execution, I'd argue. Perhaps it would be even more comparable if you save a spreadsheet only containing the formula in B1 - then open, add the data to column A, and double-click the handle on B1 to execute. YMMV of course. – Joffan Jul 22 '16 at 13:57

## 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.

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


One byte saved by nimi.

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

# 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


# 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)))

• As far as I know, you can remove the f=, just as in this answer. – LarsW Jul 23 '16 at 12:45
• @LarsW right, the f= is already not counted in the 45 bytes – edc65 Jul 23 '16 at 16:05

## 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.) # 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 :) • Here is an idea to avoid the table: #+Tr@Take[x=Rest@x,UpTo[#-1]]&/@(x=#)& Still not sure it's optimal but it saves 17 bytes. – Martin Ender Jul 22 '16 at 9:01 ## 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 # Pyth, 8 bytes .es:Qk+b  Test suite. Translation of El's answer in Python. # 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. ## 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(^)  # 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  # 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.  # Julia, 39 bytes !x=x!=[]?[take(x,x[])|>sum;!x[2:end]]:x  Try it online! ## 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]  # 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))); ## 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 # Brachylog, 27 bytes .v|h~l(A:Tc?;A?)b:0&~b.h~+A  ### 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  ## Dyalog APL, 15 bytes {+/¨⍵↑∘⌽¨⌽,\⌽⍵}  or {⌽+/¨(-↑¨,\)⌽⍵}  # 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);


# 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


# 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


## Javascript (using External Library) (66 bytes)

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


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

• Remove the var  from the variables, you don't need that in golf. You can also change .forEach to .map which costs less bytes. – charredgrass Jul 22 '16 at 1:53
• Oh yeah, you're right about var. Thanks! I'll go through this answer again tomorrow. It looks like native JS (es6) kills my solution lol – applejacks01 Jul 22 '16 at 2:27
• Good call on removing var. I also realized another solution which reduces the byte count a lot and is also more intuitive – applejacks01 Jul 25 '16 at 18:39

## 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.

# MATL, 1714 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


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.

• you arent allowed to assume a variable is predefined – downrep_nation Jul 22 '16 at 17:59
• The variable a is the input to be solved. – supermeerkat Jul 23 '16 at 18:53