Find the greatest line

Question

You will be given a 2-D array A of integers, and a length N. Your task is to find within the array the straight line (horizontal, vertical or diagonal) of N elements that yields the highest total sum, and return that sum.

Example

 N = 3, A = 
 3 3 7 9 3
 2 2 10 4 1
 7 7 2 5 0
 2 1 4 1 3

This array has 34 valid lines, including

 Vertical
 [3] 3 7 9 3
 [2] 2 10 4 1
 [7] 7 2 5 0
 2 1 4 1 3 [3,2,7] = 12
 Horizontal
 3 3 7 9 3
 2 2 10 4 1
 7 7 [2] [5] [0]
 2 1 4 1 3 [2,5,0] = 7
 Diagonal
 3 3 [7] 9 3
 2 2 10 [4] 1
 7 7 2 5 [0]
 2 1 4 1 3 [7,4,0] = 11

The maximum line is

 3 3 7 [9] 3
 2 2 [10] 4 1
 7 [7] 2 5 0
 2 1 4 1 3 [7,10,9] = 26

Note: lines may not wrap around the edges of the array.

Inputs

• A X by Y 2-D array A, with X,Y> 0. Each element of the array contains an integer value which may be positive, zero or negative. You may accept this array in an alternative format (e.g. list of 1-D arrays) if you wish.
• A single, positive integer N, no greater than max(X,Y).

Output

• A single value representing the maximal line sum that can be found in the array. Note that you do not need to provide the individual elements of that line or where it is located.

Test cases

N = 4, A = 
-88 4 -26 14 -90
-48 17 -45 -70 85
 22 -52 87 -23 22
-20 -68 -51 -61 41
Output = 58
N = 4, A =
 9 4 14 7
 6 15 1 12
 3 10 8 13
16 5 11 2
Output = 34
N = 1, A = 
 -2
Output = -2
N = 3, A =
1 2 3 4 5
Output = 12
N = 3, A = 
-10 -5 4
 -3 0 -7
-11 -3 -2
Output = -5 

• Kevin Cruijssen: Could you add a test case where the resulting output is negative? Like [[-10, -5, 4],[-3, 0, -7],[-11,-3,-2]] -> -5 (4 + -7 + -2)
• user2390246: @KevinCruijssen Sure, added
• user2390246: By the way: all answers with an explanation will gain an upvote from me, but otherwise I have no way of judging languages that I'm not familiar with (and that's most of them).

Answer 1

Jelly, 15 bytes

,ZṚ\;ŒD$+9\€€FṀ

Try it online!

How it works

,ZṚ\;ŒD$+9\€€FṀ Main link. Left argument: M (matrix). Right argument: n (integer)
 ZṚ\ Zip/transpose and reverse M. This is equivalent to rotating M 90°
 counterclockwise.
, Pair M and the result to the right.
 ;ŒD$ Append the diagonals of both matrices to the pair.
 +9\€€ Take the sums of length n of each flat array.
 FṀ Flatten and take the maximum.

• Erik the Outgolfer: Nice abuse of ¥ there...
• user202729: For future (new) users: $ creates a monad from ZṚ, while ¥ creates a dyad from ZṚ which returns the result of the same function (rotate 90 CCW) applied on its left operand. Which matches the pattern + × and evaluate v+(λ×ρ) (it is v = v , (M ZṚ¥ n) in this case). However just use $ doesn't work because there is no + F pattern in dyadic chain.

Answer 2

Wolfram Language (Mathematica), 73 bytes

Max[Tr/@Join[#,#,{#,Reverse@#}]&/@Join@@Partition[#2,{#,#},1,1,-∞]]&

Try it online!

How it works

Takes first N and then the matrix A as input.

Join@@Partition[#2,{#,#},1,1,-∞] finds every N by N submatrix of the matrix A, padded with -∞ where necessary to ensure that lines running out of the grid will be out of the running.

For each of those blocks we compute Tr/@Join[#,#,{#,Reverse@#}]: the trace (i.e. sum) of each row, the trace (i.e. sum) of each column, the trace (actually the trace, for the first time in the history of Mathematica code golfing) of the block, and the trace of the block reversed. # is Transpose@#.

Then we find the Max of all of these.

• Misha Lavrov: For most inputs, the 57-byte Max@BlockMap[Tr/@Join[#,#,{#,Reverse@#}]&,#2,{#,#},1]& also works. But we need to pad with -∞ to handle cases where A has fewer than N rows or columns, and BlockMap doesn't support padding.
• user202729: For TIO-friendly version (Mathematica script mode): The character U+F3C7 (\[Transpose]) can be typed in as \:f3c7.
• user202729: Also I believe it is not the first time Tr is used as trace.
• Misha Lavrov: Thanks! And when I'm not exaggerating, I'm sure using Tr as the trace of a matrix has come up before, but it's still rare and surprising.
• Dennis: I know I've said that before, but non-ASCII code should work just fine now. Try it online!

Answer 3

Mathematica, (削除) 135 (削除ここまで) 123 bytes

Max[(s=#;r=#2;Max[Tr/@Partition[#,r,1]&/@Join[s,s~Diagonal~#&/@Range[-(t=Tr[1^#&@@s])+2,t-1]]])&@@@{#|#2,Reverse@#|#2}]&

Try it online!

• JungHwan Min: Some optimizations: Diagonal[s,#] to s~Diagonal~#, and {{Transpose@#,#2},{Reverse@#,#2}} to {#|#2,Reverse@#|#2}. (The unprintable is U+F3C7 = \[Transpose]; TIO doesn't seem to like this, though. Alternative: {Transpose@#|#2,Reverse@#|#2})
• user202729: @JungHwanMin It's not TIO's fault, Mathematica on TIO is run in script mode, which only support ASCII. You need to type \[Transpose] or \:f3c7 (at least the latter is shorter than Thread@) However if the answer is Mathematica REPL (not Mathematica script) you can assume the 3-byte solution.
• JungHwan Min: @user202729 Thanks, didn't know!

Answer 4

Jelly, 16 bytes

μ;Z;Uμ;ŒDðṡ€ẎS€Ṁ

Try it online!

• Mr. Xcoder: Wow our solutions are nearly identical... Mine was µ;Z;UŒD$;ŒDṡ4ドルẎS€Ṁ
• hyperneutrino: @Mr.Xcoder Oh wow cool :P

Answer 5

JavaScript, (削除) 151 (削除ここまで) 129 bytes

a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m

Curry function takes two arguments, first one is an array of array of numbers, second one is a number.

Thanks to Arnauld, save 20+ bytes.

f=
a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m

<p><label>N = <input id="N" type="number" min="1" value="3" /></label></p>
<p><label>A = <textarea id="A" style="width: 400px; height: 200px;"> 3 3 7 9 3
 2 2 10 4 1
 7 7 2 5 0
 2 1 4 1 3
</textarea></label></p>
<input value="Run" type="button" onclick="O.value=f(A.value.split('\n').filter(x=>x.trim()).map(x=>x.trim().split(/\s+/).map(Number)))(+N.value)" />
<p>Result = <output id="O"></output></p>

• Arnauld: 1/s instead of s==s should work as expected.
• Arnauld: Getting rid of both eval's: 130 bytes
• tsh: @Arnauld Thanks. And change (s=(g=...)(n))>m?s:m to (g=...)(n)>m?g(n):m save 1 byte.

Answer 6

Jq 1.5, 211 bytes

def R:reverse;def U:[range(length)as$j|.[$j][$j:]]|transpose|map(map(select(.))|select(length>=N));def D:U+([R[]|R]|U|map(R)[1:]);[A|.,transpose,D,(map(R)|D)|.[]|range(length-N+1)as$i|.[$i:$i+N]]|max_by(add)|add

Expects input in N and A, e.g:

def N: 3;
def A: [
 [ 3, 3, 7, 9, 3 ],
 [ 2, 2, 10, 4, 1 ],
 [ 7, 7, 2, 5, 0 ],
 [ 2, 1, 4, 1, 3 ]
];

Expanded

def chunks: .[] | range(length-N+1) as $i | .[$i:$i+N] ;
def flip: [ reverse[] | reverse ] ;
def upperdiag: [ range(length) as $j | .[$j][$j:] ] | transpose | map(map(select(.))|select(length>=N)) ;
def lowerdiag: flip | upperdiag | map(reverse)[1:] ;
def diag: upperdiag + lowerdiag ;
def allchunks: A | ., transpose, diag, (map(reverse)|diag) | chunks ;
[allchunks]|max_by(add)|add

Note this challenge is basically the same as Project Euler problem 11

Try it online!

Answer 7

Python 2, (削除) 208 (削除ここまで) (削除) 184 (削除ここまで) (削除) 183 (削除ここまで) 176 bytes

• Saved 24 bytes by using -float("inf") to represent that the checked line reached outside the matrix instead of computing the negative sum of all matrix elements.
• Saved a byte by defining R,L=range,len to shorten built-in functions and using y in R(L(A))...R(L(A[y])) instead of y,Y in e(A)...x,_ in e(Y).
• Saved seven bytes by golfing float("inf") to 9e999.

lambda N,A:max(sum(A[y+q*j][x+p*j]if-1<x+p*j<L(A[y])>-1<y+q*j<L(A)else-9e999for j in R(N))for y in R(L(A))for x in R(L(A[y]))for p,q in[(1,0),(0,1),(1,1),(1,-1)]);R,L=range,len

Try it online!

Explanation

lambda N,A: ;R,L=range,len # lambda function, golfed built-ins
 max( ) # return the maximum line sum
 for y in R(L(A)) # loop through matrix rows
 for x in R(L(A[y])) # loop through matrix columns
 for p,q in[(1,0),(0,1),(1,1),(1,-1)] # loop through four directions; east, south, south-east, north-east
 sum( ) # matrix line sum
 for j in R(N) # loop through line indices
 if-1<x+p*j<L(A[y])>-1<y+q*j<L(A) # coordinates inside the matrix?
 A[y+q*j][x+p*j] # true; look at the matrix element
 else-9e999 # false; this line cannot be counted, max(...) will not return this line

Answer 8

R, 199 bytes

function(m,n,i=1,j=1){y=1:n-1
x=j-y;x[x<1]=NA
y=i-y;y[y<1]=NA
'if'(i>nrow(m)|j>ncol(m),NA,max(c(v(m[i,x]),v(m[y,j]),v(m[b(y,x)]),v(m[b(y,rev(x))]),f(m,n,i+1,j),f(m,n,i,j+1)), na.rm=T))}
v=sum
b=cbind

Try it online!

A recursive solution. For each element (i,j) of the matrix it returns the max between the sum along the row, the sum along the column, the sum along either diagonal, and the result of the function applied to (i+1,j) and (i,j+1). Results for the test cases are shown in the TIO.

• NofP: I hope I missed it, but R seems to be lacking a base function to compute the trace of a square matrix.
• user2390246: Haven't worked out if it would save you bytes, but you can use sum(diag(m)) for the trace

Answer 9

Husk, 14 bytes

▲さんかくmΣṁX0ṁëIT∂(∂↔

Try it online!

Thanks to the new anti∂iagonals builtin this is a quite short answer :)

Answer 10

JavaScript 170 bytes

still wip on the golf part added 4 more chars because i didnt managed a case where the max is negative and N is bigger than 1

M=-1e9
G=(A,N)=>eval(`for(y in m=M,A)
for(x in R=A[y])
{for(a=b=c=d=j=0;j<N;d+=Y[x-j++])
{a+=R[X=+x+j]
b+=(Y=A[+y+j]||[])[x]
c+=Y[X]}
m=Math.max(m,a||M,b||M,c||M,d||M)}`)
console.log(G([ [3,3,7,9,3],
 [2,2,10,4,1],
 [7,7,2,5,0],
 [2,1,4,1,3]],3)==26)
 
 console.log(G([[-88,4,-26,14,-90],
[-48,17,-45,-70,85],
[22,-52,87,-23,22],
[-20,-68,-51,-61,41]],4)==58)
console.log(G([[9,4,14,7],[6,15,1,12],[3,10,8,13],[16,5,11,2]],4)==34)
console.log(G([[-2]],1)==-2)
console.log(G([[1,2,3,4,5]],3) ==12)

• DanielIndie: @HermanLauenstein i remove the spaces but added more coverage which added in total more chars, but thx :)
• Endenite: 164 bytes by removing unnecessary newlines (G= is not counted)
• Endenite: Why did you use a||M,b||M,c||M,d||M instead of a,b,c,d?
• DanielIndie: @HermanLauenstein Math.max(NaN/undefined, 6) = NaN

Answer 11

Python 2, (削除) 222 (削除ここまで) 218 bytes

n,a=input()
W=len(a[0]);Q=['']*W;R=range;a+=[Q]*n
for l in a:l+=Q
print max(sum(x)for y in[zip(*[(a[j][i+k],a[j+k][i],a[j+k][i+k],a[j+k][i+n+~k])for k in R(n)])for j in R(len(a)-n)for i in R(W)]for x in y if''not in x)

Try it online!

• Jonathan Frech: Possible 219 bytes.
• Jonathan Frech: Possible 218 bytes.