Mainly Tech projects on Python and Electronic Design Automation.

Saturday, February 14, 2009

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

With psyco enabled I
got:
style="font-family: monospace;">Time for josephus_class_ring
0.851871117698
style="font-family: monospace;">Time for josephus_modulo
0.0548374164873
style="font-family: monospace;">Time for josephus_list_ring
0.0254780984734
style="font-family: monospace;">Time for josephus_iter_class
2.86889059922

Notice how
josephus_iter_class goes slower
with psyco.

The other bits

 color="#804040">124 
color="#804040">125
color="#804040">126
color="#804040">127
color="#804040">128 if __name__ == ' color="#ff00ff">__main__':
color="#804040">129 n = 25 color="#0000ff"># n people in a circle
color="#804040">130 m = 3 color="#0000ff"># kill every mth person
color="#804040">131
color="#804040">132 print " color="#ff00ff">In a circle of %d people, killing number %d" % (n,m)
color="#804040">133
color="#804040">134 print " color="#ff00ff">Winner by josephus_class_ring: ", josephus_class_ring(m,n)
color="#804040">135 print " color="#ff00ff">Winner by josephus_modulo: ", josephus_modulo(m,n)
color="#804040">136 print " color="#ff00ff">Winner by josephus_list_ring: ", josephus_list_ring(m,n)
color="#804040">137 print " color="#ff00ff">Winner by josephus_iter_class: ", josephus_iter_class(m,n)
color="#804040">138
color="#804040">139 #raise Exception('Stop')
color="#804040">140 print
color="#804040">141 times()
color="#804040">142
color="#804040">143 # Equality check
color="#804040">144 for n color="#804040">in range(1,25):
color="#804040">145 color="#804040">for m color="#804040">in range(1,n-1):
color="#804040">146 color="#804040">assert (josephus_class_ring(m,n) == josephus_modulo(m,n)
color="#804040">147 == josephus_list_ring(m,n) == josephus_iter_class(m,n)), " color="#ff00ff">Whoops"
color="#804040">148
Lines 128 to
137 I used most when developing each function, together with copious
print statements.
Modifications to  lines 143 to
148 ensured that each function was giving the same results, (as well as
giving stack errors for the reccursive solution).

END.

style="font-style: italic;">

7 comments:

  1. By moving the class Soldier definition of lines 93 to 97 outside the josephus_iter_class function definition, I allowed psyco to optimise the function.

    The psyco timings then became:

    Time for josephus_class_ring 0.834278378956
    Time for josephus_modulo 0.0513517779494
    Time for josephus_list_ring 0.0192393167288
    Time for josephus_iter_class 0.0526198162057

    - Paddy.

    ReplyDelete
  2. There is more here: http://www.cut-the-knot.org/recurrence/flavius.shtml

    And here: http://www.research.att.com/~njas/sequences/A032434

    Please note however that the first to die is soldier 1 in the above.

    - Paddy.

    ReplyDelete
  3. If you can do the maths you get the much quicker recurrence relation which leads to:


    def josephus_formula(m,n):
        ' from:
    http://www.research.att.com/~njas/sequences/A032434'
        if n == 1: return 1
        return (josephus_formula(m, n-1) + m) %
    n or n


    Timings With and without psyco are:

    Time for josephus_class_ring 0.836919496752
    Time for josephus_modulo 0.0448987231617
    Time for josephus_list_ring 0.0236205998248
    Time for josephus_iter_class 0.0536392195097
    Time for josephus_formula 0.00231426061134

    Time for josephus_class_ring 6.54270389114
    Time for josephus_modulo 0.148893225256
    Time for josephus_list_ring 0.056629543699
    Time for josephus_iter_class 0.336077909343
    Time for josephus_formula 0.0279940606977


    - Paddy.

    ReplyDelete
  4. how do you check for speeds of the program and this is what i wrote this .it's giving an error.if possible debug it.

    class Dequeue:
    queue=[]
    def __init__(self,number):
    self.n=number
    for i in range (0,self.n):
    self.queue.append(i)
    def pop(self,pos):
    self.queue[pos]=0
    def check(self):
    if (len(self.queue)==1):
    return 0
    else:
    return 1
    def update(self):
    l=len(self.queue)
    for i in range (0,l):
    if (self.queue[i]==0):
    del self.queue[i]
    def printsurvivour(self):
    if self.queue[0]==0:
    print "no survivour"
    else:
    print "survivour is at postion %s" %(self.queue[0]+1)

    n=input("enter total number of people")
    f=input("enter frequency of survivour")
    survivour=Dequeue(n)
    count=0
    while (survivour.check()==1):

    for i in range (0,n,f):
    survivour.pop(i)
    count=count+1
    n=n-count
    survivour.update()

    print survivour.printsurvivour()

    ReplyDelete
  5. Just one of your errors: shouldn't "count=0" be inside while loop?

    ReplyDelete
  6. In fact your whole program (when all Python errors are fixed) can be written in just two lines:

    q = list(range(n))
    while len(q) > 1: del q[::f]

    n and f are inputs, q[0] is output. In other words, you don't adjust startindex at all. And that's why your algo, while cute, isn't really useful for solving this problem.

    ReplyDelete
    Replies
    1. Blogger eat the formatting of the original. I have not made time to fix this.

      Delete

About Me

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive