Matrix trace for any matrix through… Bresenham’s line rasterisation

Inspired by this.

Agatha Stephendale, a sophomore who is really into raster graphics, has taken a course in linear algebra. Now she imagines matrices as rectangles, but in her artistic mind, she attaches diagonal lines to those rectangles and tries to compute traces along them. In fact, she wants to compute traces of all matrices, not just square ones.

Since Agatha is an artist, she knows how to draw lines in her favourite image editor, and the latter uses Bresenham’s algorithm to plot lines. She even checked Wikipedia and found the pseudocode:

 function line(x0, y0, x1, y1)
real deltax := x1 - x0
real deltay := y1 - y0
real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
// note that this division needs to be done in a way that preserves the fractional part
real error := 0.0 // No error at start
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
while error ≥ 0.5 then
y := y + sign(deltay) * 1
error := error - 1.0


(Note that this pseudocode works only for slopes less than 1; for tall grids, a similar treatment should be done, but with a loop over y. See this section for the two cases.)

Agatha imagines a matrix as a rectangle, draws a diagonal line in it, and Bresenham’s algorithm determines which elements of a matrix belong to the diagonal. Then she takes their sum, and this is what she wants to implement in as few bytes as possible because she is a poor student and cannot afford large-capacity HDDs to store her code.

Given a matrix A, return the sum of the elements that lie on the rasterised main diagonal (from top left to bottom right), where the latter is determined by Bresenham’s line algorithm. That is, assuming that the matrix represents a m×n grid, draw a line on that grid from A[1, 1] to A[m, n] using Bresenham’s algorithm, and take the sum of all elements on the line. Note that for 1×N and N×1 matrices, the entire matrix becomes its own diagonal (because this is how one would draw a line from the first element of the first row to the last element of the last row).

Input: a real matrix (may be a 1×1 matrix, a row matrix, a column matrix, or a rectangular matrix). Output: a number.

Note that some sources (e. g. the Wikipedia’s pseudocode above) use the condition check error≥0.5, while other sources use error>0.5. You should use the originally posted one (error≥0.5), but if the alternative error>0.5 is shorter in your code, then you are allowed to implement it (since this is code golf), but mention it explicitly. See test case 4.

Challenge rules

• I/O formats are flexible. A matrix can be several lines of space-delimited numbers separated by newlines, or an array of row vectors, or an array of column vectors etc.
• This is , so shortest answer in bytes wins.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs.
• Default loopholes are forbidden.

Test cases

1. [[1,2,3],[4,5,6],[7,8,9]]1+5+9 → output: 15.

1. [[1,2,3,4],[5,6,7,8]]1+2+7+8 → output: 18.

1. [[1,2,3,4,5,6],[7,8,9,10,11,12],[13,14,15,16,17,18],[19,20,21,22,23,24]]1+8+9+16+17+24 → output: 75.

1. [[1,2,3,4,5],[6,7,8,9,10]]1+2+8+9+10 (using the ≥ error condition) → output: 30.

However, if it would be shorter to use the strict inequality > in your code, then the allowed output is 1+2+3+9+10=25, but you should mention it separately.

1. [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]1+5+8+12 → output: 26.

1. [[-0.3,0.5]] → output: 0.2.

2. [[3.1],[2.9]] → output: 6.

3. [[-5]] → output: -5.

• Requested test case: [[1,2,3,4,5],[6,7,8,9,10]]. – user202729 Mar 23 '18 at 8:12
• @user202729 Added it to resolve ambiguity. – Andreï Kostyrka Mar 23 '18 at 9:51
• Can we get a test case that's taller than it is wide? Like [[1,2],[3,4],[5,6],[7,8],[9,10]] – Giuseppe Mar 23 '18 at 13:34
• @Giuseppe Catch. See case 5 now. For your example, the answer should be 28 (with ≥, the expected implementation) or 27 (with >, the optional implementation.) – Andreï Kostyrka Mar 23 '18 at 14:56
• Can the program only support matrices up to a fixed size (say, 500×500)? – user202729 Apr 1 '18 at 3:54

Jelly, 25 bytes

ZXL>LƲ¡µLḶ÷’Ɗ×XL’Ɗær0ị"OS


Try it online!

• If Jelly had 1 or 2-byte round to nearest integer built-in, this answer would be 23 or 24 bytes. – user202729 Mar 23 '18 at 10:23

SmileBASIC, 101 99 bytes

DEF D A,W,H
GCLS
GTRI.,0,0,0,W-1,H-1FOR I=0TO W*H-1=I MOD W
S=S+A[I/W,M]*!!GSPOIT(M,I/W)NEXT?S
END


I originally thought of using the GLINE function to draw a line, but it doesn't appear to use the correct algorithm. However, GTRI does seem to work,

Test case 4 outputs 30.

Input is a 2D array in [Y,X] form, along with the width/height (there's no way to check the dimensions of an array, only the total number of elements).

FMSLogo, 136 bytes

make 1 rl
setxy -1+count :1 -1+count last :1
pu home
make 9 0
foreach :1[foreach ?[if
0=last pixel[make 9 :9+?]fd 1]setxy xcor+1 0]pr :9


Full program, prompt the user for input (dialog box popup) and then print the output to the screen.

Just draw a line on the screen and calculate the output. Use strict inequality.

This only supports matrix size up to FMSLogo's canvas size (about 500×500)

Ungolfed code:

Make "input ReadList
SetXY (-1+Count :input) (-1+Count Last :input)
PenUp
Home
Make "sum 0
ForEach :input[
ForEach ?[
If 0=Last Pixel[
Make "sum :sum+?
]
Forward 1
]
SetXY XCor+1 0
]
Print :sum


JavaScript (ES6), 110 103 bytes

Outputs 25 for the 4th test case.

a=>(X=a[x=y=0].length-1,Y=1-a.length,g=e=>a[y][x]+(x-X|y+Y&&g(e+(e*2>Y&&++x&&Y)+(e*2<X&&++y&&X))))(X+Y)


Try it online!

Or 88 bytes if taking the dimensions of the matrix as input is allowed.

Python 3.X, 269 bytes

With input as comma-delimited rows of space-delimited numbers.

import math;c=math.ceil;a=[[float(k)for k in q.split(" ")]for q in input().split(",")];_=len;m=lambda f,t,x,y,e,d:sum(x[0]for x in a)if 2>_(a[0])else m(*[0]*4,*[(_(a)-1)/(_(a[0])-1)]*2)if f else m(f,t+a[y][x],x+1,y+c(e-0.5),e+d-c(e-0.5),d)if x<_(a[0])else t;m(1,*[0]*5)

Pre-golfing:

def line(a):
if len(a[0])<2: return sum([x[0] for x in a])
e = d = abs((len(a)-1)/(len(a[0])-1))
y=t=0
for x in range(len(a[0])):
t += a[y][x]
f = ceil(e-0.5)
y += f
e += d-f
return t

• It looks like that the c=math.ceil make the program longer... – user202729 Mar 24 '18 at 4:26
• Also, you don't need the [] between the sum(..). a if c else b can often be c and a or b. – user202729 Mar 24 '18 at 4:27
• input("") can be input(). – user202729 Mar 24 '18 at 4:28
• Also... what is the input/output format? Print to screen? – user202729 Mar 24 '18 at 4:28