22
\$\begingroup\$

I am standing at point (0,0) in a H x W map where the altitude is represented by digits, for example:

1132
2221
1230    # H = 3, W = 4

I'd like to experience the views from every peak, which in this case are the areas with altitude 3. However, climbing up hills is not an easy task, and I am also running out of time.

Challenge

The challenge is to find the quickest path to visit all the peaks and come back.

Shortest program wins.

Input

  • H, W - height and width of the map (Integers) (optional, may be a list/tuple or two separate integer inputs)
  • The map, given as H sets of W digits (0-9), in any convenient format (2D list, string separated by newlines, etc.)

Output

  • Shortest time taken to visit every peak and come back to your starting point (Integer)

Conditions

  • The altitude of a given area is represented by a digit from 0 to 9.
  • The "peak" is defined by the area with the highest altitude.
  • The path must both begin and end at the top-left (0,0) area.
  • You can only move to areas adjacent to your current area, and you may not move diagonally.
    • It takes 3 minutes to move from one area to another if there is no change in altitude.
    • It takes 11 minutes to climb up; that is, moving from one area to another area that is exactly 1 unit higher.
    • It takes 2 minutes to climb down; that is, moving from one area to another area that is exactly 1 unit lower.
    • You cannot move to areas that are more than 1 unit higher or lower than where you are. (You cannot go from an area with altitude 1 to an adjacent area with altitude, say, 3)
  • A path to all the peaks is guaranteed
  • Maximum number of peaks is 15.

Samples

Input

4 5
32445
33434
21153
12343

Output

96

Explanation

You start at the top-left 3. You have to visit the two 5s that are located at (0,4) and (3,3) and come back to the 3 at (0,0) in the shortest time possible.

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

Input

2 7
6787778
5777679

Output

75
\$\endgroup\$
  • 9
    \$\begingroup\$ Welcome to PPCG, and great first question! I highly recommend changing this to a code golf question, since there has to be an objective winning criterion to score answers. \$\endgroup\$ – Deusovi Jan 27 '16 at 10:53
  • 4
    \$\begingroup\$ Thank you for the recommendation, I read the rules in the help center and edited the question \$\endgroup\$ – cozyconemotel Jan 27 '16 at 23:42
  • \$\begingroup\$ Perhaps your challenge would receive more hits if the title were improved. "Mountain climbing challenge" perhaps. \$\endgroup\$ – DavidC Jul 11 '16 at 4:44
  • 1
    \$\begingroup\$ cozyconemotel, I suggested a shorter, perhaps more attractive title for your challenge. Please feel free to change it back to the original if you wish. (There have been 245 viewings since your submission.) \$\endgroup\$ – DavidC Jul 11 '16 at 12:50
  • \$\begingroup\$ @DavidC I totally agree. Thank you for the edit. \$\endgroup\$ – cozyconemotel Jul 11 '16 at 16:08
5
\$\begingroup\$

Mathematica 745 681 bytes

The basic idea is to make a weighted graph of possible moves. Weights are the time it takes to move from one place to the next. The path with the least weight will be the quickest.

The input digits are placed in an r by c (rows by columns) rectangular array and then three distinct representations come into play: (1) an r by c grid graph, where each vertex corresponds to a cell in the array, (2) (rc) by (rc) weighted adjacency matrix that holds weights corresponding to the time it takes (2, 3, or 11 minutes) to move from one location (in the grid graph) to another, and (3) a directed, weighted adjacency graph constructed from the matrix.

The grid graph helps determine which cells (i.e. which vertices) are possibly reachable from each vertex--"possibly reachable" because a neighboring cell must not only be right, left, above or below a given cell. It's value must also be within 1 unit of distance from the neighbor (e.g., a 3 does not connect to a neighboring 5 or a 1). If vertex a is not connected to vertex b then the adjacency matrix cells {a,b} and {b,a} will have a value of ∞. Accordingly, the weighted adjacency graph will not have an edge from a to b, nor from b to a.

The weighted adjacency graph serves to determine the minimum distance (GraphDistance) and shortest route between any vertices. The optimal path must begin with 1, touch each of the peaks, and return to 1. In this case, "shortest route" is not necessarily the one with the fewest moves. It is the one with the shortest overall time, measured in edge weights.


Golfed

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

Longer, more readable form

(*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]]]

Tests

weights["4 5
 32445
 33434
 21153
 12343"]

96.


weights@"2 7
 6787778
 5777679"

75.


weights@"3 4
 1132
 2221
 1230"

51.


Explanation

Think of lines 2-5 of the following input

"4 5
 32445
 33434
 21153
 12343"

as representing an array with 4 rows and 5 columns:

gridgraph

where each vertex corresponds to a digit from the input array: 3 is at vertex 1, 2 is at vertex 2, 4 is at vertex 3, another 4 at vertex 4, 5 at vertex 5, etc. The grid graph is only a rough approximation of the graph we are aiming for. It is undirected. Furthermore, some of the edges will be unavailable. (Remember: we cannot move from a position to another that is more than 1 height unit above or below the current one.) But the grid graph let's us easily find those vertices that are next to any chosen vertex. This reduces the number of edges we need to consider, in the first example (a 4 by 5 grid), from 400 (20 * 20) to 62 (31 *2 is the number of edges in the grid graph). In the same example, only 48 of the edges are operative; 14 are not.

The following 20 by 20 weighted adjacency matrix represents the distance between all pairs of vertices from the grid graph.

The key code which decides on which number to assign is below.

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

Cell {1,2}--in one-indexing-- contains the value 2 because the move from vertex 1 to vertex 2 is downhill. Cell {2,1} contains 11 because the move from vertex 2 to vertex 1 is uphill. The 3's in cells {1,6} and {6,1} signify that the movement is neither up nor down. Cell {1,1} contains ∞ because it is not connected to itself.

weights

The following graph shows the structure underlying the above input. The colored arrows show the optimal path from vertex 1 to the peaks (at 5 and 14) and back to 1. Blue arrows correspond to moves at the same level (3 min); red arrows mean ascent (11 min.) and green arrows indicate descent (2 min).

graph2

The path from vertex 1 (cell {1,1} to the two peaks and back to vertex 1:

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

96

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

Pyth, 92 bytes

hSms@Lu.dm,bhS,@Gb+@G,hbH@G,HebG[FQ.dm,(Fb?|tsaMCb>.aJ-F@LQb1.n4@[3hT2)J*QQC.<B+]hSQd1.p.M@Q

The input format is a dict mapping coordinates to heights: {(0, 0): 3, (0, 1): 2, (0, 2): 4, …}. This finds the fastest paths between all pairs of points using the Floyd–Warshall algorithm, then minimizes the total time of the desired cycle over all permutations of peaks.

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.