2009-09-10

Airplane problem simulator

I just got back from a party where a friend of mine told me the classic "Airplane seating problem", and the resulting answer. The answer was somewhat hard for me to believe, so, since I had brought my laptop, I pulled it out and spent 10 minutes writing this program to simulate the airplane problem. It turns out that the answer he had told me is correct. I'll be darned.

Anyway, here's the program, written in Java. Paste it into a file called PlaneSim.java, run "javac PlaneSim.java" and then "java PlaneSim" to run it. The javadoc at the beginning of the program explains what the airplane problem is, in case you haven't heard of it before.

import java.util.Random;

/**
* There's a common puzzle that goes something like this: There's a plane that
* has 100 seats in it. Each person has a ticket that assigns them to a
* particular seat. However, the first person doesn't follow his ticket, instead
* choosing a random seat to sit in. Each successive person tries to sit in the
* seat listed on their ticket. If that seat is already taken, they choose a
* random vacant seat to sit in. This goes on until all 100 passengers have been
* seated. What is the chance that the last person will be in his correct seat?
* The puzzle's correct answer is 0.5 (IE he's in his correct seat about half of
* the time on average). This program simulates the airplane problem several
* thousand times to verify this answer, and it does, indeed, verify that 0.5 is
* the correct answer.
*
* @author Alexander Boyd
*
*/
public class PlaneSim
{
private static int seatcount;

/**
* @param args
*/
public static void main(String[] args)
{
seatcount = 100;
// Run 100,000 simulations
int simcount = 100000;
int correctTimes = 0;
for (int i = 0; i < simcount; i++)
{
correctTimes += ((sim() == (seatcount - 1)) ? 1 : 0);
}
System.out.println("Simulation count: " + simcount);
System.out.println("Last person was in correct seat " + correctTimes
+ " times");
}

public static int sim()
{
int[] seats = new int[seatcount];
// Change all seats to be empty
for (int i = 0; i < seats.length; i++)
{
seats[i] = -1;
}
// Run the simulation
for (int i = 0; i < seatcount; i++)
{
if (i == 0)
{
// First person, so random seat
seats[random()] = 0;
}
else
{
// Put this person in their seat if it's empty
if (seats[i] == -1)
{
seats[i] = i;
}
// If it's not empty, randomly place this person until we get an
// empty seat to put them in.
else
{
int randomIndex = random();
while (seats[randomIndex] != -1)
randomIndex = random();
seats[randomIndex] = i;
}
}
}
// Simulation is done. Now see who's in the last seat.
return seats[seatcount - 1];
}

private static Random random = new Random();

public static int random()
{
return random.nextInt(seatcount);
}
}

No comments: