Finde die beste Linie

14

Sie erhalten ein 2D-Array A mit ganzen Zahlen und eine Länge N. Ihre Aufgabe ist es, innerhalb des Arrays die gerade Linie (horizontal, vertikal oder diagonal) von N Elementen zu finden, die die höchste Gesamtsumme ergibt, und diese Summe zurückzugeben .

Beispiel

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

Dieses Array enthält 34 gültige Zeilen, einschließlich

 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

Die maximale Linie ist

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

Hinweis: Linien dürfen nicht um die Ränder des Arrays gewickelt werden.

Eingänge

  • AX durch Y 2-D-Array A mit X, Y> 0. Jedes Element des Arrays enthält einen ganzzahligen Wert, der positiv, null oder negativ sein kann. Sie können dieses Array in einem anderen Format (z. B. Liste von 1-D-Arrays) akzeptieren, wenn Sie dies wünschen.
  • Eine einzelne positive ganze Zahl N, nicht größer als max (X, Y).

Ausgabe

  • Ein einzelner Wert, der die maximale Zeilensumme darstellt, die im Array gefunden werden kann. Beachten Sie, dass Sie die einzelnen Elemente dieser Zeile oder deren Position nicht angeben müssen.

Testfälle

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 
user2390246
quelle
Könnten Sie einen Testfall hinzufügen, bei dem die resultierende Ausgabe negativ ist? Like [[-10, -5, 4],[-3, 0, -7],[-11,-3,-2]]-> -5( 4 + -7 + -2)
Kevin Cruijssen
@ KevinCruijssen Sicher, hinzugefügt
user2390246
1
Übrigens: Alle Antworten mit einer Erklärung werden von mir positiv bewertet, aber ansonsten kann ich keine Sprachen beurteilen, mit denen ich nicht vertraut bin (und das sind die meisten von ihnen).
user2390246

Antworten:

10

Gelee , 15 Bytes

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

Probieren Sie es online!

Wie es funktioniert

,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.
Dennis
quelle
Nizza Missbrauch von ¥dort ...
Erik der Outgolfer
Für zukünftige (neue) Benutzer: $Erstellt eine Monade aus ZṚ, während ¥eine Dyade erstellt wird, aus ZṚder das Ergebnis der gleichen Funktion (um 90 CCW drehen) zurückgegeben wird, die auf den linken Operanden angewendet wird. Welche passt zum Muster + ×und bewerten v+(λ×ρ)(ist es v = v , (M ZṚ¥ n)in diesem Fall). Jedoch $funktioniert die Verwendung nicht, da die + Fdyadische Kette kein Muster enthält.
user202729
6

Wolfram Language (Mathematica) , 73 Byte

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

Probieren Sie es online!

Wie es funktioniert

Nimmt zuerst Ndie Matrix Aals Eingabe.

Join@@Partition[#2,{#,#},1,1,-∞]findet jede Ndurch NSubmatrix der Matrix A, aufgefüllt mit, -∞wo nötig, um sicherzustellen, dass Linien, die aus dem Gitter herauslaufen, nicht mehr laufen.

Für jeden dieser Blöcke berechnen wir Tr/@Join[#,#,{#,Reverse@#}]: die Spur (dh die Summe) jeder Zeile, die Spur (dh die Summe) jeder Spalte, die Spur ( tatsächlich die Spur, zum ersten Mal in der Geschichte des Mathematica-Code-Golfspiels) des Blocks , und die Spur des Blocks kehrt sich um. #ist Transpose@#.

Dann finden wir die Maxvon all diesen.

Mischa Lawrow
quelle
Bei den meisten Eingängen Max@BlockMap[Tr/@Join[#,#,{#,Reverse@#}]&,#2,{#,#},1]&funktioniert auch das 57-Byte-Format . Aber wir müssen auffüllen -∞, um Fälle zu behandeln, in denen Aweniger als NZeilen oder Spalten vorhanden sind und BlockMapdas Auffüllen nicht unterstützt wird.
Mischa Lawrow
1
Für TIO-freundliche Version (Mathematica-Skriptmodus): Das Zeichen U + F3C7 ( \[Transpose]) kann wie folgt eingegeben werden \:f3c7.
user202729
3
Auch ich glaube es wird nicht das erste mal Trals Spur verwendet.
user202729
Vielen Dank! Und wenn ich nicht übertreibe, bin ich mir sicher, dass Trdie Spur einer Matrix schon einmal aufgetaucht ist, aber sie ist immer noch selten und überraschend.
Mischa Lawrow
3
Ich weiß, dass ich das schon einmal gesagt habe, aber Nicht-ASCII-Code sollte jetzt einwandfrei funktionieren. Probieren Sie es online!
Dennis
4

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}]&


Probieren Sie es online!

J42161217
quelle
Einige Optimierungen: Diagonal[s,#]zu s~Diagonal~#und {{Transpose@#,#2},{Reverse@#,#2}}zu {#|#2,Reverse@#|#2}. (Die nicht druckbaren ist U + F3C7 = \[Transpose]; TIO scheint nicht wie diese, obwohl Alternative:. {Transpose@#|#2,Reverse@#|#2})
JungHwan Min
@JungHwanMin Es ist nicht die Schuld von TIO, Mathematica on TIO wird im Skriptmodus ausgeführt, der nur ASCII unterstützt. Sie müssen Folgendes eingeben \[Transpose]oder \:f3c7(zumindest ist letzteres kürzer als Thread@). Wenn die Antwort jedoch Mathematica REPL (nicht Mathematica-Skript) lautet, können Sie die 3-Byte-Lösung annehmen.
user202729
@ user202729 Danke, wusste es nicht!
JungHwan Min 17.10.17
3

Gelee , 16 Bytes

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

Probieren Sie es online!

HyperNeutrino
quelle
Wow, unsere Lösungen sind fast identisch ... Meins warµ;Z;UŒD$;ŒDṡ€⁴ẎS€Ṁ
Mr. Xcoder 16.10.17
@ Mr.Xcoder Oh wow cool: P
HyperNeutrino
3

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

Die Curry-Funktion akzeptiert zwei Argumente, das erste ist ein Array von Zahlen, das zweite ist eine Zahl.

Sparen Sie dank Arnauld mehr als 20 Bytes.

tsh
quelle
1/sstatt s==ssollte wie erwartet funktionieren.
Arnauld
Beide Evals loswerden: 130 Bytes
Arnauld
@ Arnauld Danke. Und ändern Sie (s=(g=...)(n))>m?s:m, (g=...)(n)>m?g(n):mum 1 Byte zu speichern.
Dienstag,
2

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

Erwartet Eingaben in Nund A, zB:

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 ]
];

Erweitert

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

Beachten Sie, dass diese Herausforderung im Prinzip mit Project Euler-Problem 11 identisch ist

Probieren Sie es online!

jq170727
quelle
1

Python 2 , 208 184 183 176 Bytes

  • 24 Byte gespart, indem angegeben wird -float("inf"), dass die markierte Linie außerhalb der Matrix liegt, anstatt die negative Summe aller Matrixelemente zu berechnen.
  • Ein Byte wurde gespeichert, indem definiert wurde R,L=range,len, dass eingebaute Funktionen gekürzt werden sollen und y in R(L(A))...R(L(A[y]))anstelle von y,Y in e(A)...x,_ in e(Y).
  • Gespeichert sieben Bytes von Golf float("inf")zu 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

Probieren Sie es online!

Erläuterung

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
Jonathan Frech
quelle
1

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

Probieren Sie es online!

Eine rekursive Lösung. Für jedes Element (i, j) der Matrix wird das Maximum zwischen der Summe entlang der Zeile, der Summe entlang der Spalte, der Summe entlang einer der Diagonalen und dem Ergebnis der auf (i + 1, j) und angewendeten Funktion zurückgegeben (i, j + 1). Die Ergebnisse für die Testfälle werden im TIO angezeigt.

NofP
quelle
Ich hoffe, ich habe es verpasst, aber R scheint eine Basisfunktion zu fehlen, um die Spur einer quadratischen Matrix zu berechnen.
NofP
Habe nicht herausgefunden, ob es dir Bytes ersparen würde, aber du kannst sum (diag (m)) für den Trace verwenden
user2390246 29.10.17
0

JavaScript 170 Bytes

Wip auf dem Golf-Teil fügte 4 weitere Zeichen hinzu, weil ich keinen Fall schaffte, in dem das Maximum negativ und N größer als 1 ist

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
quelle
@HermanLauenstein Ich entferne die Leerzeichen, fügte aber mehr Coverage hinzu, was insgesamt mehr Zeichen hinzufügte, aber danke :)
DanielIndie
164 Bytes durch Entfernen unnötiger Zeilenumbrüche ( G=wird nicht gezählt)
Herman L
Warum hast du a||M,b||M,c||M,d||Mstatt benutzt a,b,c,d?
Herman L
@HermanLauenstein Math.max (NaN / undefined, 6) = NaN
DanielIndie
0

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)

Probieren Sie es online!

TFeld
quelle
Mögliche 219 Bytes .
Jonathan Frech
Mögliche 218 Bytes .
Jonathan Frech