Solve an Inglenook Sidings Puzzle

Question

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 and D)
• 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].

Answer 1

Charcoal, 120 bytes

⊞υ⪪”←‴⧴ν↘pＧ8¡¶”¶Ｗ¬⊙υ№κθ«≔υη≔⟦⟧υＦηＦ⁴Ｆ…·¹Ｌ⁻§κλ Ｆ⎇λ¹…¹¦⁴¿¬‹№§κν μ⊞υ⊞ＯＥκ⎇⁼πλ◨✂ξμχ¹Ｌξ⎇⁼πν⁺⮌…§κλμ✂ξ⁰±μ¹ξ⁺⁺…§κλμ§βλ§βν»✂⊟Φυ№ιθ⁴

Try it online! Link is to verbose version of code. Very brute force (spends most of its time shuffling the first wagon between sidings a and b) so can only solve simple cases on TIO. All moves are always between siding a and another siding. Moves list the wagons in the order that they enter the other siding, which for wagons leaving siding a is the reverse of what you might expect. Explanation:

⊞υ⪪”←‴⧴ν↘pＧ8¡¶”¶

Start with the initial position.

Ｗ¬⊙υ№κθ«

Repeat until a sequence of moves resulting in the desired position is found. (The code actually checks all sidings but only siding b can actually have that position of course.)

≔υη

Save the previously found positions.

≔⟦⟧υ

Start a new list of found positions.

Ｆη

Loop over the previously found positions.

Ｆ⁴

Consider each possible source siding.

Ｆ…·¹Ｌ⁻§κλ 

Consider all of the wagons in that siding.

Ｆ⎇λ¹…¹¦⁴

For siding a, consider the other three sidings as a possible destination, otherwise consider siding a as a possible destination.

¿¬‹№§κν μ

Check whether the destination has enough room for the number of wagons being moved.

⊞υ⊞ＯＥκ⎇⁼πλ◨✂ξμχ¹Ｌξ⎇⁼πν⁺⮌…§κλμ✂ξ⁰±μ¹ξ⁺⁺…§κλμ§βλ§βν

Create an updated position with the wagons moved to the other siding, plus append the current move, and save that to the list of positions.

»✂⊟Φυ№ιθ⁴

Output the moves required to reach the desired position.

I've written a version which is somewhat faster but still only manages to solve 43521 because it cheats and ignores siding c if the input contains no digit above 5. (The above version is so slow that even this optimisation doesn't help it.)

⊞υ⪪”←‴Fa×ι|”¶≔⮌υηＷ¬⊙η№κθ«≔ηζ≔⟦⟧ηＦζＦ⁴¿∧λ∨⁻λ²›⌈θ5«≔⁺§κ⁰§κλεＦ…·⌈⟦⁰⁻Ｌε⎇⊖볦⁵⟧⌊⟦³Ｌε⟧«≔⊞ＯＥκ⎇⁼ξλ✂εμχ¹⎇ξν✂ε⁰μ¹⁺μ§βλ먪№υ…δ⁴«⊞υ…δ⁴⊞ηδ»»»»✂⊟Φη№ιθ⁴

Try it online! Link is to verbose version of code.

The output of this version is not currently in a standard format, so I'll explain it here. Each line consists of a digit and a letter. The letter represents the other siding from or to which wagons are shunted to or from siding a. The digit represents the number of wagons that end up in siding a. Example:

    /12345/678/ Initial position
3b: 123/45/678/ Fill a with 3 wagons from b
0d: /45/678/123 Move all wagons from a to d
2b: 45//678/123 Fill a with 2 wagons from b
3d: 451//678/23 Fill a with 1 wagon from d
2b: 45/1/678/23 Move 1 wagon from a to b
3d: 452/1/678/3 Fill a with 1 wagon from d
1b: 4/521/678/3 Move 2 wagons from a to b
2d: 43/521/678/ Fill a with 1 wagon from d
0b: /43521/678/ Move 2 wagons from a to b

Answer 2

Python3, 1447 bytes:

R=range
E=enumerate
F=lambda s,e,m:s+''.join(map(str,m))+e
U=lambda x:eval(str(x))
def C(w,m,o,c,e):
 if[]==c:yield w,m;return
 for x in o:
  for i,y in E(c):
   if len(w[x][1])<w[x][0]:W=U(w);M=U(m);W[x][1]=([y if x!=1 else(y,)]+W[x][1]if x else W[x][1]+[y]);M+=[F(W[e][2],W[x][2],[y])];yield from C(W,M,o,c[:i]+c[i+1:],e)
def V(w,m,t,c):
 if w[1][1][:len(j:=[i for i in w[1][1]if type(i)==tuple])]==j:
  B=0
  for W,M in C(w,m,{0,2,3}-{c},[i for[i]in j],1):
   B=1
   W,M=U(W),U(M);W[1][1]=W[1][1][len(j):];W[c][1]=(W[c][1][1:]if c else W[c][1][:-1]);M+=[F(W[c][2],'B',[t])];W[1][1]=[t]+W[1][1];yield W,M,1
  if not B:
   w[c][1].remove(t)
   for W,M in C(w,m,{0,2,3}-{c},[t],c):yield W,M,0
def f(t):
 w,m=[{0:3,1:[],2:'A'},{0:5,1:[*R(1,6)],2:'B'},{0:3,1:[6,7,8],2:'C'},{0:3,1:[],2:'D'}],[]
 if w[1][1]==t:return m
 T=t[:(r:=max(e)+1 if(e:=[i for i in R(5)if t[i]!=w[1][1][i]])else 5)]or t;W=w[1][1][:r]
 w[1][1]=w[1][1][r:]
 if(M:=W[:3][::-1]):w[3][1]+=M;m+=[F('B','D',M[::-1])]
 if(M:=W[3:]):w[0][1]+=M;m+=[F('B','A',M[::-1])]
 q=[(U(w),U(m),T)]
 while q:
  W,M,T=q.pop(0)
  if[]==T:return M
  if(O:=[i for i in[0,2,3]if W[i][1]and W[i][1][(0 if i else -1)]==T[-1]]):
   for W,M,I in V(W,M,T[-1],O[0]):q+=[(W,M,T[:-1]if I else T)]
  else:
   if(O:=[i for i in [0,2,3]if T[-1]in W[i][1]]):
    [c]=O;S=(W[c][1][:1]if c else W[c][1][-1:]);W[c][1]=(W[c][1][1:]if c else W[c][1][:-1])
    for W,M in C(W,M,{0,1,2,3}-{c},S,c):q+=[(W,M,T)]
 return m

Not the shortest solution, and can be golfed further, but produces output moves for all the test cases in 0.2 seconds. For input, it takes a list of the desired car order, and the output is a list with all the moves.

Move notation:

<source siding>[cars moved]<destination siding>

For example, 'B123D' means "move cars 1, 2, and 3 from siding B to siding D.

Try it online!