Let’s think about the design a bit. I’m envisioning six separate segments where cars or locomotive can be located:
- Lead_In - 4-cell lead-in track;
- Points_1 - 1-cell switch, from Lead to Shunt_1 or Points_2;
- Shunt_1 - 5-cell shunt;
- Points_2 - 1-cell switch, from Points_1 to Shunt_2 or Shunt_3;
- Shunt_2 - 3-cell shunt;
- Shunt_3 - 3-cell shunt.
L L L L P1 S1 S1 S1 S1 S1
P2 S2 S2 S2
S3 S3 S3
THe game starts with cars filling S1 and S2, in some random order, and the loco somewhere in L.
It is legal to have things on the points but if there is anything on a point it cannot be switched, so we will generally be able to ignore that state and the solver should never create such a state.
When I’m playing the game, what am I thinking about? One common task is to swap some two adjacent cars that are in the wrong order in S1. If they are close enough to the front of the train and there is at least one cell available in each of S2 and S3, I can do it, like this:
- Couple up to S1, cutting after the second of the two;
- Drive down past the switches, set to connect to S2;
- Push cars into S2, cutting off the furthest one;
- Back away, set to connect to S3;
- Push remaining car into S3 and cut;
- Back away, set to S2;
- Go get the car that’s there;
- Back away, set to S3;
- Go get the car that’s there.
Now those two cars are in the correct order.
Let’s call the loco zero and the cars 1-5 and x x x. Empty spaces will be underbar. Suppose we have this:
LI: _ _ 0 _
S1: 2 1 3 4 5
S2: _ x x
S3: _ _ x
We might show the transformations something like this:
| LI | S1 | S2 | S3 | action |
|---|---|---|---|---|
| ___0 | 21345 | _xx | __x | |
| _021 | 345__ | _xx | __x | Get 2,1 and pull back |
| ___0 | 345__ | 2xx | __x | Push 2 into S2 |
| ___0 | 345__ | 2xx | 1_x | Push 1 into S3 |
| __01 | 345__ | 2xx | __x | Pull 1 out of S2 |
| _012 | 345__ | _xx | __x | Pull 2 out of S3 |
| ____ | 12345 | _xx | _.x | Push 1,2 up to 3,4,5 |
Train complete!
Digression: What am I up to?
The above was written on Monday. It is now Tuesday. Here’s what’s on my mind just now.
Based on the fact that I’ve been unable to find any usable code or algorithms for shunting, I’m pretty sure that the problem does not succumb to some algorithm the way that, say, Towers of Hanoi does, even though some of my moves in shunting do remind me of those moves in Towers, where you put the disc you’re thinking about on a post where you don’t want it, to clear the post for something you need to move first, and then you move the disc back. But Towers is just counting in binary, so the resemblance is pretty thin.
But as I play the game, I sense certain patterns, such as:
-
During most of the game, I like to keep at east one open slot in each of the 3-cell shunts. That’s to facilitate reversing two cars:
-
If two adjacent cars are in the wrong order, BA, we can reverse the order by stashing A in one 3-cell, stashing B in the other, then picking up A, then picking up B, giving AB.
-
I do not consciously have this pattern, but it seems clear that we can change BxA to ABx or xAB by a similar series of swaps, perhaps also using the 5-cell as a stash.
-
I totally do not have this pattern, but it seems to me that there is probably an overall strategy in play, such as “solve the high end first”, or “solve the low end first”. It is possible—again, I don’t have the pattern yet—that there are times when we should start at the end nearest the loco and others when we should not, depending on the value sequence.
-
It seems like a good idea to get the blank cars into the 3-cell shunts, to get them out of the way. However, it is likely that a blank at the very end of the starting setup can be left there.
What I’m trying to come to with all this thinking is a sort of “language” of shunting. I’d like to have a way of expressing the situation that is easy to write, easy to read, and easy (enough) to process. I’d like to have a small set of “phrases” that are useful for expressing reasonable-sized steps toward a solution. Phrases like “stack #3 in shunt 2”, or “pick up #3”, perhaps.
In trying to think about this “language”, I think about how I’d like to tell someone else the moves to solve the game. “OK, let’s pick up the 5 and stash it in shunt 3”. As we played that way, I suspect we would make up new language, as we learned large patterns. “Let’s do a swap of the 3 and 2”. We’d probably come up with ways of expressing goals.
Take a look at this sample starting position:
What might we say if we were planning how to attack this puzzle?
-
It looks to me as if we might want to build up a 345 combo in S3. We could park the 5 there, then pull the 4 out of S2 and push it in with the 5. Then we’d put the two blanks back in S2.
-
Yes. Then we could drop the 1 and, I think, put the 3 in with 45.
-
But what about the extra blank, and the 1 and 2?
-
I’m not sure, but I think we could do the 21 swap using S1 and S2. If we can’t, though, we’ll be in deep trouble.
-
No, worst case we have to make temporary room in S3, but I think we’ll be OK.
-
Let’s try it!
Now I’m going to try it and write down what I think and do:
- Move 5 to S3; Pull out xx4 from S2, put 4 in S3, put xx back in S2.
- (put xx back in S2)
- pull 2x3 out of S1, move 3 to S3 with 4 and 5.
- Go back for the 1 in S1 and move it to S2;
-
Ah. Now we can push 2 back into S1, grab the 1 and attach it, giving 12, and then go pick up 345 and done.
-
Push 2 into S1
- Go get 1
- Go get 2 and pull it down
- Back 12 into 345 and done!
We’re getting closer to a language. I don’t think we’re there yet: I don’t know how to write a script that understands plain English. But there are some common notions that might be showing up.
-
Pull <sequence> downmight be a good verb phrase meaning to find where that sequence is, move to it, snip it out if necessary to truncate it, then pull it down into the lead-in. In practice I don’t always pull them all the way down, just far enough to clear the switches, but the computer probably can’t be quite that clever. -
Stash <sequence> in Snmight be a phrase meaning to move from the lead in and drop off the sequence (presumably a sub-sequence of what’s in lead-in) in the designated shunt. -
Maybe something like
connect n and n+1could cover cases like where we connected the 3 to the 45 or the 1 to the 2. -
Could we handle the last case as
connect 2 to 3and be at least clever enough to push up and over to S3 to connect 2 to 3 and finish the train? It’s really only one move.
Summary — For Now
Maybe you begin to see what I’m trying to do. I’m trying to devise a way of expressing changes to the layout that make sense in terms of shunting, but that are simple enough that we can imagine implementing them as reasonably simple operations. We might even be able to express some commands as sequences of others. Kind of like macros or something.
Or just functions calling other functions, methods calling other methods.
If I can come up with a reasonable set of phrases and a reasonable way to represent the current state of the layout, it might, just might, be possible to make a little progress.
Caveat emptor, though. In view of the very limited amount of information about solutions, and in view of my very limited brain, I’m not optimistic about a full solution to even the simple Ingelnook case. But we might make some progress, and we will almost certainly at least come up with some convenient commands to provide to people who want to build a switch yard of their own.
We’ll see. So far, just learning.
Safe paths!