Sum the diagonals

Question

Take a matrix of positive integers as input, and output the individual sums of the elements on the diagonal lines through the matrix.

You shall only count the lines that goes diagonally down and to the right. You must start with the diagonal that contains only the bottom-left element, then the length-two diagonal above that (if it exists) and so on through to the diagonal that contains only the top-right element, as illustrated below.

Example:

Input:
 8   14    5    1
10    5    5    8
 6    6    8   10
15   15    4   11

Output:
15, 21, 20, 32, 29, 13, 1
(Diagonals: {{15},{6,15},{10,6,4},{8,5,8,11},{14,5,10},{5,8},{1}})

Input:
1
Output:
1

Input: 
1 5
Output:
1, 5

Input:
4
1

Output: 
1, 4

Input:
17    4    5
24   16    5
 9   24   10
 1   14   22
 1   21   24
 4    4   17
24   25   17

Output:
24, 29, 22, 39, 47, 70, 43, 9, 5

Input and output formats are optional as always.

This is code-golf, so the shortest submission in each language wins.

\$\begingroup\$ Related \$\endgroup\$
– nimi
May 11, 2017 at 21:44 — nimi, May 11, 2017 at 21:44

Community · Accepted Answer · 2020-06-17 09:04:33Z

Haskell, 40 37 bytes

z=0:z
foldl1$(.(++z)).zipWith(+).(0:)

Try it online! Usage: (foldl1$(.(++z)).zipWith(+).(0:)) [[1,2,3],[4,5,6]].

Edit: Thanks to Ørjan Johansen for -3 bytes!

Ungolfed:

z = 0:z
s#t = zipWith(+)(0:s)(t++z)
f m = foldl1 (#) m

z is a list of infinitely many zeros. In f we fold over the list of lists m by combining two lists with the function #. In # the first list s contains the accumulated column sums so far and the second list t is the new row which should be added. We shift s one element to the right by adding a zero to the front and element-wise add s and t with zipWith(+). Because s might be arbitrarily large, we have to pad t with enough zeros by appending z.

That's shorter point-free: foldl1$(.(++z)).zipWith(+).(0:). — Ørjan Johansen, May 11, 2017 at 23:36

Greg Martin · Accepted Answer · 2017-05-12 18:41:38Z

6

Mathematica, 53 54 bytes

l=Length@#-1&;Tr@Diagonal[#,k]~Table~{k,-l@#,l@#&@@#}&

Pure function taking a 2D-array as input and returning a list. (Entries don't have to be integers or even numbers.) Diagonal[#,k] returns the kth diagonal above (or below, if k is negative) the main diagonal. {k,-l@#,l@#&@@#} computes the range of diagonals needed based on the dimensions of the input array. And Tr sums the entries of each diagonal.

edited May 12, 2017 at 18:41

answered May 11, 2017 at 22:04

Greg Martin

15.4k4 gold badges19 silver badges69 bronze badges

\$\begingroup\$ Alternative at the same byte count, but maybe you can golf it further? Those parentheses look bad. Tr@Diagonal[m,#]&/@Range@@({-1,1}(Dimensions[m=#]-1))& \$\endgroup\$
– Martin Ender
May 13, 2017 at 9:53

Add a comment |

Luis Mendo · Accepted Answer · 2017-05-11 21:58:44Z

5

MATL, 6 bytes

T&XdXs

Try it online! Or verify all test cases.

Explanation

T&Xd   % All diagonals of implicit input arranged as zero-padded columns
Xs     % Sum of each column. Implicitly display

edited May 11, 2017 at 21:58

answered May 11, 2017 at 21:49

Luis Mendo

104k9 gold badges132 silver badges365 bronze badges

\$\begingroup\$ Just curious: Do you think it would be better overall to have s==sum(x(:)), instead of sticking to the MATLAB convention, as MATL seems to do? \$\endgroup\$
– Stewie Griffin
May 12, 2017 at 8:43
\$\begingroup\$ @StewieGriffin I have sometimes thought about that. My doubt was more between sum(x) and sum(x,1). For a matrix x, the fact that sum(x) behaves differently if the matrix has 1 row is sometimes annoying. But in the end I decided to go with Matlab, so the two languages are closer; and add some fun(x,1) functions for the most common cases \$\endgroup\$
– Luis Mendo
May 12, 2017 at 8:59

Add a comment |

Dennis · Accepted Answer · 2017-05-12 04:00:43Z

5

Jelly, 5 bytes

0;+µ/

Try it online!

How it works

0;+µ/  Main link. Argument: M (matrix / array of rows)

   µ   Combine all links to the left into a chain (arity unknown at parse time) and
       begin a new monadic chain.
    /  Reduce M by that chain. This makes the chain dyadic.
       Let's call the arguments of the chain L and R (both flat arrays).
0;         Prepend a 0 to L.
  +        Perform element-wise addition of the result and R.
           When the chain is called for the n-th time, R has n less elements, so
           the last n elements of L won't have matching elements in R and will be
           left unaltered.

edited May 12, 2017 at 4:00

answered May 12, 2017 at 3:16

Dennis

210k41 gold badges368 silver badges819 bronze badges

\$\begingroup\$ Only the first R to reduce has one less element; it increases by one more element each row. \$\endgroup\$
– Ørjan Johansen
May 12, 2017 at 3:39
\$\begingroup\$ This is just clever... no ŒD? \$\endgroup\$
– Erik the Outgolfer
May 13, 2017 at 10:07
\$\begingroup\$ @EriktheOutgolfer Once again, ŒD's weird ordering prevented it from being useful. \$\endgroup\$
– Dennis
May 13, 2017 at 15:47
\$\begingroup\$ @Dennis Then I think I'd make something that doesn't have so weird ordering... oh, maybe 3 monads might be incoming. \$\endgroup\$
– Erik the Outgolfer
May 13, 2017 at 15:54

Add a comment |

Neil · Accepted Answer · 2017-05-13 10:04:08Z

5

JavaScript (ES6), 65 58 bytes

a=>a.map(b=>b.map((c,i)=>r[i]=~~r[i]+c,r=[,...r]),r=[])&&r

edited May 13, 2017 at 10:04

answered May 11, 2017 at 21:42

Neil

166k12 gold badges69 silver badges273 bronze badges

\$\begingroup\$ 63-byte variant: a=>a.map(r=>r.map(v=>s[i]=~~s[i++]+v,i=--y),s=[],y=a.length)&&s \$\endgroup\$
– Arnauld
May 13, 2017 at 9:57
\$\begingroup\$ @Arnauld I agree, reversing was a bad move. But taking the length is too long too! \$\endgroup\$
– Neil
May 13, 2017 at 10:04

Add a comment |

Business Cat · Accepted Answer · 2017-05-12 13:01:04Z

CJam, 22 21 bytes

Saved 1 byte thanks to Martin Ender

{_,({0\f+}*ee::m<:.+}

Anonymous block expecting the argument on the stack and leaves the result on the stack.

Try it online!

How it works

_                   e# Duplicate the matrix
 ,(                 e# Get its length (# of rows) minus 1
   {0\f+}*          e# Prepend that many 0s to each row
          ee        e# Enumerate; map each row to [index, row]
            ::m<    e# Rotate each row left a number of spaces equal to its index
                :.+ e# Sum each column

Emigna · Accepted Answer · 2017-05-11 22:12:05Z

2

05AB1E, 17 bytes

Rvy¹gÅ0«NFÁ}})øO¨

Try it online!

Explanation

R                  # reverse input
 v                 # for each N,y (index, item)
  y¹gÅ0«           # pad y with as many zeroes as the number of rows in the input
        NFÁ}       # rotate each row N times right
            })     # wrap the result in a list
              øO   # sum the columns
                ¨  # remove the last element of the resulting list (the padded zeroes)

edited May 11, 2017 at 22:12

answered May 11, 2017 at 22:01

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

Add a comment |

Conor O'Brien · Accepted Answer · 2017-05-12 02:36:53Z

2

J, 7 bytes

+//.@|.

Try it online!

This is pretty simple:

+//.@|.
+/        sum
  /.      on oblique lines
    @|.   on the reversed array

Oblique reversed lines are the diagonals of the array, so this is just summing the diagonals.

answered May 12, 2017 at 2:36

Conor O'Brien

39.9k3 gold badges88 silver badges178 bronze badges

Add a comment |

Dennis · Accepted Answer · 2017-05-12 07:38:16Z

2

Python 2, 62 bytes

lambda M:reduce(lambda x,y:map(sum,zip([0]+x,y+[0]*len(x))),M)

Try it online!

answered May 12, 2017 at 7:38

Dennis

210k41 gold badges368 silver badges819 bronze badges

Add a comment |

Jonathan Allan · Accepted Answer · 2017-05-11 22:34:26Z

Jelly, 8 bytes

ŒDS€ṙZL$

Try it online!

Half of the code is used to put the results into the correct order.

How?

ŒDS€ṙZL$ - Main link: list of lists of numbers
ŒD       - diagonals (starts with the diagonal containing the top left element,
         -            then the next diagonal to the right, and so on wrapping around)
  S€     - sum €each
       $ - last two links as a monad
     Z   - transpose the matrix
      L  - length (width of the matrix)
    ṙ    - rotate the results left by that amount

faubi · Accepted Answer · 2017-05-12 03:21:53Z

1

Perl 5, 47 bytes

map{$j=--$.;map{@a[$j++]+=$_}split}<>
print"@a"

answered May 12, 2017 at 3:21

faubi

2,6191 gold badge12 silver badges11 bronze badges

Add a comment |

Billywob · Accepted Answer · 2017-05-12 18:12:02Z

1

R, 45 bytes

Unnamed function taking a matrix-class object as input:

function(x)sapply(split(x,col(x)-row(x)),sum)

Using the idea explained in this answer.

edited May 12, 2017 at 18:12

answered May 12, 2017 at 15:47

Billywob

3,49311 silver badges16 bronze badges

\$\begingroup\$ I believe the rules in this challenge allow for you to get rid of the call to unname, but this is an awesome solution regardless! \$\endgroup\$
– Giuseppe
May 12, 2017 at 18:06

Add a comment |

Stewie Griffin · Accepted Answer · 2017-05-13 09:32:54Z

1

Octave, 71 bytes

Assuming A is a matrix, for example:

A = [17 4 5;24 16 5; 9 24 10; 1 14 22; 1 21 24; 4 4 17;24 25 17];

Then we have:

[m,n]=size(A);
a=[zeros(m,m-1),A]';
for i=1:m+n-1
trace(a(i:end,:))
end

Notice that transposing the matrix reverses the ordering of the diagonal sums, which saved an overall two bytes in the for loop.

Output:

ans =  24
ans =  29
ans =  22
ans =  39
ans =  47
ans =  70
ans =  43
ans =  9
ans =  5

edited May 13, 2017 at 9:32

Stewie Griffin

46.2k13 gold badges128 silver badges294 bronze badges

answered May 13, 2017 at 2:42

It Guy

913 bronze badges

1

\$\begingroup\$ [m,n]=size(A);for i=1:m+n-1,trace([zeros(m-1,m);A'](i:end,:)),end saves 6 bytes. Octave can do direct indexing and inline assignments. Unfortunately, assuming that a variable exist in the work space prior to running the code is not allowed, so I think you must use input, like this bringing it back up to 75 bytes. Nice approach though, so +1 from me :) And welcome to PPCG! =) \$\endgroup\$
– Stewie Griffin
May 13, 2017 at 9:31
\$\begingroup\$ Also, zeros(m-1,m) can be written ~e(m-1,m), saving 4 bytes :) Neat huh? \$\endgroup\$
– Stewie Griffin
May 13, 2017 at 10:20

Add a comment |

naffetS · Accepted Answer · 2022-07-14 18:51:13Z

1

Vyxal, 7 bytes

ÞD?L‹ǔṠ

Try it Online!

Takes 4 bytes to get it in the right order. If the order didn't matter, it would be 3 bytes (remove the ?L‹ǔ).

answered Jul 14, 2022 at 18:51

naffetS

12.2k2 gold badges17 silver badges48 bronze badges

Add a comment |

hyper-neutrino · Accepted Answer · 2017-05-11 22:31:03Z

0

Python, 126 bytes

x=input()
f=lambda k:[x[i+k][i]for i in range(len(x)-k)]
a=map(f,range(4)[::-1])
x=zip(*x)
print(map(sum,a+map(f,range(1,4))))

f only works on the lower triangular section, so I transpose it and get the upper triangular section that way. Don't know why the f function doesn't work for negative values (I changed f to be shorter because the part to get the negatives didn't work).

answered May 11, 2017 at 22:31

hyper-neutrino♦

41.3k5 gold badges65 silver badges221 bronze badges

\$\begingroup\$ I get an error for the last test case. tio.run/nexus/… \$\endgroup\$
– Dennis
May 12, 2017 at 7:50

Add a comment |

Khaled.K · Accepted Answer · 2017-05-11 22:52:02Z

0

C, 148 bytes

Try Online

s;g(int i,int j,int**m,int x){for(s=0;x;x--)s+=m[i++][j++];printf(" %d",s);}
k;f(int n,int**m){for(k=n;--k;)g(k,0,m,n-k);for(;k<n;k++)g(0,k,m,n-k);}

answered May 11, 2017 at 22:52

Khaled.K

1,4759 silver badges12 bronze badges

Add a comment |

Jörg Hülsermann · Accepted Answer · 2017-05-11 23:06:18Z

0

PHP, 81 Bytes

Take Input as 2 D Array

<?foreach($_GET as$k=>$v)foreach($v as$x=>$y)$r[$x-$k]+=$y;ksort($r);print_r($r);

Try it online!

answered May 11, 2017 at 23:06

Jörg Hülsermann

13.3k3 gold badges14 silver badges36 bronze badges

Add a comment |

Kevin · Accepted Answer · 2017-05-11 23:09:38Z

0

Awk, 67 Bytes

{for(f=0;f++<NF;)s[NF-NR+f]+=$f}END{i=0;while(i++<NR*2)print s[i]}

Ungolfed:

{
    for (f = 0; f++ < NF;)
        s[NF-NR+f] += $f
}
END {
    i = 0
    while (i++ < NR*2)
        print s[i]
}

Awk splits on whitespace $n is the nth field (1-indexed); NF is the number of fields on the line, NR is the number of the current row. Undefined variables are 0 and created on first use.

answered May 11, 2017 at 23:09

Kevin

5113 silver badges9 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

PHP, 86 bytes

a memory friendly solution in two variants:

<?for($i=$c=count($a=$_GET);--$i>-$c;print$s._)for($s=0,$d=$c;$d--;)$s+=$a[$i+$d][$d];
<?for($i=$c=count($a=$_GET);--$i>-$c;print$s._)for($s=$d=0;$d<$c;)$s+=$a[$i+$d][$d++];

takes input from script parameters, uses underscore as delimiter;
use default settings (not default php.ini) or try them online

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 12, 2017 at 7:59

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2017-05-12 09:22:14Z

0

Clojure, 81 bytes

#(apply map +(map(fn[i c](concat(repeat(-(count %)i 1)0)c(repeat i 0)))(range)%))

Quite verbose, as it pads lists with zeros so that we can just calculate the column-wise sum.

answered May 12, 2017 at 9:22

NikoNyrh

2,6319 silver badges8 bronze badges

Add a comment |

ZaMoC · Accepted Answer · 2017-05-12 15:50:08Z

0

mathematica 73 bytes

Plus@@@Table[Diagonal[Partition[#1,#2[[1]]],k],{k,-#2[[2]]+1,#2[[1]]-1}]&

This one works for ANY 2D-array m x n (not only nxn)
input the array at the end of the code like this (the last test case)

[{17,4,5,24,16,5,9,24,10,1,14,22,1,21,24,4,4,17,24,25,17},{3,7}]

{24, 29, 22, 39, 47, 70, 43, 9, 5}

input in form [{a,b,c,d...},{m,n}]

edited May 12, 2017 at 15:50

answered May 12, 2017 at 11:30

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Husk, 6 bytes

mΣ∂m↔T

Try it online.

Explanation:

     T  # Transpose the (implicit) argument; swapping rows/columns
   m↔   # Reverse each row
  ∂     # Take the anti-diagonals of this matrix
mΣ      # And sum each inner anti-diagonal list
        # (after which the result is output implicitly)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Apr 22, 2020 at 13:59

Kevin Cruijssen

123k11 gold badges135 silver badges374 bronze badges

Add a comment |

Stack Exchange Network

Sum the diagonals

22 Answers 22

Haskell, 40 37 bytes

Ungolfed:

Mathematica, 53 54 bytes

MATL, 6 bytes

Explanation

Jelly, 5 bytes

How it works

JavaScript (ES6), 65 58 bytes

CJam, 22 21 bytes

05AB1E, 17 bytes

J, 7 bytes

Python 2, 62 bytes

Jelly, 8 bytes

How?

Perl 5, 47 bytes

R, 45 bytes

Octave, 71 bytes

Vyxal, 7 bytes

Python, 126 bytes

C, 148 bytes

PHP, 81 Bytes

Awk, 67 Bytes

PHP, 86 bytes

Clojure, 81 bytes

mathematica 73 bytes

Husk, 6 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
matrix
or ask your own question.

Linked

Hot Network Questions

Sum the diagonals

22 Answers 22

Haskell, 40 37 bytes

Ungolfed:

Mathematica, 53 54 bytes

MATL, 6 bytes

Explanation

Jelly, 5 bytes

How it works

JavaScript (ES6), 65 58 bytes

CJam, 22 21 bytes

05AB1E, 17 bytes

J, 7 bytes

Python 2, 62 bytes

Jelly, 8 bytes

How?

Perl 5, 47 bytes

R, 45 bytes

Octave, 71 bytes

Vyxal, 7 bytes

Python, 126 bytes

C, 148 bytes

PHP, 81 Bytes

Awk, 67 Bytes

PHP, 86 bytes

Clojure, 81 bytes

mathematica 73 bytes

Husk, 6 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathmatrix or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
matrix
or ask your own question.