11
\$\begingroup\$

Given a list of numbers [ a1 a2 ... an ], compute the sum of all the matrices Aᵢ where Aᵢ is defined as follows (m is the maximum of all aᵢ):

       1  2  ⋯ (i-1) i (i+1) ⋯  n
     +----------------------------
 1   | 0  0  ⋯   0   aᵢ  aᵢ  ⋯  aᵢ
 2   | 0  0  ⋯   0   aᵢ  aᵢ  ⋯  aᵢ
 .   . .  .      .   .   .      .
 .   . .  .      .   .   .      .
aᵢ   | 0  0  ⋯   0   aᵢ  aᵢ  ⋯  aᵢ
aᵢ₊₁ | 0  0  ⋯   0   0   0   ⋯  0
 .   . .  .      .   .   .      .
 .   . .  .      .   .   .      .
 m   | 0  0  ⋯   0   0   0   ⋯  0

Example

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

[2 2 2 2]   [0 1 1 1]   [0 0 3 3]   [0 0 0 1]   [2 3 6 7]
[2 2 2 2] + [0 0 0 0] + [0 0 3 3] + [0 0 0 0] = [2 2 5 5]
[0 0 0 0]   [0 0 0 0]   [0 0 3 3]   [0 0 0 0]   [0 0 3 3]

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\$
  • \$\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

12 Answers 12

9
\$\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\$
  • 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\$
  • 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
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\$
3
\$\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\$
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\$
1
\$\begingroup\$

GolfScript, 39 bytes

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

Try it online!

Uses Dennis's algorithm.

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

Wolfram Language (Mathematica), 42 bytes

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

Try it online!

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

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.