Sum of replicated matrices

Given a list of numbers $$\[a_1, a_2, ... a_n]\$$, compute the sum of all the matrices $$\A_i\$$ where $$\A_i\$$ is defined as follows ($$\m\$$ is the maximum of all $$\a_i\$$):

$$\begin{array}{c|cc} & 1 & 2 & \cdots & i-1 & i & i+1 & \cdots & n \\ \hline 1 & 0 & 0 & \cdots & 0 & a_i & a_i & \cdots & a_i \\ 2 & 0 & 0 & \cdots & 0 & a_i & a_i & \cdots & a_i \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots \\ a_i & 0 & 0 & \cdots & 0 & a_i & a_i & \cdots & a_i \\ a_{i+1}& 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \vdots & & \vdots & & \vdots & & \vdots & & \vdots \\ m & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 \\ \end{array}$$

Example

Given the input [2,1,3,1] we construct the following matrix:

$$\left[\begin{matrix} 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right] + \left[\begin{matrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right] + \left[\begin{matrix} 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 3 & 3 \\ \end{matrix}\right] + \left[\begin{matrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{matrix}\right] = \left[\begin{matrix} 2 & 3 & 6 & 7 \\ 2 & 2 & 5 & 5 \\ 0 & 0 & 3 & 3 \\ \end{matrix}\right]$$

Rules and I/O

• you may assume the input is non-empty
• you may assume all the inputs are non-negative (0≤)
• the input can be a $$\1×n\$$ (or $$\n×1\$$) matrix, list, array etc.
• similarly the output can be a matrix, list of lists, array etc.
• you can take and return inputs via any default I/O format
• your submission may be a full program or function

Test cases

[0] -> [] or [[]]
[1] -> [[1]]
[3] -> [[3],[3],[3]]
[2,2] -> [[2,4],[2,4]]
[3,0,0] -> [[3,3,3],[3,3,3],[3,3,3]]
[1,2,3,4,5] -> [[1,3,6,10,15],[0,2,5,9,14],[0,0,3,7,12],[0,0,0,4,9],[0,0,0,0,5]]
[10,1,0,3,7,8] -> [[10,11,11,14,21,29],[10,10,10,13,20,28],[10,10,10,13,20,28],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,17,25],[10,10,10,10,10,18],[10,10,10,10,10,10],[10,10,10,10,10,10]]

• I'm guessing there's a font difference or something. I see you rolled back my edit. This is how it currently looks to me imgur.com/a06RH9r This is Chrome on Windows 10. The vertical ellipses are not rendered in monospace for some reason, and don't align with the columns. That's why I changed it. But I guess it must look different in different environments. May 23, 2018 at 16:37
• Definitely a font issue. Both revisions are misaligned on my screen. May 23, 2018 at 16:41
• May we return the result transposed?
May 23, 2018 at 20:08
• we need mathjax!
– qwr
May 23, 2018 at 20:26
• @Adám: I'm gonna say no to that, however feel free to include a solution in your post that does so. May 23, 2018 at 21:19

Jelly, 10 5 bytes

ẋ"z0Ä


Try it online!

How it works

ẋ"z0Ä  Main link. Argument: A (array)

e.g. [2, 1, 3, 1]

ẋ"     Repeat each n in A n times.

e.g. [[2, 2   ]
[1      ]
[3, 3, 3]
[1      ]]

z0   Zipfill 0; read the result by columns, filling missing elements with 0's.

e.g. [[2, 1, 3, 1]
[2, 0, 3, 0]
[0, 0, 3, 0]]

Ä  Take the cumulative sum of each row vector.

e.g. [[2, 3, 6, 7]
[2, 2, 5, 5]
[0, 0, 3, 3]]


R, 80 bytes

n=sum((a=scan())|1);for(i in 1:n)F=F+[<-(matrix(0,max(a),n),0:a[i],i:n,a[i]);F


Try it online!

Takes input from stdin; prints a 0x1 matrix for input 0, which prints out like

	[,1]

• For those wondering, F is a built-in global variable whose initial value is FALSE. Here it's coerced to 0 and used as the initial value of the cumulative sum. This answer demonstrates the reason not to use F and T except in code specifically designed never to be actually used!
– ngm
May 23, 2018 at 17:31

g x=[scanl1(+)[sum[n|n>=r]|n<-x]|r<-[1..maximum x]]


Try it online!

• As a puzzle, there is a 54 byte version ;) May 23, 2018 at 16:26
• @BMO How about 51 bytes instead? May 23, 2018 at 21:50
• Very nice! Mine was this :) May 23, 2018 at 21:56

APL (Dyalog Unicode), 8 bytesSBCS

Full program. Prompts stdin for list, prints matrix to stdout.

Uses Dennis's method.

+\⍉↑⍴⍨¨⎕


Try it online!

⎕ stdin

⍴⍨¨reshape-selfie of each

↑ mix list of lists into matrix, filling with 0s

⍉ transpose

+\ cumulative row-wise sum

The ⍉ doesn't make any computational difference, so it could potentially be left out and \ changed to ⍀ to sum column-wise instead of row-wise.

JavaScript (ES6), 88 79 bytes

Returns [] for [0].

f=(a,y,b=a.map((_,x)=>a.map(c=>y>=c|x--<0?0:s+=c,s=0)|s))=>s?[b,...f(a,-~y)]:[]


Try it online!

Python 2, 85 bytes

lambda x:[[sum(n*(n>j)for n in x[:i+1])for i in range(len(x))]for j in range(max(x))]


Try it online!

Octave, 64 bytes

@(x,k=a=0*(x+(1:max(x))'))eval"for i=x;a(1:i,++k:end)+=i;end,a";


Try it online!

Explanation:

Yet again: Expressions in the argument list and eval are used in one function :)

This takes x as input, and creates two identical matrices filled with zeros, with the dimensions k=a=zeros(length(x),max(x)). This is achieved by adding the horizontal vector x with a vertical vector with 1:max(x), implicitly expanding the dimensions to a 2D-array, then multiplying this with zero. ~(x+...) doesn't work unfortunately, since that forces a to be a logical array throughout the rest of the function.

for i=x is a loop that for each iteration makes i=x(1), then i=x(2) and so on. a(1:i,k++:end) is the part of the matrix that should be updated for each iteration. 1:i is a vector saying which rows should be updated. If i=0, then this will be an empty vector, thus nothing will be updated, otherwise it's 1, 2 .... ++k:end increments the k matrix by one, and creates a range from the first value of this matrix (1,2,3...) and up to the last column of the a matrix. +=i adds the current value to a. end,a ends the loop and outputs a.

Wolfram Language (Mathematica), 42 bytes

Thread@Accumulate@PadRight[#~Table~#&/@#]&


Try it online!

Java 10, 142135 134 bytes

a->{int l=a.length,i=0,j,s,m=0;for(int q:a)m=q>m?q:m;int[][]r=new int[m][l];for(;i<m;i++)for(j=s=0;j<l;j++)r[i][j]=s+=i<a[j]?a[j]:0;return r;}


-7 bytes thanks to @ceilingcat.

Try it online.

a->{              // Method with integer-array parameter and integer-matrix return-type
int l=a.length, //  Length of the input-array
i,j,        //  Index integers
s,          //  Sum integer
m=0;for(int q:a)m=q>m?q:m;
//  Determine the maximum of the input-array
var r=new int[m][l];
//  Result-matrix of size m by l
for(;m-->0;)    //  Loop i over the rows
for(j=s=0;    //   Reset the sum to 0
j<l;j++)  //   Inner loop j over the columns
r[m][j]=s+= //    Add the following to the sum s, add set it as current cell:
m<a[j]?   //     If the row-index is smaller than the j'th value in the input:
a[j]     //      Add the current item to the sum
:         //     Else:
0;       //      Leave the sum the same by adding 0
return r;}      //  Return the result-matrix


GolfScript, 39 bytes

{.\$):M;;{[.](*[0]M*+M<}%zip{{\.@+}*]}%}


Try it online!

Uses Dennis's algorithm.

Ruby, 50 bytes

->a{(1..a.max).map{|n|w=0;a.map{|r|w+=(r<n)?0:r}}}


Try it online!

Pari/GP, 60 bytes

a->matrix(vecmax(a),#a,i,j,vecsum([a[k]|k<-[1..j],a[k]>=i]))


Try it online!

Japt, 10 bytes

ÔËÆD
z ®å+


Try it (includes all test cases)

Husk, 7 bytes

m∫T0m´R


Try it online!

Dennis' method.

k, 24 Bytes

{+\'+(x#'x),'(x-|/x)#'0}


Dennis algorithm

Sample

  {+\'+(x#'x),'(x-|/x)#'0}2 1 3 1
(2 3 6 7;2 2 5 5;0 0 3 3)


numeric arrays in k are represented as a sequence of values without separators, so 2 1 3 1 is the same as [2,1,3,1] in other languages.

k Use the syntax (..;..;..) to represent an heterogeneous or multi-level list, so (2 3 6 7;2 2 5 5;0 0 3 3) is the same as [[2,3,6,7],[2,2,5,5],[0,0,3,3]] in other languages

Explanation

• {..x..} defines an anobymous function with implicit arg x
• +\array is the cummulative sum of the elems of the array
• f'matrix applies f to each row ('=each) of the matrix preserving matrix shape, so +\'matrix calculates cummulative sum of the elems of each row of the matrix
• n#x signifies take n copies of x value. if n and x are both arryas of the same length, n#'x applies # to each pair, so 2 1 3 1#'2 1 3 1 is the same as (2#2; 1#1; 3#3; 1#1) and evaluates to (2 2;,1;3 3 3;,1). NOTE one-item list is represented as ,item
• a,b joins (catenates) arrays a and b. a,'b applies , to each corresponding items of a and b: if both are matrices of the same shape, catenates each corresponding pair of rows
• |/array applies binary operator | (max) over the elements of the array (reduce), so |/2 1 3 1 is equivalent to 2|1|3|1 and reduces to 3
• (x-|/x) substract to each element of x the maximum of the array, so 2 1 3 1 - |/2 1 3 1 is the same as 2 1 3 1 - 3 and evaluate to -1 -2 0 -2
• array#'0 is "take n copies of 0" for each value n in array. It really uses "abs(n) take 0", so we don't worry about sign. -1 -2 0 -2#'0 evaluates to (,0;0 0;();0 0). NOTE.- () is the empty array

k applies unary operators and binary operators right to left, and parenthesis indicate precedence. NOTE.- k uses one-letter symbols, with two meanings (unary op or binary op) depending of context (example + as binary op is sum, but as unary op is flip (transpose).

• #' is a binary op modified by ' adverb. Its arguments are (x-|/x) and 0.
• Evaluates x-|/x first. | it's a binary op (max), but adverb / convert it to unary (max over x), and evaluates to 3. The resulting x-3 is a binary op (minus), with args xand 3, and evals to -1 -2 0 -2
• -1 -2 0 -2#'0 evals to (,0;0 0;();0 0)
• The actual expr is +\'+(x#'x),'(,0;0 0;();0 0). , is a binary op (join) modified by ' adverb (each): we need to evaluate the left arg (x#'x)
• x#'x is 2 1 3 1#'2 1 3 1, and applies binay op # (take) to each pair. The result is (2 2;,1;3 3 3;,1)
• (2 2;,1;3 3 3;,1),'(,0;0 0;();0 0) applies binary op , modified by (') each, and join each pair of corresponding values. The result is (2 2 0;1 0 0;3 3 3;1 0 0)
• + is a monad operator that transpose (flip) the matrix, so the result is (2 1 3 1;2 0 3 0;0 0 3 0)
• +\'matrix calculates cummulative sums of each row of the matrix, so eval to $$`$$(2 3 6 7;2 2 5 5;0 0 3 3)