Solve an Inglenook Sidings Puzzle
Background
The Inglenook Sidings Puzzle is a shunting/switching yard puzzle by Alan Wright for model railroading. The rules for the puzzle are as follows: (Source)
- Form a departing train consisting of 5 out of the 8 wagons sitting in the sidings.
- The 5 wagons are selected at random.
- The train must be made up of the 5 wagons in the order in which they are selected.
You have 4 sidings:
- The "main line", which is 5 cars long (labeled
B
) - Two spurs coming off the main line, each of which is 3 cars long (
C
andD
) - A yard lead, which is 3 cars long. (
A
)
(Source: http://www.wymann.info/ShuntingPuzzles/Inglenook/inglenook-trackplan.html)
The Challenge
Given the ordered list of cars in the train, generate the movements of the cars needed to form the train. These moves need not be the shortest solution.
The sidings
- Each siding can be considered to be an ordered list of cars.
- Each car can be represented by one of eight unique symbols, with an additional symbol the engine.
- Cars can only be pulled and pushed as if it were coupled to an engine on the
A
-direction (i.e. you cannot access a car from the middle of a siding without needing to remove the head/tail ends first.) - For this challenge, the starting state will be the same for all cases (where
E
is the engine, and digits are the 8 cars):
A E[ ] -- 12345 B
\-- 678 C
\- [ ] D
- The puzzle is considered solved if all five cars in the
B
-siding are in the same order as the input car list.
Input
Input is an ordered list of five car tags representing the requested train.
The car tags should be a subset of any 8 unique elements, e.g. {a b c d e f g h}
and {1 two 3 4 five six 7 eight}
are allowed sets of car tags, but {a b 3 3 e f g h}
is not allowed because not all elements are unique.
Output
Output is a list of moves for the cars. Examples of a single move can be:
B123A // source cars destination
BA123 // source destination cars
"Move from siding B cars 123 to siding A."
Among other formats. The source, destination, and cars moved should be explicit, and explained in whatever move format you choose.
If it is unambiguous that a cut of cars (a set of cars grouped together) moves unchanged from one siding to another, you can omit a step to the intermediate track, e.g. 1ba 1ad 2ba 2ad => 1bd 2bd
, e.g. 123ba 123ad 67ca 67ab 8ca 8ab => 123bd 67cb 8cb
, e.g. 5db 5ba => 5da
. All of these cases can be compacted due to a matching source-destination track, and the cut of cars moved doesn't change order. The test cases will use this compacted notation.
Movement Rules
The cars move similarly to real-life railroad cars: you usually can only access one end of the cut at a time. So, the following moves are illegal (assuming a starting state similar to the one described above):
1ba 2ba 1ad // trying to access car 1 but car 2 is blocking access, since the last car on the cut is now 2: E12
12ba 21ad // swapping the order of cars without any intermediate steps to swap them
12345ba 12345ad // trying to fit too many cars into a siding (5 > 3 for sidings A and D)
Additional Rules
- Standard loopholes are forbidden.
- Input and output can be in any reasonable format.
- This is code-golf, so shortest code wins!
Test Cases
The moves in these testcases will be in the form cars source destination
, separated by spaces. These are some possible solutions, and not necessarily the shortest.
Train -> Moves // comment
--------------
12345 -> // empty string, no moves needed
21345 -> 1bd 2bd 21db
14385 -> 123bd 67cb 8cb 867ba 67ac 4bc 8ab 123da 3ab 2ad 4ca 14ab
43521 -> 123ba 3ad 4ba 24ad 1ab 2db 215ba 5ad 21ab 5db 43db
86317 -> 67ca 7ad 8cd 6ac 8dc 1bd 23ba 3ad 45ba 5ac 3db 5cb 1db 4ac 7da 1bd 5bd 3bd 7ab 35db 1da 3bd 5bd 1ab 53da 3ab 25ad 4cd 86cb
Tips
- All Inglenook Sidings Puzzles are solvable if and only if the inequality \$(h-1)+m_1+m_2+m_3\ge w+M\$ is true, where \$h\$ is the capacity of the yard lead, \$m_1, m_2, m_3\$ are the capacities of the sidings, \$w\$ is the number of wagons, and \$M = \max(h-1, m_1, m_2, m_3)\$. For the initial state for the challenge, this is \$w = 8, h=m_1=m_2=3, m_3=5\$. (https://arxiv.org/abs/1810.07970)
- You can only take and give cars from the end of the cut facing the switches, similarly to a stack.
- A program to test your program output, input format is
final_state -> [cars_moved][source][destination]
.
67ca 7ad
(in the last test case) is a compressed form of67ca 67ad 6da
. But there must be at least 2 empty slots on line D for this move to be valid because cars 6 and 7 have to be temporarily put there. Is that correct? \$\endgroup\$8cd
is executed after67ca 7ad
, car6
is still attached to the locomotive, right? \$\endgroup\$67ca 7ad
means that cars 6 and 7 fromc
toa
, and car 7 by itself gets moved intod
. The car counts for each siding is for the max number of cars that can stay there, since (in real life/on models) the switches take some space and you can "hold" cars on there, but not really because it's not a siding track. \$\endgroup\$a
can be safely interpreted as cars attached to the engine. Alternatively (and more abstractly), all four can be interpreted as stacks where the only movement allowed is betweena
and one of the other three stacks. \$\endgroup\$