2 ms·
I spent some time trying to formulate this as an intersection of two regular expressions (the language being composed of sequences of u and d -- given a sequenc
by kmill 10y ago
I spent some time trying to formulate this as an intersection of two regular expressions (the language being composed of sequences of u and d -- given a sequence which goes to the top, you can figure out at least one path which gets you there, and it doesn't matter which you choose)... though it seems much harder to deal with than just saying "the graph is connected because it has exactly two vertices of odd degree."
- Jtsummers 10y agoInstead of a sequence of u and d, try modeling it as: Let's go with their ultimate "alphabet", all the pairs based on altitude. (A,Z), ... (M,M). Note all valid transitions. In fact, you have the exact same graph as they do since every transition is reversible. (A,Z) is the starting state, (M,M) is the final state. What you now want is the shortest matching string: AZ.CX.DY.EW.DU.MM. There ought to be only one in this case. But there are actually 3 possible machines that can be constructed and need to be analyzed if you want to go with this method. C < W, C = W, C > W. The case of C=W is trivial, no intermediate points are introduced. C < W is the case given above and in the paper. C > W is the same as C < W under a trivially constructed mapping so it's already solved as well, so ultimately only 2 cases need be considered given symmetry. I think the problem of marking it as a sequence of u and d, you'd need a metric. Some notion of how high or low each peak and valley actually are. Now, this could be discretized based on relative altitudes. Lowest is 0, next is 1, next is 2, etc. So you can ignore precision. Still greatly complicates the matter.