Home > python > Prison break

Prison break


The big boss of Montreal Prison celebrates his 50th birthday next week. For this special occasion he came up with the idea to let some prisoners go. In the prison there are 600 cells, one person in each. The cells are numbered from 1 to 600. The prison guard should go through all cells and open the doors. Then he goes to the 2nd cell and flips the lock at every second cell (that is, close the door if it was open and open it if it was closed). Then go the 3rd cell and flip the lock of every third cell, etc. This procedure should be repeated with every cell. Question: who are those lucky guys who get release, i.e. which cells remain open at the end?

Example with 8 cells:

00000000        initialization, all cells are closed
11111111        step 1, flip every lock
10101010        step 2, flip every 2nd lock
10001110        step 3, flip every 3rd lock
10011111        step 4, flip every 4th lock
10010111        step 5, flip every 5th lock
10010011        step 6, flip every 6th lock
10010001        step 7, flip every 7th lock
10010000        step 8, flip every 8th lock


#!/usr/bin/env python


cells = []
# initialization, all cells are closed
for i in range(SIZE+1):             # we won't use the cell at index 0

for i in range(1, SIZE+1):          # interval [1, SIZE], i.e. SIZE included
    for j in range(i, SIZE+1, i):
        cells[j] = 1 - cells[j]     # Flip the lock. If it was 0, set it to 1, and vice versa.

for i,v in enumerate(cells):
    if v == 1:
        print i,

I won’t answer the question, try it yourself :)

Some notes:

The function range(n) returns a list with elements from 0 to n-1, i.e. n is excluded. For instance, range(5) creates the list [0, 1, 2, 3, 4]. For range, you can specify the beginning of the interval too: range(5, 10) returns [5, 6, 7, 8, 9]. With the third parameter you can specify the step: range(0, 10, 3) means every third element in the interval [0,9], i.e. [0, 3, 6, 9].
The function enumerate allows us to retrieve not only the values of a list, but the indexes too.

Categories: python Tags: , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: