# Sorting passengers on a plane

A few days ago I made a puzzle about moving people on an airplane. Now I am interested in the general version of this puzzle and the shortest code golf for it.

I will briefly summarise the puzzle here. A small airplane went through some heavy turbulence and all its N passengers ended up sitting in reverse order, ie., passenger 1 ended up in seat N, while passenger N ended up in seat 1 and so on. Now they need to get back to their assigned seats. The image below shows the map of the plane for N=4. The circles are the passengers and the numbers indicate their assigned seat number.

Passengers can move into a neighbouring location provided that it is empty (not another passenger). They can move into, along and out of the corridor, but they cannot jump over seats. Each turn one passenger makes a single move. What is the fewest number of turns needed to get each passenger into their assigned seat?

The optimal solution for N=4 was found by @RobPratt:

26 moves:

....
4321

..2.
43.1

4.2.
.3.1

.42.
.3.1

.4.2
.3.1

..42
.3.1

...2
.341

..2.
.341

.2..
.341

2...
.341

2..1
.34.

2.1.
.34.

21..
.34.

214.
.3..

21.4
.3..

2.14
.3..

2314
....

231.
...4

23.1
...4

2.31
...4

.231
...4

.2.1
..34

...1
.234

..1.
.234

.1..
.234

1...
.234

....
1234

@RobPratt and @2012rcampion obtained optimal results for N <= 9:

N 1 2  3  4  5  6  7  8  9
L 0 NA 22 26 30 42 48 62 70


In this code golf challenge you will receive a single number N as input and your task is to compute the corresponding optimal number of steps L. You cannot simply output the table. Also this is a coding golf, so shortest code in bytes wins. However I am also interested to know the largest N that can be solved (even if the code is long).

• I guess this question is too hard for code golf... May 8, 2022 at 10:48
• If my answer over on Puzzling were proven then Python 2, 77 bytes May 8, 2022 at 19:26
• @JonathanAllan You can use N&~1 instead of N-N%2. May 8, 2022 at 19:36
• @Arnauld thanks, I wasn't really expecting a golf to be had there! May 8, 2022 at 19:38

# Python3, 436 bytes:

R=range
C=lambda x:eval(str(x))
def f(n):
q,s=[O:=([0]*n,[*R(n,0,-1)],0)],[O[:-1]]
while q:
g,p,c=q.pop(0)
if sorted(p)==p and all(p):return c
Y=[]
for i in R(n):
for I in[i-1,i+1]:
if(G:=g[i])and n>I>=0 and g[I]==0:N=C(g);N[I]=G;N[i]=0;Y+=[(N,p)]
if p[i]==0:N=C(g);P=C(p);N[i]=0;P[i]=g[i];Y+=[(N,P)]
if p[i]and g[i]==0:N=C(g);P=C(p);N[i]=p[i];P[i]=0;Y+=[(N,P)]
for i in Y:
if i not in s:s+=[i];q+=[(*i,c+1)]


Try it online!

• Can you explain what this is doing? May 7, 2022 at 23:58
• @DmitryKamenetsky This simulates the process of passengers moving between seats via an aisle (represented as the list g), terminating when the proper arrangement (in list p) is found. May 8, 2022 at 1:00
• +=[x] can be +=x,; Copying lists of ints can be done by multiplying the list by 1; You can iterate over q with a for loop; chained comparisons instead of and; ... and some other stuff to get to 362 bytes
– ovs
May 8, 2022 at 13:42
• 310
– ovs
May 8, 2022 at 13:48
• You can save another byte off of ovs's by doing if(i in s)^1 instead of if i not in s May 8, 2022 at 14:31

# APL(Dyalog Unicode), 91 79 bytes SBCS

Returns -1 for N=2, representing not possible to solve.

{i←⍵<3:1-⍵⋄i⊣{i+←1⋄∪,⍵∘.{0∊⌷∘⍺¨⍵:⌽@⍵⊢⍺⋄⍺}(↓⍤⍉,2,⍥⊂/⊣⌿)⍳⍴⊃⍵}⍣{⍺∊⍨⌽¨q}q←⊂⍉0,⍪⌽⍳⍵}


Try it on APLgolf!

Does a BFS over all possible sequences of turns, storing states of the grid as a 2×4 matrix with empty spaces represented as 0's. Some comments (slightly outdated):

{
i←⍵<3:1-⍵           ⍝ handle ⍵∊1 2, set i to 0 for all other cases
q←⊂0 1∘.×⌽⍳⍵        ⍝ start with a list containing only the initial grid
{ ... } ⍣ {⍺∊⍨⌽¨q}  ⍝ iterate left function until *initial grid* with rows reversed appears in reached grids
{
i+←1                ⍝ increment i
∪⊃,/{ ... }¨⍵       ⍝ for each grid, call inner function, then flatten result and remove duplicates
{
s←(↓⍤⍉,2,⍥⊂/⊣⌿)⍳⍴⍵  ⍝ all possible swaps inside the grid
s/⍨0∊¨⌷∘⍵¨¨s        ⍝ keep only the swaps where one of the value in the current grid is a 0
⍵∘{⌽@⍵⊢⍺}¨          ⍝ apply all of these swaps
}
}
i ⊣                 ⍝ return the value of i
}


Technically the ∪ to remove duplicate states after each iteration is not necessary, but without it even N=3 takes forever.

• This is very impressive! May 8, 2022 at 17:00