Optimaler Weg durch eine Matrix

19

Geben Sie bei einer Matrix aus positiven Ganzzahlen den Pfad mit der niedrigsten Summe aus, wenn Sie vom linken oberen Element zum rechten unteren Element wechseln. Sie können sich vertikal, horizontal und diagonal bewegen. Beachten Sie, dass es möglich ist, sich nach oben / unten, rechts / links und diagonal nach allen Seiten zu bewegen.

Beispiel:

 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

Der Pfad mit der niedrigsten Summe ist mit Sternchen markiert und ergibt die folgende Summe: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Testfälle:

1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

Das ist also gewinnt der kürzeste Code in jeder Sprache.

Stewie Griffin
quelle
Sehr ähnlich , obwohl es keine diagonale Bewegung erlaubt.
Mego
7
@ WheatWizard Ich bin nicht einverstanden. Abgesehen von den größtenteils oberflächlichen Unterschieden, die diese Herausforderung für diagonale Bewegungen zulässt und bei denen alle Positionen erreichbar sind, erfordert die andere Herausforderung die Rückkehr des Pfades selbst und nicht nur die Kosten des Pfades. Sofern Sie keine integrierten Funktionen verwenden, die beide zurückgeben, ist der Code nicht austauschbar.
Becher
@beaker Ich sehe den Unterschied nicht wirklich. Sie müssen den Pfad finden, um seine Länge zu kennen. Der Unterschied hier ist meiner Meinung nach ein kleiner Unterschied in der Ausgabe, und diese Herausforderung bietet nichts Neues oder Interessantes, das nicht bereits von dieser Herausforderung abgedeckt wird.
Weizen-Assistent
1
@ WheatWizard Meine Lösung hier findet den Pfad nicht. Es konnte den Pfad finden, aber nicht ohne ein separates Vorgängerarray und eine separate Logik, um zu vermeiden, dass ein Knoten zu einem eigenen Vorgänger wird. Ganz zu schweigen von der Wiederherstellung des Pfades am Ende.
Becher
@beaker Die Modifikation ist meiner Meinung nach eher trivial. Unabhängig davon ist die Frage der Betrüger nicht, ob jeder einzelne gültige Eintrag zu einer Challenge mit minimalem Aufwand portiert werden kann, es geht um den allgemeinen Fall. Ich denke nicht nur, dass die meisten Anstrengungen hier portiert werden können, ich denke nicht, dass diese Herausforderung etwas Neues oder Interessantes vom anderen bietet.
Weizen-Assistent

Antworten:

8

JavaScript, 442 412 408 358 Bytes

Dies ist meine erste PPCG-Einreichung. Rückmeldungen sind erwünscht.

(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

Dies nimmt ein mehrdimensionales Array als Eingabe.

Erläuterung

Grundsätzlich sollten Sie alle Zellen immer wieder durchlaufen und die niedrigsten bekannten Kosten anpassen, um zu jedem der Nachbarn zu gelangen. Irgendwann erreicht das Gitter einen Zustand, in dem die Gesamtkosten für das Erreichen der unteren rechten Ecke die niedrigsten Kosten sind.

Demo

f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34); 
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);

Edit: Besonderer Dank geht an @ETHproductions, die mir geholfen haben, Dutzende leckerer Bytes zu rasieren.

Vielen Dank an @Stewie Griffin für Ihre Tipps, die 50 Bytes gekostet haben .

Benjamin Cuningham
quelle
3
Willkommen bei PPCG! Es gibt einige zusätzliche Leerzeichen, die Sie gegen Ende entfernen könnten (ich zähle insgesamt 5), und Sie brauchen keines der Semikolons direkt vor einem, }wodurch ein paar Bytes gespart werden sollten. Sie müssen Ihre Variablen auch nicht deklarieren. Ich denke, das Entfernen des vars sollte Ihnen insgesamt 24 weitere Bytes sparen.
ETHproductions
2
Willkommen bei PPCG =) Ich freue mich, dass Sie eine meiner Herausforderungen als Ausgangspunkt gewählt haben. Mein einziger Kommentar: Ich liebe Erklärungen. Es ist jedoch optional, sodass Sie es nicht hinzufügen müssen, es sei denn, Sie möchten. :)
Stewie Griffin
Ich denke, vielleicht m[v][t]als Variable speichern : t=x+X;v=y+Y;k=m[v][t]wird noch kürzer ...?
Stewie Griffin
7

Python 3 + numpy + scipy , 239 222 186 Bytes

from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

Probieren Sie es online!

notjagan
quelle
6

Octave + Bildverarbeitungspaket, 175 162 157 151 142 139 Bytes

Dank @Luis Mendo 14 Byte und dank @notjagan 1 Byte gespeichert

function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

Verwendet das Bildverarbeitungspaket, warum nicht? Lösen nicht alle so Grafikprobleme?

Probieren Sie es online!

Explodiert

function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

Erläuterung

Eine Reihe von Gewichten gegeben:

7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

Initialisieren Sie ein Kostenarray so, dass die Kosten für das Erreichen jedes Elements unendlich sind, mit Ausnahme des Startpunkts (oberes linkes Element), dessen Kosten gleich seinem Gewicht sind.

  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Dies ist Iteration 0. Für jede nachfolgende Iteration werden die Kosten zum Erreichen einer Zelle auf das Minimum von festgelegt:

  • die aktuellen Kosten, um dieses Element zu erreichen, und
  • Die aktuellen Kosten, um die Nachbarn des Elements zu erreichen, + das Gewicht des Elements

Nach der ersten Iteration betragen die Kosten für den Pfad zum Element (2,2) (unter Verwendung einer 1-basierten Indizierung)

minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

Das vollständige Kostenarray nach der ersten Iteration wäre:

  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Nach der Iteration kstellt jedes Element die niedrigsten Kosten für das Erreichen dieses Elements von Anfang an dar, wobei höchstens kSchritte unternommen werden. Zum Beispiel kann das Element bei (3,3) in 2 Schritten (Iterationen) zu einem Preis von 22 erreicht werden:

  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

Bei der 4. Iteration wird jedoch ein Pfad mit 4 Schritten mit Kosten von 20 gefunden:

 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

Da kein Pfad durch die mxn- Matrix länger sein kann als die Anzahl der Elemente in der Matrix (als sehr lockere Obergrenze), enthält m*njedes Element nach Iterationen die Kosten des kürzesten Pfades, um dieses Element von Anfang an zu erreichen.

Becherglas
quelle
-1 Byte durch Entfernen des Leerzeichens zwischen whileund ~.
Notjagan
@notjagan Ich wechselte von whilezu forund konnte trotzdem deinen Tipp verwenden. Vielen Dank!
Becher
5

JavaScript, 197 Byte

a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

Verschönern Sie:

a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)
tsh
quelle
4

Mathematica 279 Bytes

Grundidee ist einen Graph mit den Eckpunkten entsprechend Matrixeinträge und gerichtete Kanten zwischen zwei beliebigen Vertices von einer getrennt zu schaffen ChessboardDistancegrößer als Null aber kleiner als oder gleich 1. Im übrigen geschieht dies als bekannt seinen König Graph , da sie entspricht die gültigen Züge eines Königs auf einem Schachbrett.

FindShortestPathwird dann verwendet, um den minimalen Pfad zu erhalten. Funktioniert EdgeWeightnicht VertexWeight, daher gibt es einen zusätzlichen Code, um den EdgeWeightals Matrixeintrag zu definieren, der dem Ziel jeder gerichteten Kante entspricht.

Code:

(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

Beachten Sie, dass das Zeichen das Transponierungssymbol ist. Es wird unverändert in Mathematica eingefügt.

Verwendung:

%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

Ausgabe:

67

Wenn Sie g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]und p=FindShortestPath[...dann festlegen, zeigt die folgende Grafik die Lösung visuell an (der obere Rand der Matrix entspricht dem unteren Rand der Grafik):

HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

Bildbeschreibung hier eingeben

Kelly Lowder
quelle
3

Haskell, 228 Bytes

Positionen sind Listen mit zwei Elementen, da diese einfach zu generieren sequenceund genauso einfach zu kopieren sind wie 2-Tupel.

h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

Beginnen Sie mit -1,-1und zählen Sie die Kosten für jedes Schrittzielfeld.

Alternative erste beiden Zeilen: Beginnen Sie mit 0,0, zählen Sie die Abflugfelder und enden Sie an den Koordinaten, die den Matrixabmessungen entsprechen (also rechts unten vom Ziel, das zur Liste der zulässigen Ziele hinzugefügt werden muss) - exakt dieselbe Länge, aber langsamer:

j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

Das Verwenden eines Infixes für mapspart hier keine Bytes, aber ich ersetze es, sobald es keinen kostet, weil es nur mit mehr Verwendungen und manchmal auch mit anderen Umstrukturierungen besser werden kann, die ein anderes Klammerpaar abschneiden.

Zu verbessern: Redundante filters. Merging / in-Futter sie filter(flip elem$(s$(\x->[0..x])#m)\\p)mit import Data.Listfür \\Kosten 3 Bytes.

Auch zu schade, (fromEnumTo 0)ist 2 Bytes länger als (\x->[0..x]).

sum$concat cwerden die Kosten aller Felder aufsummiert und damit eine präzise ausdrückbare Obergrenze für die Pfadkosten angegeben, minimumum eine leere Liste zu vermeiden (meine Typprüfung hat bereits festgelegt, woran alles gearbeitet werden soll Integer, also kein hartes Kodieren des Maximums) hehe). Egal, wie ich Schritte einschränke, die auf den vorherigen Schritten basieren (was den Algorithmus erheblich beschleunigen würde, aber auch Byte kosten würde), ich kann die Sackgassen nicht vermeiden, die dieses Zurückfallen erforderlich machen.

  • Eine Filteridee war das ((not.e n).zipWith(-)(head r))Extrahieren n=s[[-1..1],[-1..1]], was das Hinzufügen ,[-1,-1]zum Anfangspfad erfordert . Der Algorithmus vermeidet dann, dorthin zu gehen, wo er bereits im vorherigen Schritt hätte sein können, wodurch das orthogonale Betreten eines Kantenfelds zu einer Sackgasse wird.

  • Eine andere war das ((>=0).sum.z(*)d)Extrahieren z=zipWith, das dder rekursiven Funktion, die wie (z(-)p q)in der Rekursion und [1,1]im Anfangsfall angegeben ist, ein neues Argument hinzufügt . Der Algorithmus vermeidet aufeinanderfolgende Schritte mit einem negativen Skalarprodukt ( ddas der vorherige Schritt ist), was bedeutet, dass keine scharfen 45 ° -Drehungen auftreten. Dies schränkt die Auswahlmöglichkeiten immer noch erheblich ein und vermeidet die vorherige triviale Sackgasse, aber es gibt immer noch Wege, die in bereits besuchten Feldern eingeschlossen sind (und möglicherweise eine „Flucht“, die jedoch eine scharfe Wendung darstellen würde).

Leif Willerts
quelle
3

Python 2, 356 320 Bytes

s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

Probieren Sie es hier aus!

-36 bytes dank notjagan !

Erhält eine Liste mit Listen als Eingabe und gibt die niedrigsten Kosten aus, wenn Sie in der Matrix von links oben nach rechts unten navigieren.

Erläuterung

Suchen Sie jede mögliche Route von links oben nach rechts unten in der Matrix, und erstellen Sie für jede Route eine Liste mit x- und y-Koordinaten. Die Routen können nicht zurückverfolgt werden und müssen bei enden (len(s)-1,len(s[0])-1).

Summieren Sie die Ganzzahlen auf jedem Koordinatenpfad und geben Sie die minimalen Kosten zurück.

Das printkann leicht geändert werden, um die Liste der Koordinaten für die kürzeste Route auszugeben.

Lösung
quelle
-36 Bytes mit diversen Änderungen.
Notjagan
@notjagan Tolle Änderungen, insbesondere die Verwendung orfür die Bedingungen. Vielen Dank!
Solvation
1

APL (Dyalog Classic) , 33 Byte

{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

Probieren Sie es online!

{ } Funktion mit Argument

+\+⍀⍵ Nehmen Sie Teilsummen pro Zeile und pro Spalte, um eine pessimistische Obergrenze für Pfadentfernungen festzulegen

( )⍣≡ wiederhole bis zur Konvergenz:

  • (⍉3⌊/⊣/,⊢,⊢/)⍣2Minimale Abstände zu Nachbarn, dh zweimal ( ( )⍣2): linke Spalte ( ⊣/,) vor sich selbst ( ) stellen und rechte Spalte ( ) anhängen ,⊢/, Minima in horizontalen Tripeln finden ( 3⌊/) und transponieren ( )

  • ⍵+ Addieren Sie den Wert jedes Knotens zu den Mindestentfernungen zu den Nachbarn

  • ⊢⌊ versuche die aktuell besten Distanzen zu schlagen

⊃⌽, Geben Sie zum Schluss die untere rechte Zelle zurück

ngn
quelle