Skip to content

Instantly share code, notes, and snippets.

Created April 30, 2018 04:04
Show Gist options
  • Save bikemule/233ea718f274f8f56ee2adb5a7e960ba to your computer and use it in GitHub Desktop.
Save bikemule/233ea718f274f8f56ee2adb5a7e960ba to your computer and use it in GitHub Desktop.
Don't know why I wanted to document this in such detail, but here it is.
Some number, N, of people need to pee, and there is some number, M, of urinals
in a row in a men's room. The people always follow a rule for which urinal they
select: The first person goes to one on either far end of the row, and the rest
try to maximize the number of urinals between them and any other person. So the
second person will go on the other far end, the third person in the middle, and
so on. They continue to occupy the urinals until one person would have to go
directly next to another person, at which point that person decides not to go at
What's the minimum number, M, of urinals required to accommodate all the N
people at the same time?
def recursive_min_urinals(n):
A recursive solution to the problem. Python's default max recursion level is
1000, so won't work past that.
The logic is based on the idea that, since there must be at least 1 urinal
between urinators, you must add two each time, which also matches the
visual solution of the problem.
if n <= 1:
return 1
return 2 + recursive_min_urinals(n-1)
def min_urinals(n):
Determine the minimum number of urinals needed to satisfy the number of
urinators as described above.
return (2*n)-1
def print_urinals(urinators):
Visual proof of problem.
return '*'.join(['u' for x in range(urinators)])
if __name__ == '__main__':
# make sure that all of these methods generate same results.
for x in range(1, 1000):
calculated_m = min_urinals(x)
recursive_m = recursive_min_urinals(x)
print_m = len(print_urinals(x))
if calculated_m != recursive_m and calculated_m != print_m:
print("All done!")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment