Comparison of Python Solutions to The Josephus Problem

The
Problem

After coming across href="http://danvk.org/josephus.html">this
language comparison I decided to revisit the Josephus problem:
style="font-style: italic;">

"
Flavius Josephus was a roman historian of Jewish
origin. During the
Jewish-Roman wars of the first century AD, he was in a cave with fellow
soldiers,
40 men in all, surrounded by enemy Roman troops. They decided to commit
suicide by standing in a ring and counting off each third man. Each man
so
designated was to commit suicide...Josephus,
not wanting to die, managed to place himself in the position of the
last survivor.

In the general version of the problem, there are n soldiers
numbered from 1
to n and each m-th soldier will be eliminated. The count starts from
the first
soldier. What is the number of the last survivor?
"

Notice
that:

1. The soldiers are numbered from one
   to n.
2. If the number of soldiers, n, is more than m
   then the first soldier to be killed is the m'th 

Why
play with it?

The class based solution was created by Dan
purely to compare languages and worked well for him I guess. i on the
other hand, read his post and immediately started thinking of ways of
using Pythons lists for the task, and one thing lead to another ...

My
ramblings

Preamble

Just conditionally use
Psyco

  2  color="#804040">try:
 color="#804040">  3     import psyco
 color="#804040">  4     psyco.full()
 color="#804040">  5 except ImportError:
 color="#804040">  6     print ' color="#ff00ff">Psyco not installed, the program will just run slower'
 color="#804040">  7 

Dan's Class based solution:

I
 made a slight change to it. I needed a cleaner interface so
created a function of (m,n) that returned the one-based index of the
last soldier to be killed.:

 color="#804040">  8 
 color="#804040">  9 class  color="#008080">Person:
 color="#804040"> 10     '''
 color="#804040"> 11     # From:  href="http://danvk.org/josephus.html">http://danvk.org/josephus.html
 color="#804040"> 12     '''
 color="#804040"> 13     def  color="#008080">__init__(self,pos):
 color="#804040"> 14         self.pos = pos
 color="#804040"> 15         self.alive = 1
 color="#804040"> 16     def  color="#008080">__str__(self):
 color="#804040"> 17          color="#804040">return " color="#ff00ff">Person #%d, %s" % (self.pos, self.alive)
 color="#804040"> 18 
 color="#804040"> 19     # Creates a chain of linked people
 color="#804040"> 20     # Returns the last one in the chain
 color="#804040"> 21     def  color="#008080">createChain(self,n):
 color="#804040"> 22          color="#804040">if n>0:
 color="#804040"> 23             self.succ = Person(self.pos+1)
 color="#804040"> 24              color="#804040">return self.succ.createChain(n-1)
 color="#804040"> 25          color="#804040">else:
 color="#804040"> 26              color="#804040">return self
 color="#804040"> 27 
 color="#804040"> 28     # Kills in a circle, getting every nth living person
 color="#804040"> 29     # When there is only one remaining, the lone survivor is returned
 color="#804040"> 30     def  color="#008080">kill(self,pos,nth,remaining):
 color="#804040"> 31          color="#804040">if self.alive == 0:  color="#804040">return self.succ.kill(pos,nth,remaining)
 color="#804040"> 32          color="#804040">if remaining == 1:  color="#804040">return self
 color="#804040"> 33          color="#804040">if pos == nth:
 color="#804040"> 34             self.alive = 0
 color="#804040"> 35             pos=0
 color="#804040"> 36             remaining-=1
 color="#804040"> 37              color="#0000ff">#print "Killing", self
 color="#804040"> 38          color="#804040">return self.succ.kill(pos+1,nth,remaining)
 color="#804040"> 39 
 color="#804040"> 40 def  color="#008080">josephus_class_ring(m,n):
 color="#804040"> 41     import sys
 color="#804040"> 42 
 color="#804040"> 43     sys.setrecursionlimit(25000)
 color="#804040"> 44 
 color="#804040"> 45     first = Person(1)
 color="#804040"> 46     last = first.createChain(n-1)
 color="#804040"> 47     last.succ = first
 color="#804040"> 48     winner = first.kill(1,m,n)
 color="#804040"> 49     return winner.pos

(Line 37 is also mine)

My
first Python solution:

I wanted to use Python lists and then
use the modulo operator, % on the indexing  so that a list
would wrap-around and become a ring. I got 'cocky' too and decided to
 kill all soldiers to be killed in each pass over the list in
one go by using Pythons list slicing together with del

 color="#804040"> 51 def  color="#008080">josephus_modulo(m,n):
 color="#804040"> 52     ''' color="#ff00ff"> Use list indexing to do multiple deletes per 'round' '''
 color="#804040"> 53     if n == 1:
 color="#804040"> 54          color="#804040">return 1
 color="#804040"> 55     if m == 1:
 color="#804040"> 56          color="#804040">return n
 color="#804040"> 57 
 color="#804040"> 58     soldiers = range(1,n+1)
 color="#804040"> 59     startindex = m-1
 color="#804040"> 60     while soldiers:
 color="#804040"> 61         leng = len(soldiers)
 color="#804040"> 62         killed = soldiers[startindex::m]  color="#804040">or killed
 color="#804040"> 63          color="#804040">del soldiers[startindex::m]
 color="#804040"> 64         startindex = (m - leng%m + startindex) % m
 color="#804040"> 65     return killed[-1]

I
admit, I was stumped over the correct equation necessary for
calculating the startindex for another 'round' at line 64 - it took
some time to get right and prompted the comparison code added to the
end of the file..

I got the above working , then
went to bed.

My second solution:

In the
light of day, I thought my first solution was opaque , and I wanted to
also try a solution that used a list, but just killed soldiers one by
one. I came up with:

 66 
 color="#804040"> 67 def  color="#008080">josephus_list_ring(m,n):
 color="#804040"> 68     ''' color="#ff00ff"> Use list as ring via modulo '''
 color="#804040"> 69     if n == 1:
 color="#804040"> 70          color="#804040">return 1
 color="#804040"> 71     if m == 1:
 color="#804040"> 72          color="#804040">return n
 color="#804040"> 73     soldiers = range(1,n+1)
 color="#804040"> 74     leng = n
 color="#804040"> 75     m1 = index = m-1
 color="#804040"> 76     while leng>1:
 color="#804040"> 77          color="#0000ff">#print "soldiers, leng, index", soldiers, leng, index
 color="#804040"> 78         killed = soldiers.pop(index)
 color="#804040"> 79          color="#0000ff">#print 'killed', killed
 color="#804040"> 80         index += m1
 color="#804040"> 81         leng -= 1
 color="#804040"> 82         index %= leng
 color="#804040"> 83     return soldiers[0]

href="http://www.python.org/doc/current/library/stdtypes.html?highlight=pop#mutable-sequence-types">list.pop
was the natural way to kill each soldier.

I liked
this function. I would find this relatively easy to both explain and
maintain.

A solution using a class based ring of
objects

I know Dan deliberately added recursion to his class
based solution, and it showed, in me hitting the recursion limit when
using some combinations of m and n. I decided to try using class
instaances to create a ring but iterate over the ring to kill soldiers
insteaad of using recursion.

 color="#804040"> 84 
 color="#804040"> 85 def  color="#008080">josephus_iter_class(m,n):
 color="#804040"> 86     ''' color="#ff00ff"> Iterative class based ring solution '''
 color="#804040"> 87 
 color="#804040"> 88     if n == 1:
 color="#804040"> 89          color="#804040">return 1
 color="#804040"> 90     if m == 1:
 color="#804040"> 91          color="#804040">return n
 color="#804040"> 92 
 color="#804040"> 93     class  color="#008080">Soldier(object):
 color="#804040"> 94          color="#804040">def  color="#008080">__init__(self, number):
 color="#804040"> 95             self.number = number
 color="#804040"> 96             self.next = None
 color="#804040"> 97 
 color="#804040"> 98     # Soldiers without position
 color="#804040"> 99     soldiers = [Soldier(j+1)  color="#804040">for j  color="#804040">in xrange(n)]
 color="#804040">100     # link soldiers in a ring
 color="#804040">101     for j  color="#804040">in xrange(n):
 color="#804040">102         soldiers[j].next = soldiers[(j+1) % n]
 color="#804040">103     last, index = soldiers[m-2], soldiers[m-1]
 color="#804040">104     for i  color="#804040">in xrange(n-1):
 color="#804040">105          color="#0000ff"># Kill soldier at index
 color="#804040">106         index = last.next = index.next
 color="#804040">107          color="#0000ff"># advance
 color="#804040">108          color="#804040">for j  color="#804040">in xrange(m-1):
 color="#804040">109             last, index = index, index.next
 color="#804040">110 
 color="#804040">111     return index.number

Notice
that the class Soldier has just enough fields to form a ring and hold
its original position, (number), in the ring. The real heavy lifting is
done in the body of the function.

I liked the above
solution too, but not as much as josephus_list_ring

Timing

Note:
Dan's solution was not created with fast run times as a goal.

I
decided to run some timings on the various solutions:

 color="#804040">112 
 color="#804040">113 
 color="#804040">114 def  color="#008080">times():
 color="#804040">115     ''' color="#ff00ff"> Time the different josephus functions
 color="#804040">116     '''
 color="#804040">117     import timeit
 color="#804040">118 
 color="#804040">119     functions = [josephus_class_ring, josephus_modulo, josephus_list_ring, josephus_iter_class]
 color="#804040">120     for f  color="#804040">in functions:
 color="#804040">121          color="#804040">print ' color="#ff00ff">Time for', f.__name__, timeit.Timer(
 color="#804040">122             ' color="#ff00ff">[%s(m,n) for n in range(1,50) for m in range(1,n-1)]' % f.__name__,
 color="#804040">123             ' color="#ff00ff">from josephus import %s' % f.__name__).timeit(number=1)

The
results were: (without psyco):
style="margin-left: 40px;"> style="font-family: monospace;">Time for josephus_class_ring
6.44339937059
style="font-family: monospace;">Time for josephus_modulo
0.141748741809
style="font-family: monospace;">Time for josephus_list_ring
0.0586138741097
style="font-family: monospace;">Time for josephus_iter_class
0.336112550617