patternpythonMinor
100 Locker Problem Expanded
Viewed 0 times
expandedproblem100locker
Problem
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:
print "Please insert an integer"
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 " +
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:
print "Please insert an integer"
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 " +
Solution
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 :
Look like a native
Almost everytime you do
In your case, the code becomes (
Extra Operations (functions calls and slicing)
You keep converting
Similarly, you keep accessing
```
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])
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:
print "Please insert an integer"
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])
Code Snippets
# 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:
print "Please insert an integer"
else:
open_list = get_open_lockers(nb_lockers)
format_output(nb_lockers, 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 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 "----------------------------"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 "----------------------------"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 "----------------------------"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 "----------------------------"Context
StackExchange Code Review Q#150357, answer score: 6
Revisions (0)
No revisions yet.