Je me tiens au point (0,0)sur une carte Hx Woù l'altitude est représentée par des chiffres, par exemple:

1132
2221
1230    # H = 3, W = 4

Je voudrais faire l'expérience des vues de chaque sommet, qui dans ce cas sont les zones d'altitude 3. Cependant, grimper des collines n'est pas une tâche facile et je manque également de temps.

Défi

Le défi est de trouver le chemin le plus rapide pour visiter tous les sommets et revenir.

Le programme le plus court gagne.

Contribution

• H, W - hauteur et largeur de la carte (entiers) (facultatif, peut être une liste / tuple ou deux entrées entières distinctes)
• La carte, donnée sous forme d' Hensembles de Wchiffres ( 0- 9), dans n'importe quel format pratique (liste 2D, chaîne séparée par des retours à la ligne, etc.)

Sortie

• Temps le plus court pour visiter chaque sommet et revenir à votre point de départ (entier)

Conditions

• L'altitude d'une zone donnée est représentée par un chiffre de 0à 9.
• Le "pic" est défini par la zone avec l'altitude la plus élevée.
• Le chemin doit à la fois commencer et se terminer dans la zone supérieure gauche (0,0) .
• Vous ne pouvez vous déplacer que vers des zones adjacentes à votre zone actuelle et vous ne pouvez pas vous déplacer en diagonale.
  • Il faut 3 minutes pour passer d'une zone à l'autre s'il n'y a pas de changement d'altitude.
  • Il faut 11 minutes pour monter; c'est-à-dire se déplacer d'une zone à une autre zone qui est exactement 1plus haute.
  • Il faut 2 minutes pour descendre; c'est-à-dire se déplacer d'une zone à une autre zone qui est exactement 1inférieure à l'unité.
  • Vous ne pouvez pas vous déplacer vers des zones plus 1hautes ou plus basses que vous. (Vous ne pouvez pas passer d'une zone d'altitude 1à une zone adjacente d'altitude, par exemple 3)
• Un chemin vers tous les sommets est garanti
• Le nombre maximum de pics est 15.

Échantillons

Contribution

4 5
32445
33434
21153
12343

Sortie

96

Explication

Vous commencez en haut à gauche 3. Vous devez visiter les deux 5s qui se trouvent à (0,4)et (3,3)revenir à 3at (0,0)dans les plus brefs délais.

3  2  4->4->5
V     ^
3->3->4  3  4

2  1  1  5  3

1  2  3  4  3    # 3 + 3 + 11 + 3 + 3 + 11 = 34 minutes to visit 1st peak


3  2  4  4  5
            V
3  3  4  3  4
            V
2  1  1  5  3
         ^  V
1  2  3  4<-3    # 2 + 2 + 3 + 11 + 11 = 29 minutes to visit 2nd


3  2  4  4  5
^            
3  3  4  3  4
^            
2  1  1  5  3
^        V   
1<-2<-3<-4  3    # 2 + 2 + 2 + 2 + 11 + 11 + 3 = 33 minutes to come back

# 34 + 29 + 33 = 96 minutes total is the answer

Contribution

2 7
6787778
5777679

Sortie

75

Mathematica 745 681 octets

L'idée de base est de faire un graphique pondéré des mouvements possibles. Les poids sont le temps qu'il faut pour passer d'un endroit à l'autre. Le chemin avec le moins de poids sera le plus rapide.

Les chiffres d'entrée sont placés dans un tableau rectangulaire r par c (lignes par colonnes) puis trois représentations distinctes entrent en jeu: (1) un graphique de grille r par c, où chaque sommet correspond à une cellule du tableau, (2) (r c) par (r c) une matrice d'adjacence pondérée qui contient des poids correspondant au temps qu'il faut (2, 3 ou 11 minutes) pour se déplacer d'un endroit (dans le graphique de la grille) à un autre, et (3) une direction , graphe d'adjacence pondéré construit à partir de la matrice.

Le graphique en grille permet de déterminer quelles cellules (c'est-à-dire quels sommets) sont potentiellement accessibles à partir de chaque sommet - "éventuellement accessibles" car une cellule voisine doit non seulement être à droite, à gauche, au-dessus ou au-dessous d'une cellule donnée. Sa valeur doit également être à moins d'une unité de distance du voisin (par exemple, un 3 ne se connecte pas à un 5 voisin ou à un 1). Si le sommet an'est pas connecté au sommet, bles cellules de la matrice d'adjacence {a, b} et {b, a} auront la valeur ∞. Par conséquent, le graphe d'adjacence pondéré n'aura pas de bord de a à b, ni de b à a.

Le graphe d'adjacence pondéré sert à déterminer la distance minimale ( GraphDistance) et l'itinéraire le plus court entre tous les sommets. Le chemin optimal doit commencer par 1, toucher chacun des pics et revenir à 1. Dans ce cas, le «parcours le plus court» n'est pas nécessairement celui avec le moins de mouvements. C'est celui avec le temps global le plus court, mesuré en poids de bord.

Golfé

o=Sequence;v[a_<->b_,z_]:=(m_~u~q_:={Quotient[m-1,q[[2]]]+1,1+Mod[m-1, q[[2]]]};j=z[[o@@u[a,i=Dimensions@z]]];k=z[[o@@u[b,i]]];Which[j==k,{{a,b}->3,{b,a}->3},j==k-1,{{a,b}->11,{b,a}->2},j==k+1,{{a,b}->2,{b,a}->11},2<4,{{a,b}->∞, {b, a}->∞}]);w@e_:=Module[{d,x,l,y},x=Map[ToExpression,Characters/@Drop[StringSplit@e,2],{2}];d_~l~c_:=d[[2]](c[[1]]-1)+c[[2]];g_~y~p_:=(Min[Plus@@(GraphDistance[g,#,#2]&@@@#)&/@(Partition[#,2,1]&/@({1,o@@#,1}&/@Permutations@p))]);y[WeightedAdjacencyGraph[ReplacePart[ConstantArray[∞,{t=Times@@(d=Dimensions@x),t}],Flatten[#~v~x &/@Union@Flatten[EdgeList[GridGraph@Reverse@d,#<->_]&/@Range@(Times@@d),1],1]]], l[Dimensions@x, #] & /@ Position[x, Max@x]]

Forme plus longue et plus lisible

(*determines a weight (number of minutes) to go from vertex a to b and from b to a*)
weight[a_ <-> b_, dat_]:= 
  Module[{cellA,cellB,dim,valA,valB,vertexToCell},

  (*Convert graph vertex index to cell location*)
  vertexToCell[m_,dimen_]:={Quotient[m-1,dim[[2]]]+1,1+Mod[m-1,dimen[[2]]]};
     dim=Dimensions[dat];
     cellA = vertexToCell[a,dim];
     cellB = vertexToCell[b,dim];
     valA=dat[[Sequence@@cellA]];
     valB=dat[[Sequence@@cellB]];
     Which[
       valA==valB,{{a,b}-> 3,{b,a}-> 3},
       valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
       valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
       2<4,{{a,b}->∞,{b,a}->∞}]];

(* weights[] determines the edge weights (times to get from one position to the next), makes a graph and infers the shortest distance 
from vertex 1 to each peak and back.  It tries out all permutations of peaks and 
selects the shortest one. Finally, it returns the length (in minutes) of the shortest trip. *)

weights[str_]:=
  Module[{d,dat,neighbors,cellToVertex,peaks,z,gd},
  dat=Map[ToExpression,Characters/@Drop[StringSplit[str],2],{2}];
  cellToVertex[dim_,cell_]:=dim[[2]] (cell[[1]]-1)+cell[[2]];
  peaks[dat_]:= cellToVertex[Dimensions[dat],#]&/@Position[dat,peak =Max[dat]];

     (* to which cells should each cell be compared? neighbors[] is a function defined within weights[]. It returns a graph, g, from which graph distances will be derived in the function gd[] *)
  neighbors[dim_]:=
  Union@Flatten[EdgeList[GridGraph[Reverse@dim],#<->_]&/@Range@(Times@@dim),1];
    d=Dimensions[dat];
    m=ReplacePart[ConstantArray[∞,{t=Times@@d,t}], 
     (*substitutions=*)
    Flatten[weight[#,dat]&/@neighbors[d],1]];
    g=WeightedAdjacencyGraph[m,VertexLabels->"Name",ImageSize->Full,GraphLayout->"SpringEmbedding"];

    (* finds shortest path.  gd[] is also defined within weights[] *)
  gd[g3_,ps_]:=
    Module[{lists,pairs},
    pairs=Partition[#,2,1]&/@({1,Sequence@@#,1}&/@Permutations@ps);
    Min[Plus@@(GraphDistance[g3,#,#2]&@@@#)&/@pairs]]; 

  gd[g,peaks[dat]]]

Les tests

weights["4 5
 32445
 33434
 21153
 12343"]

96.

weights@"2 7
 6787778
 5777679"

75.

weights@"3 4
 1132
 2221
 1230"

51.

Explication

Pensez aux lignes 2 à 5 de l'entrée suivante

"4 5
 32445
 33434
 21153
 12343"

comme représentant un tableau à 4 lignes et 5 colonnes:

où chaque sommet correspond à un chiffre du tableau d'entrée: 3 est au sommet 1, 2 est au sommet 2, 4 est au sommet 3, 4 autres au sommet 4, 5 au sommet 5, etc. Le graphique de la grille n'est qu'une ébauche approximation du graphique que nous visons. Il n'est pas dirigé. De plus, certains bords ne seront pas disponibles. (N'oubliez pas: nous ne pouvons pas passer d'une position à une autre qui se trouve à plus d'une unité de hauteur au-dessus ou en dessous de la position actuelle.) Mais le graphique de la grille nous permet de trouver facilement les sommets qui sont à côté de tout sommet choisi. Cela réduit le nombre d'arêtes que nous devons considérer, dans le premier exemple (une grille de 4 x 5), de 400 (20 * 20) à 62 (31 * 2 est le nombre d'arêtes dans le graphique de la grille). Dans le même exemple, seulement 48 des bords sont opérationnels; 14 ne le sont pas.

La matrice d'adjacence 20 x 20 pondérée suivante représente la distance entre toutes les paires de sommets du graphique de grille.

Le code clé qui décide du numéro à attribuer est ci-dessous.

Which[
      valA==valB,{{a,b}-> 3,{b,a}-> 3},
      valA==valB-1,{{a,b}-> 11,{b,a}-> 2},
      valA==valB+1,{{a,b}-> 2,{b,a}-> 11},
      2<4,{{a,b}->∞,{b,a}->∞}]

La cellule {1,2} - en une seule indexation - contient la valeur 2 car le déplacement du sommet 1 au sommet 2 est en descente. La cellule {2,1} contient 11 car le passage du sommet 2 au sommet 1 est en montée. Les 3 dans les cellules {1,6} et {6,1} signifient que le mouvement n'est ni vers le haut ni vers le bas. La cellule {1,1} contient ∞ car elle n'est pas connectée à elle-même.

Le graphique suivant montre la structure sous-jacente à l'entrée ci-dessus. Les flèches colorées indiquent le chemin optimal du sommet 1 aux pics (à 5 et 14) et reviennent à 1. Les flèches bleues correspondent à des mouvements au même niveau (3 min); les flèches rouges indiquent la montée (11 min.) et les flèches vertes indiquent la descente (2 min).

Le chemin du sommet 1 (cellule {1,1} aux deux pics et retour au sommet 1:

3 + 3 + 11 + 3 + 3 + 11 + 2 + 2 + 3 + 11 + 11 + 2 + 2 + 2 + 2 + 11 + 11 + 3

96

Pyth, 92 octets

[email protected],bhS,@Gb+@G,hbH@G,HebG[FQ.dm,(Fb?|tsaMCb>[email protected]@[3hT2)J*QQC.<B+]hSQd1.p.M@Q

Le format d'entrée est un dict mappant les coordonnées aux hauteurs: {(0, 0): 3, (0, 1): 2, (0, 2): 4, …} . Cela trouve les chemins les plus rapides entre toutes les paires de points en utilisant l' algorithme de Floyd-Warshall , puis minimise la durée totale du cycle souhaité sur toutes les permutations de pics.

Essayez-le en ligne