100 passengers revisited

As with the article about the puzzle itself, this article is an update from a few years back, when I was literally new to Python. Today I am professionally involved in Cloud Computing (first Azure, now AWS) and use Python a lot.

And now for something completely different…Python to the rescue

For some years I toyed with the idea of learning Python – but I never got to the point of actually diving into it. The puzzle with the 100 passengers inspired me to create a python based simulation – without knowing any python! I roughly know how to convert ideas about such a simulation into an algorithm. But filling in the details and doing this with python was completely new and provided an interesting challenge. Sounds like fun!

Here’s the plan

After installing a basic programming environment for Python (I’d suggest vscode nowadays) and running the hello world program I was ready to start coding! The main idea is to do a simulation of passengers entering the plane one by one and taking their legitimate seats – or a random one if they lost their ticket or if their seat has already been taken. Doing such a simulation, say, a 1000 times should give us a fair indication of the odds for the last passenger to take his own seat. My personal challenge was mostly about converting my ideas into python – the logic of the program is simple enough. Exciting stuff and good to have partners in crime like Google and StackOverflow 😄.

Results

I looked up how to do the basic stuff in Google: loops, variables & arrays (actually lists in native python types), if-then-else statements, random numbers. After gluing everything together I ended up with the program below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/python
from random import randint, shuffle

# run sim 1000 times, keep track of succesful runs
success = 0
iterations = 1000

for iteration in range(iterations):

    # for passengers we need to keep track of the passenger number and the seat number
    # the index is the passenger number 0-99 and the content/value indicates the seat number
    # note passenger[0] is set to -1 to indicate he lost his ticket
    # note: seat numbers do not need to be randomly distributed, but for fun we shuffle their tickets
    passengers = [*range(100)]
    # shuffle(passengers)
    passengers[0] = -1

    # for seats we need to keep track of the seat numbers and their status (taken or not)
    # the index is the seat number 0-99 and the content is either -1 (free) or x (taken by passenger x)
    seats = [-1] * 100

    # in each run we loop over all the passengers and their ticketnumbers
    for passengerNumber, seatNumber in enumerate(passengers):

        # if ticketnr is invalid or if seat is taken we must find a random seat
        if seatNumber == -1 or seats[seatNumber] != -1:
            # take a random free seat
            freeSeats = [i for i, j in enumerate(seats) if j == -1]
            randomFreeSeat = freeSeats[randint(0, len(freeSeats) - 1)]
            seats[randomFreeSeat] = passengerNumber

        else:
            # just take the given seat
            seats[seatNumber] = passengerNumber

    # run is successful if last passenger 99 was seated according to his ticketNumber
    if seats[passengers[99]] == 99:
        success += 1

# finally we print out how often we had a successful run
print("Success rate is ", success, " out of ", iterations)

Wow! In a few hours time you  can convert such ideas into working python code! The results are good, indeed we end up with something close to 50% after 1000 runs. On my mac this runs in about 130 ms which I think is quite fast considering the age of my iMac (2014), the nature of Python (interpreted language, not optimal for speed) and the fact that my program is not optimized for speed in any ways.

I experimented with keeping track of the free seats in an extra list. Not generating this list on the fly every time would surely speed things up right? Nope. To my surprise it turned out that the overhead of setting up an extra list and keeping it up to date was more than I gained back by not having to generate the free seats.