Take a non-empty matrix / numeric array containing positive integers as input. Return, in this order, the sums of the first row and column, then the second row and column and continue until there aren't any more rows or columns.
Suppose the input is:
2 10 10 2 4
9 7 7 2 9
1 7 6 2 4
7 1 4 8 9
Then the output should be:
45, 33, 16, 17
Because: 2+たす9+たす1+たす7+たす10+たす10+たす2+たす4=わ45, 7+7+1+7+2+9=33, 6+4+2+4=16, 8+9=17.
Test cases:
Test cases are on the following format:
Input
---
Output
5
---
5
..........
1 4
----
5
..........
7
2
---
9
..........
8 3 7 10 3 7 10 1
10 7 5 8 4 3 3 1
1 6 4 1 3 6 10 1
2 3 8 2 8 3 4 1
---
62 40 33 18
..........
30 39 48 1 10 19 28
38 47 7 9 18 27 29
46 6 8 17 26 35 37
5 14 16 25 34 36 45
13 15 24 33 42 44 4
21 23 32 41 43 3 12
22 31 40 49 2 11 20
---
320 226 235 263 135 26 20
..........
7 10 1
4 4 2
6 3 4
1 4 10
5 7 6
---
34 20 20
As arrays:
[[5]]
[[1,4]]
[[7],[2]]
[[8,3,7,10,3,7,10,1],[10,7,5,8,4,3,3,1],[1,6,4,1,3,6,10,1],[2,3,8,2,8,3,4,1]]
[[30,39,48,1,10,19,28],[38,47,7,9,18,27,29],[46,6,8,17,26,35,37],[5,14,16,25,34,36,45],[13,15,24,33,42,44,4],[21,23,32,41,43,3,12],[22,31,40,49,2,11,20]]
[[7,10,1],[4,4,2],[6,3,4],[1,4,10],[5,7,6]]
This is code-golf so the shortest solution in each language wins.
33 Answers 33
MATL, 16 bytes
&n:w:!XlX:GX:1XQ
Try it online! Or verify all test cases.
Explanation
Consider, as an example, the input
2 10 10 2 4
9 7 7 2 9
1 7 6 2 4
7 1 4 8 9
The code &n:w:!Xl builds the column vector [1; 2; 3; 4] and the row vector [1 2 3 4 5]. Then Xl computes the minimum element-wise with broadcast, which gives the matrix
1 1 1 1 1
1 2 2 2 2
1 2 3 3 3
1 2 3 4 4
X: linearizes this matrix (in column-major order) into the column vector [1; 1; 1; 1; 1; 2; 2; ... ; 4]. This vector and the linearized input matrix, obtained as GX:, are passed as inputs to the accumarray(... @sum) function, or 1XQ. This computes the sum of the second input grouped by values of the first input.
CJam, (削除) 23 (削除ここまで) 18 bytes
{[{(:+\z}h;]2/::+}
Anonymous block expecting the argument on the stack and leaving the result on the stack.
Explanation
[ e# Begin working in an array.
{ e# Do:
(:+ e# Remove the first row of the matrix and sum it.
\z e# Bring the matrix back to the top and transpose it.
}h e# While the matrix is non-empty.
; e# Discard the remaining empty matrix.
] e# Close the array.
2/ e# Split it into consecutive pairs of elements (possibly with a singleton on the end).
::+ e# Sum each pair.
-
\$\begingroup\$ Isn't this a bit "cheating"? I mean, you are not counting the input and output code in the byte count. With both input and output it is only 1 byte longer:
q~[{(:+\z}h;]2/::+p\$\endgroup\$FrodCube– FrodCube2017年05月18日 20:35:02 +00:00Commented May 18, 2017 at 20:35 -
\$\begingroup\$ @FrodCube It is allowed by meta consensus. \$\endgroup\$Business Cat– Business Cat2017年05月18日 20:36:44 +00:00Commented May 18, 2017 at 20:36
-
2\$\begingroup\$ Actually, technically, it would be the same length as a full program, since I could omit the opening
[. But as a block I think I need it because it needs to not capture the entire stack below as well. \$\endgroup\$Business Cat– Business Cat2017年05月18日 20:38:01 +00:00Commented May 18, 2017 at 20:38
05AB1E, (削除) 14 (削除ここまで) 11 bytes
[ćOˆøŽ] ̄2ôO
Explanation
[ Ž ] # loop until stack is empty
ć # extract the head
Oˆ # sum and add to global list
ø # transpose
̄ # push global list
2ô # split into pairs
O # sum each pair
JavaScript (ES6), 60 bytes
a=>a.map((b,y)=>b.map((c,x)=>r[x=x<y?x:y]=~~r[x]+c),r=[])&&r
Naive solution, may be a better way.
Octave, (削除) 63 (削除ここまで) 60 bytes
@(A)(@(L)sum(triu(A,1)')(L)+sum(tril(A))(L))(1:min(size(A)))
The answer for this matrix:
2 10 10 2 4
9 7 7 2 9
1 7 6 2 4
7 1 4 8 9
is the vector of row sums of its upper triangular part:
0 10 10 2 4
0 0 7 2 9
0 0 0 2 4
0 0 0 0 9
plus the vector of column sums of its lower triangular part:
2 0 0 0 0
9 7 0 0 0
1 7 6 0 0
7 1 4 8 0
which is precisely what my answer is computing.
Mathematica, 60 bytes
Inspired by Luis Mendo's MATL answer.
Pick[#,Min~Array~d,n]~Total~2~Table~{n,Min[d=Dimensions@#]}&
Explanation: Min~Array~Dimensions@# constructs a matrix like the following:
1 1 1 1 1
1 2 2 2 2
1 2 3 3 3
1 2 3 4 4
Then Pick[#,...,n]~Total~2 picks out the entries of the input matrix corresponding to the number n in the weird matrix above, and sums them. Finally ...~Table~{n,Min[d=Dimensions@#]} iterates over n.
This is 1 byte shorter than the naïve approach:
{#[[n,n;;]],#[[n+1;;,n]]}~Total~2~Table~{n,Min@Dimensions@#}&
Haskell, (削除) 50 (削除ここまで) 49 bytes
f(a@(_:_):b)=sum(a++map(!!0)b):f(tail<$>b)
f _=[]
If there's at least one row with at least one element, the result is the sum of the first row and the heads of all other rows followed by a recursive call with the tails of all other rows. In all other cases, the result is the empty list.
Edit: Ørjan Johansen saved a byte. Thanks!
Octave, (削除) 64 (削除ここまで) 52 bytes
Thanks to @StewieGriffin for saving 1 byte!
@(x)accumarray(min((1:size(x))',1:rows(x'))(:),x(:))
This defines an anonymous function.
Explanation
The code is similar to my MATL answer (see explanation there).
Two bytes have been saved using 1:size(x) instead of 1:size(x,1), exploiting the fact that 1:[a b] behaves the same as 1:a. Also, one byte has been saved using 1:rows(x') instead of 1:size(x,2), thanks to Stewie.
R, (削除) 63 (削除ここまで) (削除) 60 (削除ここまで) (削除) 59 (削除ここまで) (削除) 57 (削除ここまで) 56 bytes
Edit: -4 bytes, and then -2, and then -1 more, thanks to Robin Ryder
function(m,`+`=sum)while(+m)show(m+-{m=m[-1,-1,drop=F]})
Repeatedly removes the first row & column (using negative indexing: m[-1,-1] is m without the first row & column), prints the difference between the sum of m and this, and keeps going if there's anything left.
R is very well-suited to this type of vectorized matrix operation, so this approach comes-out significantly shorter than a looping approach.
-
-
1\$\begingroup\$ @Giuseppe - that will print a final
0if the matrix has more cols than rows, because the rows will run-out first: try it. \$\endgroup\$Dominic van Essen– Dominic van Essen2020年12月05日 14:58:42 +00:00Commented Dec 5, 2020 at 14:58 -
1\$\begingroup\$ 61 bytes \$\endgroup\$Robin Ryder– Robin Ryder2020年12月05日 16:20:29 +00:00Commented Dec 5, 2020 at 16:20
-
1\$\begingroup\$ I've just noticed that the challenge specs state the input will be positive, so you can use
while(m)for 52 bytes. If you dislike the function erroring after printing the correct output, you can add atryfor 57. \$\endgroup\$Robin Ryder– Robin Ryder2020年12月05日 22:50:03 +00:00Commented Dec 5, 2020 at 22:50 -
2\$\begingroup\$ In that case, you can use a shorthand for
sumfor 56. \$\endgroup\$Robin Ryder– Robin Ryder2020年12月05日 23:22:48 +00:00Commented Dec 5, 2020 at 23:22
oK, (削除) 19 (削除ここまで) 18 bytes
-1 byte thanks to coltim.
1_--':+//'(1_+1_)\
Explanation:
(1_+1_) /a function that strips the top and leftmost rows of a matrix
\ /apply this function as many times as possible,
/ saving each result as one element of a list
+//' /for each result, get the sum of all numbers
--': /subtract every right value from every left value
1_ /remove the extra 0
-
\$\begingroup\$ I think you can do
1_--':instead of|1_-':|to save a byte. \$\endgroup\$coltim– coltim2020年12月05日 16:47:24 +00:00Commented Dec 5, 2020 at 16:47
Julia, 62 bytes
f=x->1∈size(x)?sum(x):(n=f(x[2:end,2:end]);[sum(x)-sum(n);n])
Works recursively by summing up the whole matrix and then subtracting off the sum of the next block. Probably not the most effective approach, but nicely intuitive.
05AB1E, 16 bytes
[ćOsø.g<NQ#])2ôO
Try it online! or Try all tests
[ # Start loop
ć # Extract first element
O # Sum
sø # Transpose the input array (without the first N rows and columns)
.g<NQ # Push if (stack height - 1 == loop count)
#] # If they were equal break
)2ô # Break stack into chunks of 2
O # Sum the chunks
Vim, (削除) 66 (削除ここまで), 52 bytes
qq^f j<C-v>}dkV}Jo<esc>p@qq@q:%s/\v> +</+/g|%norm C<C-v><C-r>=<C-v><C-r>"<C-v><cr><cr>
The wrong tool for the job...
Perl 6, (削除) 63 (削除ここまで) 55 bytes
(削除) {($_ Z [Z] $_).kv.map(->\a,\b{b.flatmap(*[a..*]).sum -b[0;a]})} (削除ここまで)
{($_ Z [Z] .skip).kv.map({$^b.flatmap(*[$^a..*]).sum})}
$_is the matrix input to the anonymous function.skipis the input matrix with its first row removed[Z] .skipis the transpose of the input matrix with its first row removed; that is, the transpose without its first column$_ Z [Z] .skipzips the input matrix with its transpose-sans-first-column, producing a list((first-row, first-column-sans-first-element), (second-row, second-column-sans-first-element), ...).kvprefixes each pair with its indexmap({...})maps over the the pairs, using a function which takes its first argument (the index) in$^aand its second (the row/column pair) in$^b$^b.flatmap(*[$^a..*]).sumstrips off the first$^aelements of each row/column pair, then sums all the remaining elements
After some thought I realized that stripping off the first column of the transpose before zipping was equivalent to subtracting the doubly-contributing diagonal elements, as in my first solution. That let me delete that subtraction, and using each argument to the mapping function only once made the {...$^a...$^b...} method of passing arguments to an anonymous function more efficient than the original -> \a, \b {...a...b...}.
GNU APL 1.7, 123 bytes
Solution requires two functions: one creates a global array and the calls the second, which recursively appends the sums to that array.
∇f N
R←⍬
g N
R
∇
∇g ×ばつ0∈⍴N
R←R,(+/N[1;])+(+/N[;1])-N[1;1]
g N[1↓⍳1⊃⍴N;1↓⍳2⊃⍴N]
∇
∇ begins and ends the function. Both f and g take tables as arguments (essentially 2D arrays). These can be created with X←rows cols ⍴ 1 2 3 4....
R←⍬ assigns an empty vector to global variable R.
g N calls the second function with the same argument given to the first.
⍴N gives the dimensions of N; when one of the dimensions is zero, there are no more rows/columns to add up. 0∈⍴N returns 1 if there is a zero in the dimensions. ×ばつ0∈⍴N branches to line number 2 plus 2 times the return value of the ∈ function: if there is no zero, ∈ returns 0 and the function branches to line 2 (the next line). If there is a zero, ∈ returns 1 and the function branches to line 4 (the end of the function, so return essentially).
/ is the reduce operator. It applies the left argument, which is an operator (+) to every element in the list given as the right argument. N[1;] gives the entire first row of the table and N[;1] gives the first column. (+/N[1;])+(+/N[;1])-N[1;1] sums the first row and column and subtracts the value in the upper left corner because it gets added both in the column sum and the row sum. R←R,... appends the newly calculated value to the global vector R.
The function then calls itself (recurse until no more rows or columns). The ⊃ pick operator obtains the specified element from the list. 1⊃⍴N gives the number of rows, 2⊃⍴N the number of columns. ⍳ gives all numbers from 1 to the specified number. The ↓ drop operator removes elements from the beginning of the list. If you give multiple indices when accessing elements from a table or vector (e.g. N[1 2 3]), APL accesses each one. Therefore, 1↓⍳1⊃⍴N gives the indices of each row excluding the first one (2, 3, 4, ..., N) and 1↓⍳2⊃⍴N gives a similar vector but for the columns. g N[1↓⍳1⊃⍴N;1↓⍳2⊃⍴N] calls the function again but without the first row or column.
Java 10, (削除) 248 (削除ここまで) (削除) 245 (削除ここまで) (削除) 227 (削除ここまで) (削除) 223 (削除ここまで) (削除) 219 (削除ここまで) 218 bytes
a->{int l=a.length,L=a[0].length,b[][]=new int[l][L],i,j,x=0,s;for(;++x<l|x<L;)for(i=l;i-->x;)for(j=L;j-->x;)b[i][j]=x;var r="";for(;x-->0;r=s>0?s+" "+r:r)for(s=0,i=l*L;i-->0;)s+=b[i/L][i%L]==x?a[i/L][i%L]:0;return r;}
-8 bytes thanks to @ceilingcat
General explanation:
Let's say the input array has dimensions of 4x6. The first part of the code will create a temp matrix and fills it as follows:
// 1. Fill the entire array with 0:
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
// 2. Overwrite the inner part with 1 (excluding the first row & column):
0 0 0 0 0 0
0 1 1 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
// #. Etc. until we are left with this:
0 0 0 0 0 0
0 1 1 1 1 1
0 1 2 2 2 2
0 1 2 3 3 3
And in the second part of the code it will loop over this temp matrix, and sums all values of the input-matrix for each of the distinct numbers in the temp matrix.
Explanation of the code:
a->{ // Method with int-matrix parameter and String return-type
int l=a.length, // Amount of rows
L=a[0].length, // Amount of columns
b[][]=new int[l][L], // New temp matrix to fill as explained above
i,j,x=0,s; // Some temp integers
//This is the first part of the code mentioned above:
for(;++x<l|x<L;) // Loop `x` over the rows or columns (whichever is larger):
for(i=l;i-->x;) // Inner loop over the rows:
for(j=L;j-->x;) // Inner loop over the cells of this row:
b[i][j]=x; // Set the value of the current cell to `x`
//This is the second part of the code mentioned above:
var r=""; // Result-String, starting empty
for(;x-->0 // Loop over the unique numbers in the temp matrix:
; // After every iteration:
r=s>0?s+" "+r:r) // If the sum is larger than 0: append it
for(s=0, // Reset the sum to 0
i=l*L;i-->0;) // Inner loop over the cells:
s+=b[i/L][i%L]==x? // If the current cell of the temp-matrix contains `x`:
a[i/L][i%L]:0; // Add the input's value at this position to the sum
return r;} // Return the result-String
Jelly, 10 bytes
Ḣ;Ḣ€SṄȧßS¿
A full program that prints the values
How?
Ḣ;Ḣ€SṄȧßF¿ - Main link: list of lists a
Ḣ - head a (pop the first row and yield it, modifying a)
Ḣ€ - head €ach (do the same for each of the remaining rows)
; - concatenate
S - sum (adds up the list that contains the top row and left column)
Ṅ - print that plus a linefeed and yield the result
¿ - while:
- ... condition:
F - flatten (a list of empty lists flattens to an empty list which is falsey)
- ... body:
ß - call this link with the same arity (as a monad) i.e. Main(modified a)
ȧ - logical and (when the sum is non-zero gets the modified a to feed back in)
Python 2, 97 bytes
f=lambda m:[reduce(lambda x,y:x+y[i],m[i:],sum(m[i][i+1:]))for i in range(min(len(m),len(m[0])))]
-
\$\begingroup\$ There is a good deal of whitespace in this answer that could be removed. \$\endgroup\$2017年05月19日 00:03:53 +00:00Commented May 19, 2017 at 0:03
-
\$\begingroup\$ @WheatWizard Thanks! Reduced my answer by 4 bytes :) \$\endgroup\$ZestyLemon– ZestyLemon2017年05月19日 00:12:02 +00:00Commented May 19, 2017 at 0:12
Pyth, (削除) 16 (削除ここまで) 15 bytes
.es+>b+1k>@CQkk
Takes a python-style array of arrays of numbers, returns an array of sums.
Explanation
.es+>b+1k>@CQkk
.e Q # Enumerated map over the implicit input (Q); indices k, rows b
CQ # Take the transpose
@ k # The kth column
> k # cut off the first k elements
>b+1k # cut off the first k+1 elements of the rows, so (k,k) isn't counted twice
s+ # add the row and column together and sum
Python + NumPy, (削除) 75 (削除ここまで) 66 bytes
Input is a 2D numpy array.
lambda L:[sum(L[i,i:])+sum(L[i+1:,i])for i in range(min(L.shape))]
-9 bytes by Black Owl Kai
PHP, 76 Bytes
<?foreach($_GET as$k=>$v)foreach($v as$n=>$i)$r[min($k,$n)]+=$i;print_r($r);
Mathematica, 116 bytes
l=Length;If[l@#==1||l@#[[1]]==1,Total@Flatten@#,Total/@Flatten/@Table[{#[[i]][[i;;]],#[[All,i]][[i+1;;]]},{i,l@#}]]&
Input form
[{{5}}], [{{1},{4}}], [{{7,2}}] or [{{....},{....}...{....}}]
Clojure, 98 bytes
#(vals(apply merge-with +(sorted-map)(mapcat(fn[i r](map(fn[j v]{(min i j)v})(range)r))(range)%)))
Iterates over the input with row and column indexes (in a very verbose manner), creates a hash-map with the minimum of i and j as the key, merges hash-maps with + into a sorted-map, returns values.
R, 102 bytes
function(x)`for`(i,1:min(r<-nrow(x),k<-ncol(x)),{dput(sum(x[,1],x[1,-1]));x=matrix(x[-1,-1],r-i,k-i)})
returns an anonymous function; prints the results to the console, with a trailing newline. I probably need a different approach.
Iterates over the minimum of the rows and columns; prints the sum of x[,1] (the first column) and x[1,-1] the first row except for the first entry, then sets x to be a matrix equal to x[-1,-1] (i.e., x excluding its first row and column). Unfortunately, simply setting x=x[-1,-1] causes it to fail in the case of a square matrix, because when x is 2x2, the subsetting returns a vector rather than a matrix.
-
1\$\begingroup\$ Re: "I probably need a different approach" - yes. 63 bytes without looping... \$\endgroup\$Dominic van Essen– Dominic van Essen2020年12月05日 14:32:20 +00:00Commented Dec 5, 2020 at 14:32
-
1\$\begingroup\$ @DominicvanEssen lol I've gotten much better at golfing in the last 3 years. \$\endgroup\$Giuseppe– Giuseppe2020年12月05日 15:01:15 +00:00Commented Dec 5, 2020 at 15:01
Java 7, (削除) 280 (削除ここまで) 276 bytes
import java.util.*;String d(ArrayList l){String r="";for(;l.size()>0&&((List)l.get(0)).size()>0;l.remove(0))r+=s(l)+" ";return r;}int s(List<ArrayList<Integer>>l){int s=0,L=l.size(),i=1;for(;l.get(0).size()>0;s+=l.get(0).remove(0));for(;i<L;s+=l.get(i++).remove(0));return s;}
Alternative approach compared to my previous answer with arrays, which is still shorter than this one in the end (so I kinda wasted time trying this alternative approach).
General explanation:
Inspiration from @Riley's amazing 05AB1E answer
This answer uses a List and after every sum is calculated it removes the first column and first row from the List-matrix, like this:
// Starting matrix:
7 10 1
4 4 2
6 3 4
1 4 10
5 7 6
// After first iteration (result so far: "34 "):
4 2
3 4
4 10
7 6
// After second iteration (result so far: "34 20 "):
4
10
6
// After last iteration, result: "34 20 20 "
Explanation of the code:
import java.util.*; // Required import for List and ArrayList
String d(ArrayList l){ // Method with ArrayList parameter and String return-type
String r=""; // Return-String
for(;l.size()>0&&((List)l.get(0)).size()>0;
// Loop as long as the list still contains anything
l.remove(0)) // And remove the first row after every iteration
r+=s(l)+" "; // Append the sum to the result-String
// End of loop (implicit / single-line body)
return r; // Return result-String
} // End of method
int s(List<ArrayList<Integer>>l){ // Separate method with List-matrix parameter and integer return-type
int s=0, // The sum
L=l.size(), // The size of the input list
i=1; // Temp integer
for(;l.get(0).size()>0; // Loop (1) over the items of the first row
s+=l.get(0). // Add the number to the sum
remove(0) // And remove it from the list afterwards
); // End of loop (1)
for(;i<L; // Loop (2) over the rows
s+=l.get(i++). // Add the first number of the row to the sum
remove(0) // And remove it from the list afterwards
); // End of loop (2)
return s; // Return sum
} // End of separate method
Python, 93 bytes
Similar to mbomb007's answer, but without NumPy
f=lambda m:[sum(m[k][k:])+sum(list(zip(*m))[k][k+1:])for k in range(min(len(m),len(m[0])))]
Perl 5 -MList::Util=sum -n, 48 bytes
@,=eval;say sum@{shift@,},map{shift@$_}@,while@,
AWK, 76 bytes
{for(i=0;i++<NF;i>NR&&a[NR]+=$i)i<=NR&&a[i]+=$i}END{for(;j++<NR;)print a[j]}
Uiua, 8 bytes
⊕/+⧋/↧°⊡
°⊡ unpick the coordinates, /↧ reduce min along the last axis (⧋ evert), and then ⊕ group into /+ sums.
10,7,7,1, the second row is9,7,7,2,9and the sum is59. And so on \$\endgroup\$