Chemin optimal à travers une matrice

19

Étant donné une matrice composée d'entiers positifs, affichez le chemin avec la somme la plus faible lorsque vous passez de l'élément supérieur gauche au coin inférieur droit. Vous pouvez vous déplacer verticalement, horizontalement et en diagonale. Notez qu'il est possible de se déplacer vers le haut / bas, droite / gauche et en diagonale de tous les côtés.

Exemple:

 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*

Le chemin donnant la somme la plus faible est marqué d'astérisques et donne la somme suivante: 1 + 4 + 1 + 1 + 1 + 5 + 1 + 9 = 23 .

Cas de test:

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)

Il s'agit de donc le code le plus court dans chaque langue l'emporte.

Stewie Griffin
la source
Très similaire , bien qu'il ne permette pas de mouvement diagonal.
Mego
7
@WheatWizard Je ne suis pas d'accord. Hormis les différences principalement superficielles que ce défi permet pour le mouvement diagonal et toutes les positions sont accessibles, l'autre défi nécessite le retour du chemin lui-même plutôt que juste le coût du chemin. À moins que vous n'utilisiez des fonctions intégrées qui renvoient les deux, le code n'est pas interchangeable.
bécher
@beaker Je ne vois pas vraiment la différence. Il faut trouver le chemin pour connaître sa longueur. La différence ici est une différence de production plutôt faible à mon avis et ce défi n'offre rien de nouveau ou d'intéressant qui n'est pas déjà couvert par ce défi.
Wheat Wizard
1
@WheatWizard Ma solution ici ne trouve pas le chemin. Il pourrait trouver le chemin, mais pas sans un tableau et une logique de prédécesseur séparés pour éviter de faire d'un nœud son propre prédécesseur. Sans parler de retrouver le chemin à la fin.
bécher
@beaker La modification est plutôt triviale à mon avis. Indépendamment de la question des dupes n'est pas de savoir si chaque entrée valide unique sur un défi peut être transférée avec un effort minimal, il s'agit du cas général. Non seulement je pense que la plupart des efforts peuvent être portés, mais je ne pense pas que ce défi offre quelque chose de nouveau ou d'intéressant de l'autre.
Wheat Wizard

Réponses:

8

JavaScript, 442 412 408 358 octets

Ceci est ma première soumission PPCG. Des commentaires seraient appréciés.

(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}

Cela prend un tableau multidimensionnel en entrée.

Explication

Fondamentalement, parcourez toutes les cellules à plusieurs reprises en ajustant le coût connu le plus bas pour atteindre chacun des voisins. Finalement, la grille atteindra un état où le coût total pour atteindre le coin inférieur droit est le coût le plus bas pour y arriver.

Démo

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: Un merci spécial à @ETHproductions pour m'avoir aidé à raser des dizaines d'octets savoureux.

Merci à @Stewie Griffin pour vos conseils qui ont fait tomber 50 octets.

Benjamin Cuningham
la source
3
Bienvenue chez PPCG! Il y a quelques espaces supplémentaires que vous pouvez supprimer vers la fin (je compte 5 au total), et vous n'avez besoin d'aucun point-virgule directement avant un }qui devrait économiser quelques octets. Vous n'avez pas non plus besoin de déclarer vos variables; Je pense que la suppression des vars devrait vous faire économiser 24 octets de plus au total.
ETHproductions
2
Bienvenue chez PPCG =) Je suis heureux que vous ayez choisi l'un de mes défis comme point de départ. Mon seul commentaire: j'adore les explications. Il est cependant facultatif, vous n'avez donc pas à l'ajouter à moins que vous ne le souhaitiez. :)
Stewie Griffin
Je pense que peut-être le stockage en m[v][t]tant que variable: t=x+X;v=y+Y;k=m[v][t]sera encore plus court ...?
Stewie Griffin
7

Python 3 + numpy + scipy , 239 222 186 octets

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]

Essayez-le en ligne!

notjagan
la source
6

Octave + Image paquet de traitement, 175 162 157 151 142 139 octets

14 octets enregistrés grâce à @Luis Mendo et 1 octet grâce à @notjagan

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)

Utilise le package de traitement d'image, car pourquoi pas? N'est-ce pas ainsi que tout le monde résout les problèmes graphiques?

Essayez-le en ligne!

A explosé

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

Explication

Étant donné un éventail de poids:

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

Initialisez un tableau de coûts pour que le coût pour atteindre chaque élément soit Infinity, sauf le point de départ (l'élément supérieur gauche) dont le coût est égal à son poids.

  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

Il s'agit de l'itération 0. Pour chaque itération suivante, le coût pour atteindre une cellule est fixé au minimum:

  • le coût actuel pour atteindre cet élément, et
  • le coût actuel pour atteindre les voisins de l'élément + le poids de l'élément

Après la première itération, le coût du chemin vers l'élément (2,2) (en utilisant une indexation basée sur 1) sera

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

Le tableau de coût complet après la première itération serait:

  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

Après l'itération k, chaque élément sera le coût le plus bas pour atteindre cet élément dès le début en prenant la plupart des kétapes. Par exemple, l'élément à (3,3) peut être atteint en 2 étapes (itérations) pour un coût de 22:

  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

Mais à la 4ème itération, on trouve un chemin de 4 étapes avec un coût de 20:

 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

Puisqu'aucun chemin à travers la matrice mxn ne peut être plus long que le nombre d'éléments dans la matrice (comme une limite supérieure très lâche), après les m*nitérations, chaque élément contiendra le coût du chemin le plus court pour atteindre cet élément depuis le début.

gobelet
la source
-1 octet en supprimant l'espace entre whileet ~.
notjagan
@notjagan Je suis passé de whileà foret j'ai toujours pu utiliser votre astuce. Merci!
bécher
5

JavaScript, 197 octets

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())

Enjoliver:

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
la source
4

Mathematica 279 octets

L'idée de base est de créer un graphique avec des sommets correspondant aux entrées de la matrice et des arêtes dirigées entre deux sommets séparés par un ChessboardDistancesupérieur à zéro mais inférieur ou égal à 1. Par ailleurs, cela se trouve être connu sous le nom de graphe King , car il correspond à les mouvements valides d'un roi sur un échiquier.

FindShortestPathest ensuite utilisé pour obtenir le chemin minimal. Cela fonctionne EdgeWeight, non VertexWeight, donc il y a du code supplémentaire pour définir l' EdgeWeightentrée de la matrice correspondant à la destination de chaque bord dirigé.

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

Notez que le caractère est le symbole de transposition. Il sera collé dans Mathematica tel quel.

Usage:

%@{{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}}

Production:

67

Si vous définissez g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]et p=FindShortestPath[...ensuite le graphique suivant affichera visuellement la solution ( en haut de la matrice correspond au bas du graphique):

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

entrez la description de l'image ici

Kelly Lowder
la source
3

Haskell, 228 octets

Les positions sont des listes de deux éléments, car ceux-ci sont faciles à générer avec sequenceet tout aussi faciles à mettre en correspondance que les 2-tuples.

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

Commencez par -1,-1et comptez le coût de chaque champ de destination des étapes.

Deux premières lignes alternatives: commencer à 0,0, compter les champs de départ, terminer aux coordonnées égales aux dimensions de la matrice (donc en bas à droite de l'objectif, qui doit être ajouté à la liste des destinations légales) - même longueur exacte mais plus lente:

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]

L'utilisation d'un infixe pour mapne permet pas d'économiser des octets ici, mais je le remplace dès qu'il n'en coûte pas un, car il ne peut s'améliorer qu'avec plus d'utilisations, et parfois avec d'autres restructurations qui rasent une autre paire de parenthèses.

Points à améliorer: Redundant filters. Les fusionner / les aligner avec filter(flip elem$(s$(\x->[0..x])#m)\\p)avec import Data.Listpour des \\coûts de 3 octets.

Aussi, dommage, (fromEnumTo 0)c'est 2 octets de plus que (\x->[0..x]).

sum$concat cest le coût de tous les champs résumé et donc une limite supérieure exprimable de manière concise sur le coût du chemin qui est donné à minimumpour éviter une liste vide (mon vérificateur de type a déjà déterminé le tout pour travailler sur Integers, donc pas de codage en dur le maximum , hehe). Peu importe comment je restreins les étapes basées sur la précédente (ce qui accélérerait beaucoup l'algorithme, mais coûterait également des octets), je ne peux pas éviter les impasses qui rendent cette solution de repli nécessaire.

  • Une idée de filtre était ((not.e n).zipWith(-)(head r))avec l'extraction n=s[[-1..1],[-1..1]], ce qui nécessite d'ajouter ,[-1,-1]au chemin initial. L'algorithme évite alors d'aller là où il aurait déjà pu aller à l'étape précédente, ce qui fait que marcher sur un champ de bord orthogonalement à ce bord est une impasse.

  • Un autre était ((>=0).sum.z(*)d)d'extrairez=zipWith , qui introduit un nouvel argument dà la fonction récursive qui est donnée comme (z(-)p q)dans la récursivité et [1,1]dans le cas initial. L'algorithme évite les étapes successives avec un produit scalaire négatif ( détant l'étape précédente), ce qui signifie pas de tours brusques de 45 °. Cela rétrécit encore considérablement les choix et évite l'impasse triviale précédente, mais il y a encore des chemins qui finissent enfermés dans des champs déjà visités (et peut-être une `` évasion '' qui serait cependant un virage serré).

Leif Willerts
la source
3

Python 2, 356 320 octets

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

Essayez-le ici!

-36 octets grâce à notjagan !

Reçoit une liste de listes en entrée et affiche le coût le plus bas lors de la navigation dans la matrice du coin supérieur gauche au coin inférieur droit.

Explication

Trouvez tous les itinéraires possibles du coin supérieur gauche au coin inférieur droit de la matrice, en créant une liste de coordonnées x, y pour chaque itinéraire. Les itinéraires ne peuvent pas revenir en arrière et doivent se terminer à(len(s)-1,len(s[0])-1) .

Additionnez les entiers sur chaque chemin de coordonnées et retournez le coût minimum.

Le printpeut être facilement modifié pour afficher la liste des coordonnées de l'itinéraire le plus court.

Solvation
la source
-36 octets avec quelques modifications diverses.
notjagan
@notjagan Grands changements, en particulier l'utilisation de orconditionnels. Je vous remercie!
Solvation
1

APL (Dyalog Classic) , 33 octets

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

Essayez-le en ligne!

{ } fonction avec argument

+\+⍀⍵ prendre des sommes partielles par ligne et par colonne pour établir une limite supérieure pessimiste sur les distances de chemin

( )⍣≡ répéter jusqu'à convergence:

  • (⍉3⌊/⊣/,⊢,⊢/)⍣2minimum de distances avec les voisins, c.-à-d. faire deux fois ( ( )⍣2): ajouter la colonne la plus à gauche ( ⊣/,) à self ( ) et ajouter les colonnes à l'extrême droite ( ,⊢/), trouver les minima dans les triplets horizontaux ( 3⌊/) et transposer ( )

  • ⍵+ ajouter la valeur de chaque nœud à son minimum de distances aux voisins

  • ⊢⌊ essayez de battre les meilleures distances actuelles

⊃⌽, enfin, retournez la cellule en bas à droite

ngn
la source