CODEWITHSUNDEEP
pythonalgorithmjosephus
piotrulu
piotrulu

Reputation: 13

Josephus algorithm partial succes

My friend told me about Josephus problem, where you have 41 people sitting in the circle. Person number 1 has a sword, kills person on the right and passes the sword to the next person. This goes on until there is only one person left alive. I came up with this solution in python:

print('''There are n people in the circle. You give the knife to one of 
       them, he stabs person on the right and
       gives the knife to the next person. What will be the number of whoever
       will be left alive?''')

pplList = []
numOfPeople = int(input('How many people are there in the circle?'))


for i in range(1, (numOfPeople + 1)):
    pplList.append(i)
print(pplList)

while len(pplList) > 1:
    for i in pplList:
        if i % 2 == 0:
            del pplList[::i]
    print(f'The number of person which survived is {pplList[0]+1}')
    break

But it only works up to 42 people. What should I do, or how should I change the code so it would work for, for example, 100, 1000 and more people in the circle?

I've looked up Josephus problem and seen different solutions but I'm curious if my answer could be correct after some minor adjustment or should I start from scratch.

Upvotes: 0

Views: 331

Answers (2)

sudheer naidu
sudheer naidu

Reputation: 162

The problem is you are not considering the guy in the end if he is not killed. Example, if there are 9 people, after killing 8, 9 has the sword, but you are just starting with 1, instead of 9 in the next loop. As someone mentioned already, it is not working for smaller numbers also. Actually if you look close, you're killing odd numbers in the very first loop, instead of even numbers. which is very wrong.

You can correct your code as followed

while len(pplList )>1:
    if len(pplList )%2 == 0:
        pplList  = pplList [::2] #omitting every second number
    elif len(pplList )%2 ==1:
        last = pplList [-1] #last one won't be killed
        pplList  = pplList [:-2:2]
        pplList .insert(0,last) # adding the last to the start

There are very effective methods to solve the problem other than this method. check this link to know more

Upvotes: 0

btilly
btilly

Reputation: 46399

I see two serious bugs.

  1. I guarantee that del ppList[::i] does nothing resembling what you hope it does.
  2. When you wrap around the circle, it is important to know if you killed the last person in the list (first in list kills again) or didn't (first person in list dies).

And contrary to your assertion that it works up to 42, it does not work for many smaller numbers. The first that it doesn't work for is 2. (It gives 3 as an answer instead of 1.)

Upvotes: 1

Related Questions