There is a crack, a crack in everything. That’s how the light gets in.
– Leonard Cohen
I think I’ve got it cracked! Not optimally, mind you, but I think I see enough to be able to solve any train, perhaps sub-optimally. Here’s what has happened since we were last together here:
I played a few more games. I’m probably up to having played the on line game 20 or 25 times. The early plays, I didn’t have much in the way of strategy, but in later plays I was able to think a bit more strategically, and to recognize patterns in what I was doing.
I began to formulate a theory, namely that If I could stash two blank cars in one 3-siding and one in the other, with all five numbered cars in the 5-siding, I could always solve from there.
I realized that what we have with 34251 is a “permutation” of the numbers 1-5, and I looked up permutations and learned the notion of “inversions”. In essence, an “inversion” in a permutation is the occurrence of a number to the left which is higher than a number on its right. Obviously our solution is the only permutation with zero inversions.
I saw that, given some inversion, we could “work it out” by swapping adjacent numbers to make it better.
32145 -> 23145 -> 21345 -> 12345.
I worked out — in my head, yay me — that I can readily define the operations to swap any adjacent pair in the train. For some value of “readily”.
With that in hand, it seems to me that it will be “easy” to take any given arrangement, stash the blanks as described above, then reduce the inversions in the remaining train one at a time until done. Maybe there is a faster way, but yesterday I had no solutions and today I nearly have one. Zero to one way is a big step. Sometime impossible yesterday is possible today.
If I’m right. But I’m confident that I am. I could be wrong. As one of my heroes often says, “I frequently am”, but I think this is not one of those times.
Good question. I am not sure, but I think next steps might include:
Somewhere along there, perhaps last, start breaking the train into two pieces, including the blanks, and build up the part that moves the situation to the canonical position: numbered cars in the 5-shunt, 1 blank in one 3-shunt and 2 blanks in the other. Put that code at the beginning and the problem is solved.
The basic idea of the program will be that there will be four “primitive” moving operations defined: Swap12, Swap23, Swap34, and Swap45. Then we’ll “just” scan the train from left to right, looking for inversions and when we find them, swap them. Repeat until there are no more. Declare victory.
Well, no. I call that a design idea, I guess, or a random pile of design ideas. But they are enough to get me started, and yesterday I was stopped. But yes, plenty needs to be figured out. Questions that I can see include:
What scheme, what operations, can be defined for moving from the random starting situation to the preferred starting situation with the numbered cars in the 5-shunt, and the blanks distributed between the 3-shunts?
How can we rig it so that we don’t care which 3-shunt has two blanks and which has one?
On the train layout, at least one swap, Swap45 requires us to stash the two low-order cars so that we can pull out numbers 4 and 5 to swap them. Similarly, if my imagination is correct, for Swap34, we need to stash the low-order car.
Are there any operations to swap two non-adjacent items more efficiently than the series of adjacent swaps?
Can we set things up so that the code can produce a plan before starting and somehow optimize the plan?
Can we write some constraints into the code so that we detect going through an illegal state through a bug in the code?
Suppose the starting position has numbered cars in the 3-cells, which it generally does. What operations starting from there might help with the overall situation? Something about collecting them in a low-inversion order? Mumble …
Can we write the program so that it can recognize certain situations, sub-trains if you will, and then “remember” how to solve that bit?
If we did that, would it really save anything but a tiny bit of computer time? Maybe not. Would it be fun? Maybe.
Right now, nothing. I think I’ll read my dragon fantasy romance book for a bit. But next steps beyond that will be some SLua code.
Safe paths!