# 100 Locker Problem Expanded

The locker problem for 100 lockers is simple:

A school has 100 lockers and 100 students. All lockers are closed on the first day of school. As the students enter, the first student, denoted S1, opens every locker. Then the second student, S2, begins with the second locker, denoted L2, and closes every other locker. Student S3 begins with the third locker and changes every third locker (closes it if it was open, and opens it if it was closed). Student S4 begins with locker L4 and changes every fourth locker. Student S5 starts with L5 and changes every fifth locker, and so on, until student S100 changes L100.

Which lockers will remain open?

Now my program in Python uses a trick hidden in this problem which is that all lockers whose numbers have an odd number of divisors will remain open. In other words, lockers whose numbers are perfect squares. This allowed me to expand my program to solve the problem for any $x$ amount of lockers, provided by the user:

# 100 Locker Problem

counter_open = 0
counter_close = 0
open_list = []

def locker(num_lockers):
global counter_open, counter_close
num = 1
while num**2 < num_lockers:
open_list.append(num**2)
num += 1
counter_open = len(open_list)
counter_close = num_lockers - len(open_list)

def run():
global open_list, counter_close, counter_open
open_list = []
counter_open = 0
counter_close = 0
endings = ["st", "nd", "rd", "th"]
try:
user_input = int(raw_input("How many lockers will there be: "))
except ValueError:
else:
locker(user_input)
return_str = "The "
for index in range(0, len(open_list)):
if index == (len(open_list) - 1):
if str(open_list[index])[-1:] == "1":
return_str += ("and " + str(open_list[index]) + endings[0])
elif str(open_list[index])[-1:] == "2":
return_str += ("and " + str(open_list[index]) + endings[1])
elif str(open_list[index])[-1:] == "3":
return_str += ("and " + str(open_list[index]) + endings[2])
else:
return_str += ("and " + str(open_list[index]) + endings[3])
else:
if str(open_list[index])[-1:] == "1":
return_str += (str(open_list[index]) + endings[0] + ", ")
elif str(open_list[index])[-1:] == "2":
return_str += (str(open_list[index]) + endings[1] + ", ")
elif str(open_list[index])[-1:] == "3":
return_str += (str(open_list[index]) + endings[2] + ", ")
else:
return_str += (str(open_list[index]) + endings[3] + ", ")
return_str += " locker(s) will be open."
print return_str

while True:
run()
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"


Yes, I do realize that I am using global in my functions and I have 8 if/elif statements for grammar but accuracy in the result (and PEP 8) is key to me (keep that in mind) . How do I improve the efficiency of the code and/or shorten the code?

Algorithm

The beginning of the mathematical analysis is very nice and well explained. Maybe it would be nice to have it in your code as a comment.

Also, please note that if what you really care about is the number of lockers open (or closed), it is just a matter of computing a square root.

Separation of concerns

The biggest issue in your code is that you have a function doing everything : handling user input, string formatting, updating globals... This makes your code hard to follow and hard to test. A better way to do it would be to have smaller units (functions or sometimes classes and modules) with a single responsability.

By doing so, you could get rid of the globals and write the code like this :

# 100 Locker Problem

def get_open_lockers(num_lockers):
open_list = []
num = 1
while num**2 < num_lockers:
open_list.append(num**2)
num += 1
return open_list

def format_output(nb_lockers, open_list):
endings = ["st", "nd", "rd", "th"]
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
return_str = "The "
for index in range(0, len(open_list)):
if index == (len(open_list) - 1):
if str(open_list[index])[-1:] == "1":
return_str += ("and " + str(open_list[index]) + endings[0])
elif str(open_list[index])[-1:] == "2":
return_str += ("and " + str(open_list[index]) + endings[1])
elif str(open_list[index])[-1:] == "3":
return_str += ("and " + str(open_list[index]) + endings[2])
else:
return_str += ("and " + str(open_list[index]) + endings[3])
else:
if str(open_list[index])[-1:] == "1":
return_str += (str(open_list[index]) + endings[0] + ", ")
elif str(open_list[index])[-1:] == "2":
return_str += (str(open_list[index]) + endings[1] + ", ")
elif str(open_list[index])[-1:] == "3":
return_str += (str(open_list[index]) + endings[2] + ", ")
else:
return_str += (str(open_list[index]) + endings[3] + ", ")
return_str += " locker(s) will be open."
print return_str
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"

while True:
try:
nb_lockers = int(raw_input("How many lockers will there be: "))
except ValueError:
else:
open_list = get_open_lockers(nb_lockers)
format_output(nb_lockers, open_list)


Look like a native

Almost everytime you do range(len(list)), you are not doing things the right way. I highly recommend Ned Batchelder's excellent talk called "Loop like a native".

In your case, the code becomes (l stands for locker which is probably not the best name):

def format_output(nb_lockers, open_list):
endings = ["st", "nd", "rd", "th"]
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
return_str = "The "
for i, l in enumerate(open_list):
if i == (len(open_list) - 1):
if str(l)[-1:] == "1":
return_str += ("and " + str(l) + endings[0])
elif str(l)[-1:] == "2":
return_str += ("and " + str(l) + endings[1])
elif str(l)[-1:] == "3":
return_str += ("and " + str(l) + endings[2])
else:
return_str += ("and " + str(l) + endings[3])
else:
if str(l)[-1:] == "1":
return_str += (str(l) + endings[0] + ", ")
elif str(l)[-1:] == "2":
return_str += (str(l) + endings[1] + ", ")
elif str(l)[-1:] == "3":
return_str += (str(l) + endings[2] + ", ")
else:
return_str += (str(open_list[i]) + endings[3] + ", ")
return_str += " locker(s) will be open."
print return_str
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"


Extra Operations (functions calls and slicing)

You keep converting l to str. Maybe you could it once and for all.

Similarly, you keep accessing string[-1:] : it would be nice to do it only once. By the way, the usual way to get the last elements of the list is just [-1] (no need for colon).

def format_output(nb_lockers, open_list):
endings = ["st", "nd", "rd", "th"]
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
return_str = "The "
for i, l in enumerate(open_list):
s = str(l)
last_dig = s[-1]
if i == (len(open_list) - 1):
if last_dig == "1":
return_str += ("and " + s + endings[0])
elif last_dig == "2":
return_str += ("and " + s + endings[1])
elif last_dig == "3":
return_str += ("and " + s + endings[2])
else:
return_str += ("and " + s + endings[3])
else:
if last_dig == "1":
return_str += (s + endings[0] + ", ")
elif last_dig == "2":
return_str += (s + endings[1] + ", ")
elif last_dig == "3":
return_str += (s + endings[2] + ", ")
else:
return_str += (s + endings[3] + ", ")
return_str += " locker(s) will be open."
print return_str
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"


Don't repeat yourself

Your have similar logic in the then and else blocks in format_output. This could be factorised out. Also, it would be a good idea to take this chance to extract it out in a function on its own.

def int_to_ordinal(n):
endings = ["st", "nd", "rd", "th"]
s = str(n)
last_dig = s[-1]
if last_dig == "1":
return s + endings[0]
elif last_dig == "2":
return s + endings[1]
elif last_dig == "3":
return s + endings[2]
else:
return s + endings[3]

def format_output(nb_lockers, open_list):
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
return_str = "The "
for i, l in enumerate(open_list):
if i == (len(open_list) - 1):
return_str += ("and " + int_to_ordinal(l))
else:
return_str += (int_to_ordinal(l) + ", ")
return_str += " locker(s) will be open."
print return_str
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"


Tiny bug

I've just discovered one bug as I was trying to go further. I imagine it was in the original code but I might be wrong. It happens when there is only one lock open (the first), the formatting gives : "The and 1st locker(s) will be open." which looks a bit weird.

PEP8 and join

There is a style guide for Python code called PEP 8 : it is worth reading (and worth following as much as possible). Your code seems to follow the PEP 8 style for most parts but there is a part you'd be interested in:

For example, do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a += b or a = a + b . This optimization is fragile even in CPython (it only works for some types) and isn't present at all in implementations that don't use refcounting. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.

Even though I can safely assume that your code performance is not that important, the join builtin, on top of making your code faster, can make it clearer. You could write something like:

def format_output(nb_lockers, open_list):
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
print "The " + ", ".join(int_to_ordinal(l) for l in open_list) + " locker(s) will be open."
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"


(I removed the part with the "And" because it seemed buggy anyway).

If main

In Python, it is recommended to put the part of your code that actually does something (instead of merely defining something) behind an if __name__ == "__main__": so that you can easily run your code as a main program but also import it to be able to reuse the functions/classes you've defined.

if __name__ == "__main__":
while True:
try:
nb_lockers = int(raw_input("How many lockers will there be: "))
except ValueError:
else:
open_list = get_open_lockers(nb_lockers)
format_output(nb_lockers, open_list)


Optimisation in get_open_lockers

In get_open_locks, you can easily compute the number of iterations you'll need. Also, you could use a list comprehension to avoid calling append many times.

import math

def get_open_lockers(num_lockers):
if num_lockers <= 0:
return []
sqrt = int(math.sqrt(num_lockers-1))
return [i*i for i in range(1, sqrt+1)]


(It is easy to write tests to ensure that the function returns the same resultats before and after)

Final version of the code

My final code looks like (it can still probably be improved):

import math

def get_open_lockers(num_lockers):
if num_lockers <= 0:
return []
sqrt = int(math.sqrt(num_lockers-1))
return [i*i for i in range(1, sqrt+1)]

def int_to_ordinal(n):
endings = ["st", "nd", "rd", "th"]
s = str(n)
last_dig = s[-1]
if last_dig == "1":
return s + endings[0]
elif last_dig == "2":
return s + endings[1]
elif last_dig == "3":
return s + endings[2]
else:
return s + endings[3]

def format_output(nb_lockers, open_list):
counter_open = len(open_list)
counter_close = nb_lockers - counter_open
print "The " + ", ".join(int_to_ordinal(l) for l in open_list) + " locker(s) will be open."
print "Open Lockers: " + str(counter_open)
print "Closed Locker: " + str(counter_close)
print "----------------------------"

if __name__ == "__main__":
while True:
try:
nb_lockers = int(raw_input("How many lockers will there be: "))
except ValueError:
else:
open_list = get_open_lockers(nb_lockers)
format_output(nb_lockers, open_list)


Avoid alternation by expanding the endings array to cover all 10 endings as follows:

def int_to_ordinal(n):
endings = ["th", "st", "nd", "rd", "th", "th", "th", "th", "th", "th"]
s = str(n)
last_dig = s[-1]
ord = int(last_dig)
return s + endings[ord]


Of course this does not correct the misnaming of the teens where 11, 12 and 13 are returned as "11st", "12nd" and "13rd" respectively whenever they are the last two digits in the argument.

• Or Use return endings.get(str(n)[-1], "th"), by making endings a dictionary and get rid of all th. – Graipher Dec 20 '16 at 9:24