Finding the winning number when given a group number and selected number

Question

I'm very new to python and programming so bear with me =]

I'm trying to write a code for a scenario a friend came up with.

Game:

1. Pick a number for an amount of participants in a group.

2. Pick a random number

Line the participates up and then remove the participate in which the "random number" falls on. Then starting from the next person in line, use the same "random number" to remove the next person. This cycles through the group until there is one remaining.

Example would be :

group = 5

number_picked = 3

So, [0,1,2,3,4] would remove(or pop) the 3rd person and look like so [0,1,3,4].

Then STARTING at 3, you would count 3 again and remove person 0 as that is were the next person selected falls in the cycle. Which would look like [1,3,4].

Then it would be [1,3] and finally [3]. So 3 would be the winner.

Here is the code i currently have:

amount_in_group = int(input("How many people in the group? \n"))
number_picked = int(input("select a number: \n"))

group = [i for i in range((amount_in_group))]
print(group)
while group.__len__() != 1:
    if number_picked > group.__len__():
        index_position = number_picked % group.__len__()
        group.pop(index_position -1)
        # print(group)
    elif group.__len__() >= number_picked:
        group.pop(number_picked -1)
        # print(group)
        
## winner is ##
print(group)

I feel like I am close but the issue with my code is every time a number is popped it starts back at index 0 and counts from there. I need it to pop an index and then START from the next position and cycle through the list until 1 is left! Any help would be greatly appreciated!

Answer 1

By looking at wikipedia on Josephus problem you find this simple algorithm

def choose(amount, pick):
    if amount == 1:
        return 0
    return (choose(amount - 1, pick) + pick) % amount

Answer 2

Here's a simple iterative algorithm:

amount_in_group = 5
number_picked = 3

start = 0
group = list(range(amount_in_group))
while len(group) > 1:
    print(group)
    index = (start + number_picked - 1) % len(group)
    group.pop(index)
    start = index % len(group)
print(group)

>>> [0, 1, 2, 3, 4]
>>> [0, 1, 3, 4]
>>> [1, 3, 4]
>>> [1, 3]
>>> [3]

Answer 3

What you need is to keep track of where you finish - you aren't doing that.

amount_in_group = int(input("How many people in the group? \n"))
number_picked = int(input("select a number: \n"))

group = [i for i in range((amount_in_group))]
print(group)
index = 0 
while len(group) != 1:
   index = (index + number_picked) % len(group)
   group.pop(index -1)
   # print(group)
    
## winner is ##
print(group)

Notice how I keep track of the index each time round the loop.

BTW - It is considered to be bad form to call the __len__() method (or any magic mathod) directly, which is why I have changed your code to call len(group).

Answer 4

The problem is that you never advance your position within the group. You need to work in multiples of number_picked, wrapping back to the start whenever you run off the end. Start with something like this:

pos = number_picked
while len(group) > 1:
   group.pop(pos)
   pos += number_picked
   # I leave it to you to adjust pos to be within bounds

That should give you a good push toward a solution.