How to generate optimal solution and order the rest

Question

This is a decimal maze, you start with 100 points and you must choose the path that gives you the highest score. Rule: You should not go twice for the same point and the same segment.

My question: Is it possible to make Mathematica go through the figure and give me correct answers ordered from highest to lowest?

So that something like this

and this and so on

Answer 1

First, let's define the edges of this graph:

start = 100;
edgedefinition = {{edge[start, a], mul[0.9]},
    {edge[start, b], sub[0.009]},
    {edge[start, c], div[0.6]},
    {edge[start, d], add[0.7]},
    {edge[a, b], div[0.09]},
    {edge[b, c], add[1.9]},
    {edge[c, d], mul[1.2]},
    {edge[a, e], div[2.01]},
    {edge[b, e], mul[1.9]},
    {edge[c, e], div[0.4]},
    {edge[e, f], sub[12]},
    {edge[c, f], mul[0.99]},
    {edge[d, f], add[2.1]},
    {edge[a, g], mul[1.89]},
    {edge[e, g], mul[0.5]},
    {edge[g, h], sub[-1.7]},
    {edge[e, h], mul[1.99]},
    {edge[f, h], div[1.4]},
    {edge[h, i], div[0.87]},
    {edge[f, i], sub[0.8]},
    {edge[i, j], mul[1.09]},
    {edge[f, j], div[0.8]},
    {edge[d, j], div[0.5]},
    {edge[g, meta], div[1.2]},
    {edge[h, meta], mul[0.97]},
    {edge[i, meta], mul[1.01]},
    {edge[j, meta], div[0.7]}};
edges = Sort[UndirectedEdge @@ #[[1]]] & /@ edgedefinition;

This should be all of them, but there's every possibility that I missed one. The vertices are labelled alphabetically from the upper left to the lower right, aside from the top one (100) and the bottom one (meta).

Second, let's define some helper functions which will be used later:

toEdges[l_] := Inner[UndirectedEdge, l[[1 ;; -2]], l[[2 ;; -1]], List];
getOperation[e_] := 
    edgedefinition[[Position[edges, Sort[e]][[1, 1]], 2]];
constructPath[l_] := Prepend[getOperation /@ toEdges[l], l[[1]]];

toEdges transfers a list of vertices to a list of edges between them, getOperation is used to find the operation associated with a given edge (e.g. so that we can turn 100 <-> a into mul[0.9]), and constructPath turns a series of vertices into the path's starting point and the list of operations it under goes (e.g. constructPath[{100, d, j, meta}] becomes {100, add[0.7], div[0.5], div[0.7]}).

Thus, constructPath turns the vertices into the path of operations that this undergoes. I have taken care to ensure that the operations above are listed consistently as add, sub, mul, or div according to the figure in your question. constructPath gives us a useful format to describe what's going on, but we need one more function to evaluate it to a usable number for sorting:

evaluatePath[{x_}] := x;
evaluatePath[{x_, add[y_], z___}] := evaluatePath[{x + y, z}];
evaluatePath[{x_, sub[y_], z___}] := evaluatePath[{x - y, z}];
evaluatePath[{x_, mul[y_], z___}] := evaluatePath[{x y, z}];
evaluatePath[{x_, div[y_], z___}] := evaluatePath[{x/y, z}];

This is probably not the fastest way to implement this function, but it is one of the most readable and it's sufficiently fast for this problem. In short, given a list containing a number (x_), an operation (f[y_]), and possibly extra (z_), turn it into a shorter list {f[x,y], z} and evaluate again. If the list contains only one element, return that element instead.

Now, let's find every possible path from 100 to meta:

allpaths = FindPath[Graph[edges], start, meta, 15, 100000];

And confirm how many such paths exist:

Length[allpaths]

1641

You can show to yourself that no more paths exist by noting that there aren't enough vertices to have paths of length 15 or longer. FindPath does not revisit vertices, so there shouldn't be any issues with that. Similarly, since it does not revisit vertices, it is guaranteed to never revisit any edge.

Then evaluate all of these paths while maintaining a copy of the original path:

unorderedresults = 
  Table[{p, evaluatePath[constructPath[p]]}, {p, allpaths}];

And then sort them:

orderedresults = SortBy[unorderedresults, #[[2]] &]

This is the sorting from lowest to highest, you can use -#[[2]] & or Reverse to find the other ordering. Somewhat unsurprisingly, the lowest-scoring path starts with the $\times 0.9$ edge and the highest-scoring path starts with the $\div 0.6$ edge.