26
\$\begingroup\$

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 , 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]
\$\endgroup\$
  • \$\begingroup\$ I think you mean "sub-list", not "substring". There's no strings. \$\endgroup\$ – mbomb007 Jul 22 '16 at 13:32
  • 4
    \$\begingroup\$ @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). \$\endgroup\$ – Dennis Jul 23 '16 at 0:19

29 Answers 29

15
\$\begingroup\$

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

Python, 40 bytes

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

Test it on Ideone.

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

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.

\$\endgroup\$
  • \$\begingroup\$ I'd give you a second upvote for teaching me about that double-click trick if I could. \$\endgroup\$ – Neil Jul 22 '16 at 8:15
  • \$\begingroup\$ While it works it's a bit of cheating as execution requires manual input. \$\endgroup\$ – user3819867 Jul 22 '16 at 13:47
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Joffan Jul 22 '16 at 13:57
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 34, 33 bytes

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

One byte saved by nimi.

\$\endgroup\$
4
\$\begingroup\$

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>

\$\endgroup\$
4
\$\begingroup\$

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

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

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

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

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Jul 22 '16 at 9:01
3
\$\begingroup\$

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

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

Pyth, 8 bytes

.es:Qk+b

Test suite.

Translation of El's answer in Python.

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

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.

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

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

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

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

Julia, 39 bytes

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

Try it online!

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

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

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

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

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

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

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

Dyalog APL, 15 bytes

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

or

{⌽+/¨(-↑¨,\)⌽⍵}
\$\endgroup\$
1
\$\begingroup\$

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

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

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

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

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Remove the var from the variables, you don't need that in golf. You can also change .forEach to .map which costs less bytes. \$\endgroup\$ – charredgrass Jul 22 '16 at 1:53
  • \$\begingroup\$ 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 \$\endgroup\$ – applejacks01 Jul 22 '16 at 2:27
  • \$\begingroup\$ Good call on removing var. I also realized another solution which reduces the byte count a lot and is also more intuitive \$\endgroup\$ – applejacks01 Jul 25 '16 at 18:39
1
\$\begingroup\$

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.

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

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

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.

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

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.