21
$\begingroup$

A small plane went through some heavy turbulence and all its passengers ended up in the wrong seat. Now they need to get back to their assigned seats. The image below shows the map of the plane. The circles are the passengers and the numbers indicate their assigned seat number. For example the left-most passenger needs to get to the right-most seat.

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?

$\endgroup$
3
  • $\begingroup$ Can you define a single move? Is it one square? For example, how many moves would Passenger 2 -ULLL be? $\endgroup$ Commented May 4, 2022 at 15:53
  • 1
    $\begingroup$ Any turbulence sufficient to result in people vaulting over 3 seats (in both directions) is likely to result in most of them being too injured to be able to get back to their original seats... $\endgroup$ Commented May 5, 2022 at 20:50
  • 1
    $\begingroup$ @DarrelHoffman I am still confused on why the injured people even want to go back if everyone has a window or aisle seat! Just get your baggage after you land. $\endgroup$
    – Varun W.
    Commented May 9, 2022 at 3:03

4 Answers 4

16
$\begingroup$

Consider an undirected graph where each node corresponds to one possible arrangement of passengers and two nodes are linked if you can get from one node to the other by a single passenger moving one step. This graph has $8!/4!=8\cdot7\cdot6\cdot5=1680$ nodes, and we are looking for a shortest path between two specific nodes. Running a shortest path algorithm on this graph gives the following solution with the minimum number of moves:

26:

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


By request, here is SAS code:

proc optmodel;
   num n = 4;
   set PEOPLE = 1..n;
   set SLOTS = 1..2*n; /* 1..n is top row, n+1..2*n is bottom row */

   /* use constraint programming solver to enumerate all (2n)!/n! assignments of people to slots */
   var X {PEOPLE} >= 1 <= 2*n integer;
   con Alldiff: alldiff(X);
   solve with clp / findallsolns;
   put (fact(2*n)/fact(n))=;

   /* construct nodes from solutions */
   set NODES;
   NODES = 1.._NSOL_;
   set <str> SOLS init {};
   num slot {NODES, PEOPLE};
   str solStr {NODES};
   str solStrThis;
   num isAssigned;
   num nodeId {SOLS};
   num sloti, slotj, isEdge, diff, countDiffs;
   for {node in NODES} do;
      solStrThis = '';
      for {s in SLOTS} do;
         isAssigned = 0;
         for {p in PEOPLE: X[p].sol[node] = s} do;
            slot[node,p] = s;
            solStrThis = solStrThis||p;
            isAssigned = 1;
            leave;
         end;
         if isAssigned = 0 then solStrThis = solStrThis||'.';
      end;
      SOLS = SOLS union {solStrThis};
      nodeId[solStrThis] = node;
      solStr[node] = solStrThis;
   end;

   /* construct edges */
   set <num,num> EDGES init {};
   str solStrNext;
   num nodeNext;
   for {i in NODES} do;
      solStrThis = solstr[i];
      for {p in PEOPLE} do;
         /* current slot occupied by person p */
         sloti = slot[i,p];
         /* person p moves up */
         if sloti - n in SLOTS and substr(solStrThis,sloti-n,1) = '.' then do;
            solStrNext = 
               (if sloti-n-1 in SLOTS then substr(solStrThis,1,sloti-n-1) else '')
               ||p
               ||substr(solStrThis,sloti-n+1,n-1)
               ||'.'
               ||(if sloti+1 in SLOTS then substr(solStrThis,sloti+1) else '');
            nodeNext = nodeId[solStrNext];
            if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
         end;
         /* person p moves down */
         if sloti + n in SLOTS and substr(solStrThis,sloti+n,1) = '.' then do;
            solStrNext = 
               (if sloti-1 in SLOTS then substr(solStrThis,1,sloti-1) else '')
               ||'.'
               ||substr(solStrThis,sloti+1,n-1)
               ||p
               ||(if sloti+n+1 in SLOTS then substr(solStrThis,sloti+n+1) else '');
            nodeNext = nodeId[solStrNext];
            if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
         end;
         /* person p moves left */
         if sloti in 2..n and substr(solStrThis,sloti-1,1) = '.' then do;
            solStrNext = 
               (if sloti-2 in SLOTS then substr(solStrThis,1,sloti-2) else '')
               ||p
               ||'.'
               ||(if sloti+1 in SLOTS then substr(solStrThis,sloti+1) else '');
            nodeNext = nodeId[solStrNext];
            if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
         end;
         /* person p moves right */
         if sloti in 1..n-1 and substr(solStrThis,sloti+1,1) = '.' then do;
            solStrNext = 
               (if sloti-1 in SLOTS then substr(solStrThis,1,sloti-1) else '')
               ||'.'
               ||p
               ||(if sloti+2 in SLOTS then substr(solStrThis,sloti+2) else '');
            nodeNext = nodeId[solStrNext];
            if i < nodeNext then EDGES = EDGES union {<i,nodeNext>};
         end;
      end;
   end;

   /* use network solver to find shortest path from source to sink */
   num sourceArray {i in SLOTS} = (if i <= n then . else 2*n+1-i);
   str sourceStr = cat(of sourceArray[*]);
   num sinkArray {i in SLOTS} = (if i <= n then . else i-n);
   str sinkStr = cat(of sinkArray[*]);
   set SOURCE = {nodeId[sourceStr]};
   set SINK   = {nodeId[sinkStr]};
   set <num,num,num,num,num> PATHSNODES; /* source, sink, path, order, node */
   solve with network / shortpath=(source=SOURCE sink=SINK) links=(include=EDGES) out=(pathsnodes=PATHSNODES);
   for {<s,t,p,o,i> in PATHSNODES} do;
      put 'Move ' (o-1);
      put (substr(solStr[i],1,n));
      put (substr(solStr[i],n+1,n));
      put;
   end;
quit;

Here are shortest path lengths: \begin{matrix} n & \text{nodes} & \text{edges} & \text{length} \\ \hline 1 & 1 & 0 & 0 \\ 2 & 12 & 12 & \text{infeasible} \\ 3 & 120 & 180 & 22 \\ 4 & 1680 & 3360 & 26 \\ 5 & 30240 & 75600 & 30 \\ 6 & 665280 & 1995840 & 42 \\ 7 & 17297280 & 60540480 & 48 \\ 8 & & & 62 \\ 9 & & & 70 \\ \end{matrix}

$\endgroup$
10
  • $\begingroup$ I was about to post the same thing. My computer program also found this minimum. $\endgroup$ Commented May 4, 2022 at 18:19
  • 1
    $\begingroup$ @DmitryKamenetsky it doesn't have to be. 4 can take a seat before 3 goes out. $\endgroup$
    – justhalf
    Commented May 5, 2022 at 6:52
  • 3
    $\begingroup$ RobPratt, could you share your program/algorithm? I have no idea how this kind of things are done... $\endgroup$ Commented May 5, 2022 at 8:29
  • 1
    $\begingroup$ I found solutions for 8 and 9 using A* search; I added the lengths to your table instead of making my own answer, I hope that's OK. $\endgroup$ Commented May 6, 2022 at 3:25
  • 2
    $\begingroup$ @RobPratt Dynamically as needed; for n=9 there are something like 17 billion total nodes, I only had to generate around 130 million. But for n=10 I need to generate at least 250 million nodes which is too much for my memory. Possibly with a better heuristic I would be able to prune more of the search tree, currently I'm just using the total distance all passengers have to move, disregarding any crossings. $\endgroup$ Commented May 6, 2022 at 3:34
9
$\begingroup$

Here is my first attempt, done by hand. This is probably not optimal.

   0     ....
         4321

   3     2...
         43.1

   6     2...
         431.

   10    2...
         4.13

   12    ....
         4213

   16    ...4
         .213

   20    ...4
         12.3

   22    .4..
         12.3

   25    .4..
         123.

   28    ....
         1234

EDIT:
I ran it through my computer, and it found an optimal solution with

26 moves.

It is essentially the same as RobPratt's solution.

$\endgroup$
2
  • 2
    $\begingroup$ All my attempts end up with this same number of moves. $\endgroup$
    – Florian F
    Commented May 4, 2022 at 16:47
  • 5
    $\begingroup$ Could you post your computer program as well? $\endgroup$ Commented May 5, 2022 at 2:58
6
$\begingroup$

A scheme which I believe might be optimal in the general case

...but I cannot prove it.

Assume there are $N\ge 4$ passengers (less may be considered special cases).

 x   x   ...  x   x
 N   M   ...  2   1

(Labelling $N-1$ as $M$ for convenience)

Passengers $1$ and $N$ must swap seats, but cannot move out of each other's way so we will do this while $2$ and $M$ also swap seats, leaving any other passengers where they are:

  • Passenger $2$ moves up and right letting $N$ take that (incorrect) seat.
  • Passenger $M$ moves up and left letting $2$ take their seat.
  • Passenger $1$ moves up and $2$ left letting $N$ take their seat.
  • Passenger $1$ moves $2$ right letting $M$ take their seat.
  • Passenger $1$ takes their seat.

This has costs ($\text{Passenger}: \text{moves}$): $$1:N+5$$ $$2:N+1$$ $$M:N+1$$ $$N:N+3$$

The rest of the passengers then proceed to swap seats in pairs of low and high passenger numbers $L$ and $H$, like so:

  • Passenger $L$ moves up and right
  • Passenger $H$ takes their seat
  • Passenger $L$ takes their seat

This has costs ($\text{Passenger}: \text{moves}$): $$L: N-(2L-3)+2$$ $$H: N-(2L-3)$$

Note that when $N$ is odd one passenger does not move at all.

So the total cost for $N\ge4$ passengers is:

$$N(N-(N\mod 2))+10-\sum_{L=3}^{\lfloor\frac{N}{2}\rfloor}(4L-8)$$

This gives the same results as the searches in other answers:

$$4:26$$ $$5:30$$ $$6:42$$ $$7:48$$ $$8:62$$ $$9:70$$ $$10:86$$


Here is some Python code that runs the scheme outlined above outputting the state at the start and after each passenger moves, along with the moves taken up to that point.

$\endgroup$
7
  • $\begingroup$ Brilliant. This feels like it must be optimal, I bet someone on Math SE could make this idea rigorous $\endgroup$
    – Jonah
    Commented May 9, 2022 at 1:17
  • $\begingroup$ This is very cool and may indeed be optimal! Now we just need someone to prove it or at least find a few more terms. $\endgroup$ Commented May 9, 2022 at 12:06
  • 1
    $\begingroup$ I can confirm that $N=10$ can be done in 86 moves, which is what the amazing formula predicts. $\endgroup$ Commented May 13, 2022 at 14:19
  • $\begingroup$ ...and not in less? $\endgroup$ Commented May 13, 2022 at 16:48
  • 1
    $\begingroup$ The scheme works, so it's certainly an upper bound. I've added Python code that prints the movements and total moves. $\endgroup$ Commented May 14, 2022 at 22:00
1
$\begingroup$

Since it appears that some people are interested in the code, here is a golang sample for this problem. Playground. Credit to RobPratt for describing the solution.

// https://puzzling.stackexchange.com/q/116014/12376
// This is programmed for ease of understaning not for efficiency
package main

import (
    "fmt"
    "github.com/marselester/alg/digraph/spt"
    "github.com/marselester/alg/digraph/weighted"
)

// Total number of nodes in the arrangements graph
const nodesTotal = 8 * 7 * 6 * 5

// There are many ways to model an arrangement
// We will go with an array of corridor spots and an array of seats
type arrangement struct {
    corridor [4]int
    seats    [4]int
}

// This helper function prints out a single "lane" for output:
// either the corridor lane or seats late
func printLane(lane [4]int) {
    for _, i := range lane {
        if i == 0 {
            fmt.Print(".")
        } else {
            fmt.Print(i)
        }
    }
    fmt.Println()
}

// We will need to output our steps in the result
// this will print out an arrangment
func (p arrangement) print() {
    printLane(p.corridor)
    printLane(p.seats)
}

// Place a single passenger on their designated spot:
// seats are numbered from 0 to 3 left to right,
// and corridor spots are numbered 4 to 7 (place parameter)
// Passengers are 1 to 4
func (p *arrangement) placeOne(passenger int, place int) {
    if place > 3 {
        p.corridor[place-4] = passenger
    } else {
        p.seats[place] = passenger
    }
}

// Given 4 placements for each passenger from 1 to 4
// place them in an arrangement
func (p *arrangement) placeAll(place1 int, place2 int, place3 int, place4 int) {
    p.placeOne(1, place1)
    p.placeOne(2, place2)
    p.placeOne(3, place3)
    p.placeOne(4, place4)
}

// Each passenger can potentially move in four directions
// if they are in a corridor they can move left and right
// and also "down" to a seat
// If they are in a seat they can potentially move up to the corridor
// The next four functions assume that the target space exists
// and is vacant and move the passenger
func (p arrangement) moveLeft(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.corridor[place-1] = passenger
    return
}

func (p arrangement) moveRight(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.corridor[place+1] = passenger
    return
}

func (p arrangement) moveDown(passenger int, place int) (result arrangement) {
    result = p
    result.corridor[place] = 0
    result.seats[place] = passenger
    return
}

func (p arrangement) moveUp(passenger int, place int) (result arrangement) {
    result = p
    result.seats[place] = 0
    result.corridor[place] = passenger
    return
}

// This is used to build the graph, it gets us
// all possible moves from a given arrangement
func (p arrangement) getNeigbours() (result []int) {
    for i, a := range p.corridor {
        if a != 0 { // if corridor space occupied
            if i > 0 && p.corridor[i-1] == 0 { // if vacant on the left
                result = append(result, lookup[p.moveLeft(a, i)])
            }
            if i < len(p.corridor)-1 && p.corridor[i+1] == 0 { // if vacant on the right
                result = append(result, lookup[p.moveRight(a, i)])
            }
            if p.seats[i] == 0 { // if vacant seat "down"
                result = append(result, lookup[p.moveDown(a, i)])
            }
        }
    }
    for i, a := range p.seats {
        if a != 0 { // if seat occupied
            if p.corridor[i] == 0 { // if vacant corridor space "up"
                result = append(result, lookup[p.moveUp(a, i)])
            }
        }
    }
    return
}

// Map each arrangement to an index 0..nodesTotal-1
// the index is required by the path search data structure
var lookup = map[arrangement]int{}

// And map back from index to arrangement
var arrangements [nodesTotal]*arrangement

func main() {
    index := 0
    for a := 0; a < 8; a++ {
        for b := 0; b < 8; b++ {
            for c := 0; c < 8; c++ {
                for d := 0; d < 8; d++ {
                    // One place cannot be occupied by two people
                    // so if this is the case, bail out
                    if a == b || a == c || a == d || b == c || b == d || c == d {
                        continue
                    }
                    // Create a new arrangement for the current loop iteration
                    p := arrangement{}
                    p.placeAll(a, b, c, d)
                    // Fill in both mapping from arrangement to index and back
                    arrangements[index] = &p
                    lookup[p] = index
                    index++
                }
            }
        }
    }

    // Create graph with all the nodes and edges
    graph := weighted.NewAdjacencyList(nodesTotal)
    for p, i := range lookup {
        for _, e := range p.getNeigbours() {
            graph.Add(&weighted.Edge{i, e, 1})
        }
    }

    // Get the start arrangememnt
    start := arrangement{}
    start.placeAll(0, 1, 2, 3)

    // Get the finish arrangememnt
    finish := arrangement{}
    finish.placeAll(3, 2, 1, 0)

    start.print()

    // Find a shortest path
    d := spt.NewDijkstra(graph, lookup[start])
    path := d.PathTo(lookup[finish])

    // Print resutls
    for i, p := range path {
        fmt.Printf("Step %d\n", i+1)
        arrangements[p.W].print()
    }
}

Output:

....
1234
Step 1
1...
.234
Step 2
.1..
.234
Step 3
..1.
.234
Step 4
...1
.234
Step 5
..31
.2.4
Step 6
.231
...4
Step 7
2.31
...4
Step 8
23.1
...4
Step 9
231.
...4
Step 10
2.1.
.3.4
Step 11
21..
.3.4
Step 12
21.4
.3..
Step 13
214.
.3..
Step 14
21..
.34.
Step 15
2.1.
.34.
Step 16
2..1
.34.
Step 17
.2.1
.34.
Step 18
..21
.34.
Step 19
..2.
.341
Step 20
...2
.341
Step 21
..42
.3.1
Step 22
.4.2
.3.1
Step 23
.42.
.3.1
Step 24
4.2.
.3.1
Step 25
4...
.321
Step 26
....
4321

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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