15
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Kevin Cruijssen Oct 17 '17 at 8:01
  • \$\begingroup\$ @KevinCruijssen Sure, added \$\endgroup\$ – user2390246 Oct 17 '17 at 8:16
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – user2390246 Oct 17 '17 at 10:24

11 Answers 11

10
\$\begingroup\$

Jelly, 15 bytes

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

Try it online!

How it works

,ZṚ¥;ŒD$+⁹\€€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.
        +⁹\€€    Take the sums of length n of each flat array.
             FṀ  Flatten and take the maximum.
\$\endgroup\$
  • \$\begingroup\$ Nice abuse of ¥ there... \$\endgroup\$ – Erik the Outgolfer Oct 16 '17 at 18:17
  • \$\begingroup\$ 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. \$\endgroup\$ – user202729 Oct 17 '17 at 0:56
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Oct 17 '17 at 0:36
  • 1
    \$\begingroup\$ For TIO-friendly version (Mathematica script mode): The character U+F3C7 (\[Transpose]) can be typed in as \:f3c7. \$\endgroup\$ – user202729 Oct 17 '17 at 1:07
  • 3
    \$\begingroup\$ Also I believe it is not the first time Tr is used as trace. \$\endgroup\$ – user202729 Oct 17 '17 at 1:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Misha Lavrov Oct 17 '17 at 1:12
  • 3
    \$\begingroup\$ I know I've said that before, but non-ASCII code should work just fine now. Try it online! \$\endgroup\$ – Dennis Oct 17 '17 at 1:31
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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}) \$\endgroup\$ – JungHwan Min Oct 16 '17 at 20:56
  • \$\begingroup\$ @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. \$\endgroup\$ – user202729 Oct 17 '17 at 1:06
  • \$\begingroup\$ @user202729 Thanks, didn't know! \$\endgroup\$ – JungHwan Min Oct 17 '17 at 1:19
3
\$\begingroup\$

Jelly, 16 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Wow our solutions are nearly identical... Mine was µ;Z;UŒD$;ŒDṡ€⁴ẎS€Ṁ \$\endgroup\$ – Mr. Xcoder Oct 16 '17 at 17:01
  • \$\begingroup\$ @Mr.Xcoder Oh wow cool :P \$\endgroup\$ – HyperNeutrino Oct 16 '17 at 17:35
3
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ 1/s instead of s==s should work as expected. \$\endgroup\$ – Arnauld Oct 17 '17 at 14:56
  • \$\begingroup\$ Getting rid of both eval's: 130 bytes \$\endgroup\$ – Arnauld Oct 17 '17 at 15:31
  • \$\begingroup\$ @Arnauld Thanks. And change (s=(g=...)(n))>m?s:m to (g=...)(n)>m?g(n):m save 1 byte. \$\endgroup\$ – tsh Oct 18 '17 at 1:06
2
\$\begingroup\$

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I hope I missed it, but R seems to be lacking a base function to compute the trace of a square matrix. \$\endgroup\$ – NofP Oct 28 '17 at 23:57
  • \$\begingroup\$ Haven't worked out if it would save you bytes, but you can use sum(diag(m)) for the trace \$\endgroup\$ – user2390246 Oct 29 '17 at 8:59
1
\$\begingroup\$

Husk, 14 bytes

▲mΣṁX⁰ṁëIT∂(∂↔

Try it online!

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

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ @HermanLauenstein i remove the spaces but added more coverage which added in total more chars, but thx :) \$\endgroup\$ – DanielIndie Oct 16 '17 at 18:00
  • \$\begingroup\$ 164 bytes by removing unnecessary newlines (G= is not counted) \$\endgroup\$ – Herman L Oct 16 '17 at 18:03
  • \$\begingroup\$ Why did you use a||M,b||M,c||M,d||M instead of a,b,c,d? \$\endgroup\$ – Herman L Oct 16 '17 at 18:11
  • \$\begingroup\$ @HermanLauenstein Math.max(NaN/undefined, 6) = NaN \$\endgroup\$ – DanielIndie Oct 16 '17 at 19:15
0
\$\begingroup\$

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!

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