3 ms·
Instead 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 vali
by Jtsummers 10y ago
Instead 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.