rude_flier.pl

#!/usr/bin/perl -w

# Simulate the "will you get your seat on a plane if a rude passenger
# picks a seat at random at the start of boarding" puzzle posed here:
#    http://fivethirtyeight.com/features/will-someone-be-sitting-in-your-seat-on-the-plane/

# My spoilery attempt to explain the unexpected result this script generates is at
#   https://gist.github.com/RMGiroux/dd8856e68dd0ed5f3064

use strict;

my $passenger_and_seat_count = 100;

if (@ARGV) {
    $passenger_and_seat_count = shift;
}

# A Fisher-Yates shuffle is a simple and reliable way to get an O(N) shuffle of
# an array.
#
# From _Perl Cookbook_:
#     http://docstore.mik.ua/orelly/perl/cookbook/ch04_18.htm
sub fisher_yates_shuffle {
    my $array = shift;
    my $i;
    for ($i = @$array; --$i; ) {
        my $j = int rand ($i+1);
        next if $i == $j;
        @$array[$i,$j] = @$array[$j,$i];
    }
}

# Run one iteration of the simulation specified at
#    http://fivethirtyeight.com/features/will-someone-be-sitting-in-your-seat-on-the-plane/
sub simulate {
    # We have N passengers...
    my $passenger_and_seat_count = shift;

    # ... all with assigned seats in random order.
    my @passengers = (1..$passenger_and_seat_count);
    fisher_yates_shuffle(\@passengers);

    # Keep track of the seats free.  Use an array so we can do a random lookup,
    # and a hash so we can check availability.
    my @remaining_seats = (1..$passenger_and_seat_count);
    my %remaining_seats;

    @remaining_seats{@remaining_seats}=@remaining_seats;

    # The first passenger is a jerk, who sits in a random seat instead of his
    # assigned seat.
    my $jerk_seat = $remaining_seats[rand(@remaining_seats)];

    delete $remaining_seats{$jerk_seat};
    splice @passengers, 0, 1;

    # All the other passengers except the last one will...
    while(@passengers > 1) {
        my $desired_seat = $passengers[0];
        # ... sit in their assigned seat if available...
        if (!$remaining_seats{$desired_seat}) {
            # ... otherwise, sit in a random seat.
            @remaining_seats = keys %remaining_seats;
            $desired_seat = $remaining_seats[rand(@remaining_seats)];
        }

        # Delete the desired seat from the remaining seats.
        delete $remaining_seats{$desired_seat};
        # Delete the passenger from the queue.
        splice @passengers, 0, 1;
    }

    # Did the last passenger find their assigned seat unoccupied?
    return exists $remaining_seats{$passengers[0]};
}

# We'll run 1_000_000 iterations in chunks of 10_000 so we can see progress.
my $total_trials = 0;
my $total_seats  = 0;

foreach(1..100) {
    my $trials      = 0;
    my $got_my_seat = 0;
    foreach(1..10_000) {
        $got_my_seat += simulate($passenger_and_seat_count);
        $trials++;
    }

    printf "Trials: $trials, Successes: $got_my_seat, fraction: %.3f%%\n",
           100*$got_my_seat/$trials;

    $total_trials += $trials;
    $total_seats  += $got_my_seat;
}

printf "**Trials: $total_trials, Successes: $total_seats, fraction: %.3f%%\n",
       100*$total_seats/$total_trials;