9
\$\begingroup\$

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.

enter image description here

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).

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

2 Answers 2

3
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ Can you explain what this is doing? \$\endgroup\$ May 7 at 23:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Ajax1234
    May 8 at 1:00
  • \$\begingroup\$ +=[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 \$\endgroup\$
    – ovs
    May 8 at 13:42
  • 1
    \$\begingroup\$ 310 \$\endgroup\$
    – ovs
    May 8 at 13:48
  • \$\begingroup\$ You can save another byte off of ovs's by doing if(i in s)^1 instead of if i not in s \$\endgroup\$
    – Steffan
    May 8 at 14:31
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ This is very impressive! \$\endgroup\$ May 8 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.