DISQUS

Hi,
Every property takes 5 lines instead of 1? And you were worried about length???

You could call a separate method from init to do the setting.

- Paddy.

Graphs. When to ship often depends on looking at graphs of bugs/time fixes/time and a lot of guesswork.

- Paddy.

F.Y.I...
http://cbcg.net/2007/04/22/python-up-ruby-down-...

I know I'm supposed to be following the class based approach of your static language examples but I do like the problem itself.

There is more info on the problem here:
http://www.research.att.com/~njas/sequences/A03...

Including a recurrence relation that gives the answer.

It translates into the following Python recursive function:

def T(n, k):
....if n == 1 : return 1
....tmp = (T(n-1, k)+k) % n
....if tmp == 0:
........return n
....else:
........return tmp

....
for n in range(1,8):
....print "\n",n,":",
....for k in range(1, n+1): print T(n, k),


1 : 1
2 : 2 1
3 : 3 3 2
4 : 4 1 1 2
5 : 5 3 4 1 2
6 : 6 5 1 5 1 4
7 : 7 7 4 2 6 3 5
T(40,3)
28



If only I new enough maths to derive the above!

Oh, here's the timings:
Time per iteration for T = 8.75 microseconds
Time per iteration for findlast2 = 93.1200003624 microseconds
Time per iteration for Chain = 221.560001373 microseconds


I haven't had so much fun with a sequence since Ackermanns function, and that was ages ago :-)

- Paddy.

Hi,
You concentrate on the speed of each implementation but speed is no good if it gives wrong results.

How do you know you are getting the right result?

I've walked through my algorithms partial results as you can see and know that I have to return 28. It was straightforward to do in Pythons shell.
On researching the problem further I found this page: http://mathworld.wolfram.com/JosephusProblem.html. Mathworld seems to be good at maths problems and I stuck their 41,3 sized problem into my algorithm with the print statements un-commented and found that my algo gave the same results of the last person being numbered 31 and the second to last being 16.

And on that note I then tried to replicate the triangular table of results numbered (3) on the Wolfram page and came a cropper. I have to withdraw findlast() and make the following modification to findlast2() to handle the special case of choosing every soldier on order:

..def findlast2(chainlength = 40, kill = 3):
......if kill == 1:
..........return [chainlength]
......n, c = 0, range(1,chainlength + 1)
......while len(c)1:
..........#print "n=%3i, (n+1)%%3=%i, c=%s" % (n, (n+1)%3, c)
..........c = [x for n,x in izip(count(n+1),c) if n % kill]
......#print "n=%3i, (n+1)%%3=%i, c=%s" % (n, (n+1)%3, c)
......return c

With the following loops to create the table:

..mx = 10
..print"\nTable showing last positions"
..print "\n%12s" % "kill every:",
..for kill in range(1,mx+1):
......print "%2i" % kill,
..print
..for chain in range(1,mx+1):
......print "\n%12s" % ("chain of %i:" % chain),
......for kill in range(1,chain+1):
..........print "%2i" % findlast2(chain, kill)[0],
..print
..

I then get the following output that tallies with the Wolfram table:

..Table showing last positions
..
.. kill every: 1 2 3 4 5 6 7 8 9 10
..
.. chain of 1: 1
.. chain of 2: 2 1
.. chain of 3: 3 3 2
.. chain of 4: 4 1 1 2
.. chain of 5: 5 3 4 1 2
.. chain of 6: 6 5 1 5 1 4
.. chain of 7: 7 7 4 2 6 3 5
.. chain of 8: 8 1 7 6 3 1 4 4
.. chain of 9: 9 3 1 1 8 7 2 3 8
..chain of 10: 10 5 4 5 3 3 9 1 7 8


A quick modification of the table printing loop to use:
print "%2i" % int(findlast2(chain, kill)[0] == Chain(chain).kill(kill).count+1)
Shows that by allowing for the off by one error, Your Python solution tallies with mine.

What to glean from the above?
* Verification counts.
* Verification and exploration is easy in an interpreted language that gives concise algorithms - it is easier to "throw one away" in the quest for quality.

- Paddy.

Hi again Dhananjay,

I made a slightly different version using izip() and count(). It is no fasterbut might be even easier to show how the python list is used as a circular list.
It also has the two lines needed for optimising with psyco.

..from itertools import izip, count
..import psyco
..psyco.full()
..def findlast2(chainlength = 40, kill = 3):
......n, c = 0, range(1,chainlength + 1)
......while len(c)1:
..........#print "n=%3i, (n+1)%%3=%i, c=%s" % (n, (n+1)%3, c)
..........c = [x for n,x in izip(count(n+1),c) if n % 3]
......#print "n=%3i, (n+1)%%3=%i, c=%s" % (n, (n+1)%3, c)
......return c


Again, if you un-comment the print statements and call findlast2() you get a better insight into the algorithm as it will return:

findlast2()
n= 0, (n+1)%3=1, c=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
n= 40, (n+1)%3=2, c=[1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40]
n= 67, (n+1)%3=2, c=[1, 4, 5, 8, 10, 13, 14, 17, 19, 22, 23, 26, 28, 31, 32, 35, 37, 40]
n= 85, (n+1)%3=2, c=[1, 5, 8, 13, 14, 19, 22, 26, 28, 32, 35, 40]
n= 97, (n+1)%3=2, c=[1, 8, 13, 19, 22, 28, 32, 40]
n=105, (n+1)%3=1, c=[1, 13, 19, 28, 32]
n=110, (n+1)%3=0, c=[1, 13, 28, 32]
n=114, (n+1)%3=1, c=[13, 28]
n=116, (n+1)%3=0, c=[13, 28]
n=118, (n+1)%3=2, c=[28]
[28]

Hi again,
With a simple addition of two lines (OK and the prior installation of the non-standard package called psyco)
The Psyco JIT compiler gave the following faster times on the same box:

Time per iteration for findlast = 32.1899986267 microseconds
Time per iteration for Chain = 109.370000362 microseconds

So, that is an order of magnitude speed up.

- Paddy..

Hi Dhananjay,

I decided to do a more idiomatic solution in Python than your one. As you yourself state, the Python solution closely follows the static language solutions and so it is handicapped.

I came up with this:

..def findlast(chainlength = 40, kill = 3):
....firstinc, c = 1, range(1,chainlength + 1)
....while len(c)1:
........#print firstinc, c
........c, firstinc = [x for n,x in enumerate(c) if (firstinc+n) % 3], \
......................(n+1 +firstinc) %3
....#print firstinc, c
....return c

(Replace initial dots with spaces)

The run time was around four times faster, and its is only SIX lines of code versus the ~33 lines of your static-like classes.

Here is my timings:

Time per iteration for Chain = 386.570000648 microseconds
Time per iteration for findlast = 94.0599989891 microseconds

If you remove the # from the print statements you get printouts to help show what is happeneing.

To create this I used Pythons interactive shell to play around with removing positions in a list, then on how to wrap around and remove more positions from the start of the reduced list. After the experimentation it was straight forward to create the function, (not everything needs to be a class).

I note that your result of Chain(40).kill(3).count == 27 wheras I get findlast() == 28
On looking closer at your lines 18 and 19 I see that you are counting Persons from zero when the problem statement says count from 1. You need to make sure that you don't get an off-by-one error when you report the position as someones life could be at stake :-)

All-in-all I am quite happy with finding a solution with Python, I can concentrate on getting the algorithm right. If I need it faster then I would probably translate the Python algorithm or use the psycho JIT compiler.

- Paddy.

I thought from the input format and the output that a Python list comprehension would be the way I'd solve it and came up with this:

>>> from pprint import pprint as pp
>>> tabular = [["col1","col2","col3"],[["a","b","c"],["e","f","g"]]]
>>> triples = [(row[0], col[1], row[1][col[0]])
for row in enumerate(tabular[1])
for col in enumerate(tabular[0])]
>>> pp(triples)
[(0, 'col1', 'a'),
(0, 'col2', 'b'),
(0, 'col3', 'c'),
(1, 'col1', 'e'),
(1, 'col2', 'f'),
(1, 'col3', 'g')]
>>>


(I added a couple of newlines to the list comprehension to get it into the comment box).

If I were using it then I might wrap it in a function and add a docstring to test/explain it.

- Paddy.

Maybe some of your problem with duck typing as it is called is reflected in your first paragraph:

" You should instead infer what type of object you have by checking for the presence or absence of particular methods".

That isn't quite right. You should just go ahead and use whatever object you have assuming it is the correct object and trust Pythons run-time type checking and your programming team to "do the right thing". It isn't that explicit interface checking isn't needed in Python - its just not the only way, or necessarily the first way to try when programming Python.

- Paddy.

Ref: http://en.wikipedia.org/wiki/Duck_typing