tag:blogger.com,1999:blog-11149365.post8915801975858499726..comments2024-03-23T04:34:59.089+00:00Comments on Go deh!: Comparison of Python Solutions to The Josephus ProblemPaddy3118http://www.blogger.com/profile/06899509753521482267noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-11149365.post-87109574359943255762015-06-12T21:41:24.608+01:002015-06-12T21:41:24.608+01:00Blogger eat the formatting of the original. I have...Blogger eat the formatting of the original. I have not made time to fix this.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-74442009984191518432015-06-12T11:52:15.573+01:002015-06-12T11:52:15.573+01:00In fact your whole program (when all Python errors...In fact your whole program (when all Python errors are fixed) can be written in just two lines:<br /><br />q = list(range(n))<br />while len(q) > 1: del q[::f]<br /><br />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.Vekyhttps://www.blogger.com/profile/12207072339468136950noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-83150857582707563842015-06-12T11:32:03.744+01:002015-06-12T11:32:03.744+01:00Just one of your errors: shouldn't "count...Just one of your errors: shouldn't "count=0" be inside while loop?Vekyhttps://www.blogger.com/profile/12207072339468136950noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-2163977421169038142009-03-03T17:21:00.000+00:002009-03-03T17:21:00.000+00:00how do you check for speeds of the program and thi...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.<BR/><BR/>class Dequeue:<BR/> queue=[]<BR/> def __init__(self,number):<BR/> self.n=number<BR/> for i in range (0,self.n): <BR/> self.queue.append(i)<BR/> def pop(self,pos):<BR/> self.queue[pos]=0<BR/> def check(self):<BR/> if (len(self.queue)==1):<BR/> return 0<BR/> else:<BR/> return 1<BR/> def update(self):<BR/> l=len(self.queue)<BR/> for i in range (0,l):<BR/> if (self.queue[i]==0):<BR/> del self.queue[i]<BR/> def printsurvivour(self):<BR/> if self.queue[0]==0:<BR/> print "no survivour"<BR/> else:<BR/> print "survivour is at postion %s" %(self.queue[0]+1)<BR/><BR/>n=input("enter total number of people")<BR/>f=input("enter frequency of survivour")<BR/>survivour=Dequeue(n)<BR/>count=0<BR/>while (survivour.check()==1):<BR/> <BR/> for i in range (0,n,f):<BR/> survivour.pop(i)<BR/> count=count+1<BR/> n=n-count<BR/> survivour.update()<BR/><BR/>print survivour.printsurvivour()Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11149365.post-68517780127629904252009-02-15T07:52:00.000+00:002009-02-15T07:52:00.000+00:00If you can do the maths you get the much quicker r...If you can do the maths you get the much quicker recurrence relation which leads to:<BR/><BR/><BR/>def josephus_formula(m,n):<BR/> ' from:<BR/>http://www.research.att.com/~njas/sequences/A032434'<BR/> if n == 1: return 1<BR/> return (josephus_formula(m, n-1) + m) %<BR/>n or n<BR/><BR/><BR/>Timings With and without psyco are:<BR/><BR/>Time for josephus_class_ring 0.836919496752<BR/>Time for josephus_modulo 0.0448987231617<BR/>Time for josephus_list_ring 0.0236205998248<BR/>Time for josephus_iter_class 0.0536392195097<BR/>Time for josephus_formula 0.00231426061134<BR/><BR/>Time for josephus_class_ring 6.54270389114<BR/>Time for josephus_modulo 0.148893225256<BR/>Time for josephus_list_ring 0.056629543699<BR/>Time for josephus_iter_class 0.336077909343<BR/>Time for josephus_formula 0.0279940606977<BR/><BR/><BR/>- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-84883718064474960872009-02-15T07:14:00.000+00:002009-02-15T07:14:00.000+00:00There is more here: http://www.cut-the-knot.org/re...There is more here: http://www.cut-the-knot.org/recurrence/flavius.shtml<BR/><BR/>And here: http://www.research.att.com/~njas/sequences/A032434<BR/><BR/>Please note however that the first to die is soldier 1 in the above.<BR/><BR/>- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-11149365.post-55689254464025070462009-02-15T07:05:00.000+00:002009-02-15T07:05:00.000+00:00By moving the class Soldier definition of lines 93...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.<BR/><BR/>The psyco timings then became:<BR/><BR/>Time for josephus_class_ring 0.834278378956<BR/>Time for josephus_modulo 0.0513517779494<BR/>Time for josephus_list_ring 0.0192393167288<BR/>Time for josephus_iter_class 0.0526198162057<BR/><BR/>- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.com