Free lunch consists of a group of friends trying to determine who gets free lunch. The way they decide is that they arrange themselves in a circle and start counting the positive natural numbers in order. The person at the most north of the circle starts counting from 1. Anyone who says an even natural number gets removed from the circle. When we reach the last person this wraps around and goes back to the person at the beginning. This continues until there is exactly one person left, and this person gets free lunch in the end.
Devise a Plan:
I'm going to perform a few basic examples to help clear out exactly what happens
Carry out the Plan:
So a few examples to help clear out what happens in different situations, I left the index underneath and used a list because I was preparing it so that I could code it easily later on. The case below, is just a simple example without any complications.
[1, 2, 3, 4]
(0, 1, 2, 3) - Index
[1, 3]
(0, 1) - Index
[1] - Last One = 1
Here there is no complication in reaching the person who gets free lunch since the number of people stays even until you reach the last person. You just continuously remove the person who is at an odd index in python terms.
(0, 1, 2, 3, 4,) - Index
[5, 1, 3]
(0, 1, 2) - Indes
[3, 5]
(0, 1) - Index
[3]- Last One = 3
Here is were it gets a bit more tricky, since the last item is on an even index, (the number of people is odd) and is right after someone who gets removed. For the python code to work that person becomes the technical new "first person" and we start counting from them. That is why the 5 moves to the front and then the 3 gets moved to the front, since the lists are odd.
def remove_odd_index(L):
''' Remove the odd indeces, which corrolate to the "person"
counting the even natural numbers.
# Once the list has a length of 1 return that item, which means once theres only one person left,
# you have the winner.
if len(L) == 1:
return L[0]
# Go through all the odd indices and remove them.
work = L[:]
for i in range(1, len(L), 2):
work.remove(L[i])
# If there is now an odd number of people then the last person because the first
# in the new "set" of people
if len(L) % 2 != 0:
work.insert(0, L[-1])
work = work[:-1]
# Continue calling the function until there is one person left
return remove_eve_ind(work)
Look Back:
I tried doing it with circles and it made it harder to actually see the pattern when dealing with certain numbers of people, such as the pattern of how to deal with even number of people and the pattern that there is when dealing with an odd number of people. It took me a little while to figure out how to insert the last item at the front of the list, and had a lapse in brain power trying to remember that I could just slice the list to remove the last item, but that was just some rustiness in coding. The general concept of the problems I understand when I kept it as a line because it was easier to see that I could just move the last person in an odd numbered list to the front and continued from there.
I also want to thank Mandy from http://mandyxu.blog.com for showing me this problem, it was actually pretty fun to figure it out the code for this.
No comments:
Post a Comment