CODEWITHSUNDEEP
pythonpython-2.7loops
Vale
Vale

Reputation: 1033

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())

Upvotes: 4

Views: 93

Answers (3)

jkd
jkd

Reputation: 1045

In addition to all the other answers (telling you to make a copy of the list when iterating), another problem with your code is that you reset the positionCounter to 1 in this line: positionCounter = 1. It should be reset to 0. Here is the complete working code (works so far):

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[:]: #Make copy of iterating list
            positionCounter += 1
            if positionCounter == killPosition:
                print(person)
                people.remove(person)
                positionCounter = 0 #Important! 0 != 1

solveJosephus(raw_input().split())

Upvotes: 1

Loocid
Loocid

Reputation: 6441

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.

Upvotes: 5

Eric Renouf
Eric Renouf

Reputation: 14490

I'm not sure why you sometimes get the right or wrong answer, but I've always run into strange problems if I try to modify a list while iterating over it as your 

for person in people:
    ...
    people.remove(person)

does. Perhaps you can iterate over people.copy() instead so you aren't modifying the same list you're iterating over.

Upvotes: 1

Related Questions