11
\$\begingroup\$

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]]
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ – recursive May 23 '18 at 16:37
  • 1
    \$\begingroup\$ Definitely a font issue. Both revisions are misaligned on my screen. \$\endgroup\$ – Dennis May 23 '18 at 16:41
  • \$\begingroup\$ May we return the result transposed? \$\endgroup\$ – Adám May 23 '18 at 20:08
  • 1
    \$\begingroup\$ we need mathjax! \$\endgroup\$ – qwr May 23 '18 at 20:26
  • 1
    \$\begingroup\$ @Adám: I'm gonna say no to that, however feel free to include a solution in your post that does so. \$\endgroup\$ – ბიმო May 23 '18 at 21:19

15 Answers 15

11
\$\begingroup\$

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

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]

\$\endgroup\$
1
  • 3
    \$\begingroup\$ 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! \$\endgroup\$ – ngm May 23 '18 at 17:31
4
\$\begingroup\$

Haskell, 70 66 51 bytes

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

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ As a puzzle, there is a 54 byte version ;) \$\endgroup\$ – ბიმო May 23 '18 at 16:26
  • 1
    \$\begingroup\$ @BMO How about 51 bytes instead? \$\endgroup\$ – Laikoni May 23 '18 at 21:50
  • \$\begingroup\$ Very nice! Mine was this :) \$\endgroup\$ – ბიმო May 23 '18 at 21:56
4
\$\begingroup\$

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.

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

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!

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

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!

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

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.

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

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

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

GolfScript, 39 bytes

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

Try it online!

Uses Dennis's algorithm.

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

Java 10, 142 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;}

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
  int[][]r=new int[m][l];
                   //  Result-matrix of size `m` by `l`
  for(;i<m;i++)    //  Loop `i` over the rows
    for(j=s=0;     //   Reset the sum to 0
        j<l;j++)   //   Inner loop `j` over the columns
      r[i][j]=s+=  //    Add the following to the sum `s`, add set it as current cell:
        i<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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 50 bytes

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

Try it online!

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

Pari/GP, 60 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 10 bytes

ÔËÆD
z ®å+

Try it (includes all test cases)

\$\endgroup\$
0
\$\begingroup\$

Husk, 7 bytes

m∫T0m´R

Try it online!

Dennis' method.

\$\endgroup\$
0
\$\begingroup\$

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

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.