“Josephus-p‌r‌o‌b‌l‌e‌m” using list in python

Question

I wanted to know if it will be possible to solve the Josepheus problem using list in python.

In simple terms Josephus problem is all about finding a position in a circular arrangement which would be safe if executions were handled out using a skip parameter which is known beforehand.

For eg : given a circular arrangement such as [1,2,3,4,5,6,7] and a skip parameter of 3, the people will be executed in the order as 3,6,2,7,5,1 and position 4 would be the safe.

I have been trying to solve this using list for some time now, but the index positions becomes tricky for me to handle.

 a=[x for x in range(1,11)]
 skip=2
 step=2
 while (len(a)!=1):
   value=a[step-1]
   a.remove(value)
   n=len(a)
   step=step+skip
   large=max(a)
   if step>=n:        
      diff=abs(large-value)
      step=diff%skip
   print a

Updated the question with code snippet, but i don't think my logic is correct.

Answer 1

Quite simply, you can use list.pop(i) to delete each victim (and get his ID) in a loop. Then, we just have to worry about wrapping the indices, which you can do just by taking the skipped index mod the number of remaining prisoners.

So then, the question solution becomes

def josephus(ls, skip):
    skip -= 1 # pop automatically skips the dead guy
    idx = skip
    while len(ls) > 1:
        print(ls.pop(idx)) # kill prisoner at idx
        idx = (idx + skip) % len(ls)
    print('survivor: ', ls[0])

Test output:

>>> josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor:  4

Answer 2

My solution uses a math trick I found online here: https://www.youtube.com/watch?v=uCsD3ZGzMgE It uses the binary way of writing the number of people in the circle and the position where the survivor sits. The result is the same and the code is shorter.

And the code is this:

numar_persoane = int(input("How many people are in the circle?\n")) #here we manually insert the number of people in the circle

x='{0:08b}'.format(int(numar_persoane)) #here we convert to binary

m=list(x) #here we transform it into a list

for i in range(0,len(m)): #here we remove the first '1' and append to the same list

    m.remove('1')

    m.append('1')

    break

w=''.join(m) #here we make it a string again

print("The survivor sits in position",int(w, 2)) #int(w, 2) makes our string a decimal number

Answer 3

In [96]: def josephus(ls, skip):
    ...:     from collections import deque
    ...:     d = deque(ls)
    ...:     while len(d)>1:
    ...:         d.rotate(-skip)
    ...:         print(d.pop())
    ...:     print('survivor:' , d.pop())
    ...:     

In [97]: josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor: 4

If you do not want to calculate the index, you can use the deque data structure.

Answer 4

it looks worse but easier to understand for beginners

def last(n):
    a=[x for x in range(1,n+1)]
    man_with_sword = 1
    print(a)
    while len(a)!=1:   
        if man_with_sword == a[len(a)-2]:  #man_with_sword before last in circle
            killed = a[len(a)-1]
            a.remove(killed)
            man_with_sword=a[0]
        elif man_with_sword==a[len(a)-1]:  #man_with_sword last in circle
            killed = a[0]
            a.remove(killed)
            man_with_sword=a[0]
        else:
            i=0
            while i < (len(a)//2): 
                i=a.index(man_with_sword)
                killed = a[a.index(man_with_sword)+1]
                a.remove(killed)
                #pass the sword 
                man_with_sword=a[i+1] # pass the sword to next ( we killed next)
                print (a, man_with_sword) #show who survived and sword owner
                i+=1
        print (a, man_with_sword,'next circle') #show who survived and sword owner

Answer 5

if you are looking for the final result only, here is a simple solution.

def JosephusProblem(people):
  binary = bin(people)  # Converting to binary
  winner = binary[3:]+binary[2]  # as the output looks like '0b101001'. removing 0b and adding the 1 to the end
  print('The winner is',int(winner,2))  #converting the binary  back to decimal

If you are looking for the math behind this code, go check out this video: Josephus Problem(youTube)

Answer 6

The total number of persons n and a number k, which indicates that k-1 persons are skipped and a kth person is killed in the circle.

def josephus(n, k): 
  if n == 1: 
    return 1
  else: 
    return (josephus(n - 1, k) + k-1) % n + 1

n = 14
k = 2            
print("The chosen place is ", josephus(n, k))

Answer 7

This is my solution to your question:

# simple queue implementation<ADT>
class Queue:
    def __init__(self):
        self.q = []
    def enqueue(self,data):
        self.q.insert(0,data)
    def dequeue(self):
        self.q.pop()
    def sizeQ(self):
        return len(self.q)
    def printQ(self):
        return self.q


lists = ["Josephus","Mark","Gladiator","Coward"]
to_die = 3
Q = Queue()
# inserting element into Q
for i in lists:
    Q.enqueue(i)
# for size > 1 
while Q.sizeP() > 1:
    for j in range(1,3): 
# every third element to be eliminated
         Q.enqueue(Q.dequeue())
    Q.dequeue()
print(Q.printQ())

Answer 8

def Last_Person(n):
    person = [x for x in range(1,n+1)]
    x = 0
    c = 1
    while len(person) > 1:
        if x == len(person) - 1:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[0])
            person.pop(0)
            x = 0
            c = c+1
        elif x == len(person) - 2:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1])
            person.pop(x+1)
            x = 0
            c = c + 1
        else:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1])
            person.pop(x + 1)
            x = x + 1
            c = c + 1
    print("Person", person[x], "is the winner")

Last_Person(50)