Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is going wrong inside of my loop?

I've been trying to program the Josephus problem and for some reason it is only working in some situations, I'm unsure why. The TL;DR of how it works is this:

You have X group of people in a circle. Every Nth person is going to be killed until only one final person remains. So say for example you have 10[AKA: X] people and you decide to kill every 3rd [AKA: Nth] person it will look like this:

1st round: 1, 2, (3 dies), 4, 5, (6 dies), 7, 8, (9 dies), 10

2nd round: 1, (2 dies because it is a continuous circle), 3, 5, (7 dies), 8, 10

3rd round: (1), 4, 5, (8), 10

4th round: 4, (5), 10

5th round: 4, (10)

And we are finally left with person #4 as the lone survivor.

My program does this perfectly fine. However, when I enter X as 55 and N as 17 I get the incorrect answer of person 27 when it should be person 40. Can anyone tell me where my loop messes up?

Source code:

def solveJosephus(specifics):
    people = [int(x) for x in range(1,int(specifics[0])+1)]
    killPosition = int(specifics[1])
    positionCounter = 0
    sorted = False

    while not sorted:
        if len(people) == 1:
            print(people[0]) # Pyschologically scarred Winner!
            sorted = True
        for person in people:
            positionCounter += 1
            if positionCounter == killPosition:
                print(person)
                people.remove(person)
                positionCounter = 1

solveJosephus(raw_input().split())
like image 203
Vale Avatar asked Mar 16 '23 06:03

Vale


1 Answers

The problem is you are removing people from the list while iterating through it.

What happens is the following:

Say you have X = 5 and N = 2. Your list is [1,2,3,4,5]. You get to index = 1 and person 2 dies. Now your list is [1,3,4,5]. The problem is your index still equals 1 but now that points to person 3. When you go two more places (index = 3), instead of killing person 4, you kill person 5.

like image 119
Loocid Avatar answered Mar 27 '23 18:03

Loocid