Extended Vanity Search on Rosetta Code

This is the href="http://paddy3118.blogspot.com/2009/02/vanity-search-on-rosetta-code.html">first,
extended so I can see how far up I am in the href="http://www.rosettacode.org/w/index.php?title=Special:PopularPages">league
table of page views.



Since that first blog entry I have created three new pages:' href="http://www.rosettacode.org/wiki/First-class_functions">First-class
functions ', href="http://www.rosettacode.org/wiki/Octal">'Octal'
which was created after I made a large edit to the href="http://www.rosettacode.org/wiki/Hexadecimal">Hex
page, and 'Y
combinator', which is my current ' href="http://paddy3118.blogspot.com/2009/02/y-combinator-in-python.html">stretch
goal'.



Here is the code:

'''
Rosetta Code Vanity search:
 color="#ff00ff">    How many new pages has someone created?
'''

 color="#a020f0">import urllib, re

user = ' color="#ff00ff">Paddy3118'

site = ' color="#ff00ff">http://www.rosettacode.org'
nextpage = site + ' color="#ff00ff">/wiki/Special:Contributions/' + user
nextpage_re = re.compile(
    r' color="#ff00ff"><a href="([^"]+)" title="[^"]+" rel="next">older ')

newpages = []
pagecount = 0
 color="#804040">while nextpage:
    page = urllib.urlopen(nextpage)
    pagecount +=1
    nextpage = ''
     color="#804040">for line  color="#804040">in page:
         color="#804040">if  color="#804040">not nextpage:
             color="#0000ff"># Search for URL to next page of results for download
            nextpage_match = re.search(nextpage_re, line)
             color="#804040">if nextpage_match:
                nextpage = (site + nextpage_match.groups()[0]).replace(' color="#ff00ff">&amp;', ' color="#ff00ff">&')
                 color="#0000ff">#print nextpage
                npline=line
         color="#804040">if ' color="#ff00ff"><span class="newpage">'  color="#804040">in line:
             color="#0000ff"># extract N page name from title
            newpages.append(line.partition(' color="#ff00ff"> title="')[2].partition(' color="#ff00ff">"')[0])
    page.close()

nontalk = [p  color="#804040">for p  color="#804040">in newpages  color="#804040">if  color="#804040">not ' color="#ff00ff">:' in p]

 color="#804040">print " color="#ff00ff">User: %s has created %i new pages of which %i were not Talk: pages, from approx %i edits" % (
    user, len(newpages), len(nontalk), pagecount*50 )
 color="#804040">print " color="#ff00ff">New pages created, in order, are: color="#6a5acd">\n ",
 color="#804040">print " color="#6a5acd">\n  ".join(nontalk[::-1])




nextpage = site + ' color="#ff00ff">/w/index.php?title=Special:PopularPages'
nextpage_re = re.compile(
    r' color="#ff00ff"><a href="([^"]+)" class="mw-nextlink">next ')

data_re = re.compile(
    r' color="#ff00ff">^<li><a href="[^"]+" title="([^"]+)".*</a>.*\(([0-9,]+) views\)' )

title2rankviews = {}
rank = 1
pagecount = 0
 color="#804040">while nextpage:
    page = urllib.urlopen(nextpage)
    pagecount +=1
    nextpage = ''
     color="#804040">for line  color="#804040">in page:
         color="#804040">if  color="#804040">not nextpage:
             color="#0000ff"># Search for URL to next page of results for download
            nextpage_match = re.search(nextpage_re, line)
             color="#804040">if nextpage_match:
                nextpage = (site + nextpage_match.groups()[0]).replace(' color="#ff00ff">&amp;', ' color="#ff00ff">&')
                 color="#0000ff"># print nextpage
                npline=line
        datamatch = re.search(data_re, line)
         color="#804040">if datamatch:
            title, views = datamatch.groups()
            views = int(views.replace(' color="#ff00ff">,', ''))
            title2rankviews[title] = [rank, views]
            rank += 1
    page.close()

 color="#804040">print " color="#6a5acd">\n\n Highest page Ranks for user pages:"
fmt = " color="#ff00ff">  %-4s %-6s %s"  color="#0000ff"># rank, views, title
 color="#804040">print fmt % (' color="#ff00ff">RANK', 'VIEWS', ' color="#ff00ff">TITLE')
highrank = [title2rankviews.get(t,[99999, 0]) + [t]  color="#804040">for t  color="#804040">in nontalk]
highrank.sort()
 color="#804040">for x  color="#804040">in highrank:
     color="#804040">print fmt % tuple(x)

(I promise to restructure it if I go back to it again :-)



Here is the output:

User: Paddy3118 has created 33 new pages of which 20 were not Talk: pages, from approx 300 edits
New pages created, in order, are:
  Spiral
  Monty Hall simulation
  Web Scraping
  Sequence of Non-squares
  Anagrams
  Max Licenses In Use
  One dimensional cellular automata
  Conway's Game of Life
  Data Munging
  Data Munging 2
  Column Aligner
  Probabilistic Choice
  Knapsack Problem
  Yuletide Holiday
  Common number base conversions
  Octal
  Integer literals
  Command Line Interpreter
  First-class functions
  Y combinator


 Highest page Ranks for user pages:
  RANK VIEWS  TITLE
  107  1767   Monty Hall simulation
  127  1409   Conway's Game of Life
  171  1109   Anagrams
  183  1037   Knapsack Problem
  224  812    Max Licenses In Use
  232  789    Web Scraping
  239  717    Spiral
  242  712    One dimensional cellular automata
  289  536    Sequence of Non-squares
  321  442    Yuletide Holiday
  329  422    Column Aligner
  333  418    Probabilistic Choice
  347  389    Data Munging
  351  382    Data Munging 2
  427  175    Integer literals
  448  128    Common number base conversions
  454  110    Command Line Interpreter
  469  61     First-class functions
  480  42     Octal
  634  2      Y combinator

A quick perusal of the results shows that although Conway's Game of
Life was created later, it is high in views; conversely Spiral, my
first page, is down in views.





- Paddy.

Y Combinator in Python

I've been thinking again, and it hurts (its a good hurt though).



Somehow I came across the term 'Y combinator' again and this time
followed it up. It seems that it is a way to create a function
 that adds recursion to functions that don't have recursion in
their definition.



I am still learning from mainly href="http://mvanier.livejournal.com/2897.html">this
explanation 'The Y Combinator (Slight Return)' by Mike Vanier. but I've
managed to follow some things.



Here is a definition of a factorial function in Python:

factorial = lambda n: (1  color="#804040">if n<2  color="#804040">else n*factorial(n-1))

it is easy to see that it is recursive as the lambda expression is
assigned to a name and the name, fibonacci, is used in the lambda
expression.

We can mechanically generate a related function by calling the recursed
call 'f' and by wrapping the expression in an outer lambda expression
of f:

fac = lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))

Notice that fac is not a recursive function as fac is not called inside
its definition. The fac function does not, in itself, compute the
factirial, but wrapping it in the Y combinator function Y produces a
function that computes a factorial, i.e:

Y(fac)(i) == factorial(i)

 

I am not too clear on the whole derivation of Y but Y,is itself a non
recursive function and, in Python is given by:

Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))

here follows my interactive session where I am using it to compute
factorials and fibonacci numbers by adding recursion to non-recursive
functions:

>>> Y = lambda f: ( color="#804040">lambda x: x(x))( color="#804040">lambda y: f( color="#804040">lambda z: y(y)(z)))
>>> fac =  color="#804040">lambda f:  color="#804040">lambda n: (1  color="#804040">if n<2  color="#804040">else n*f(n-1))
>>> [ Y(fac)(i)  color="#804040">for i  color="#804040">in range(10) ]
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
>>> fib =  color="#804040">lambda f:  color="#804040">lambda n: 0  color="#804040">if n == 0  color="#804040">else (1  color="#804040">if n == 1  color="#804040">else f(n-1) + f(n-2))
>>> [ Y(fib)(i)  color="#804040">for i  color="#804040">in range(10) ]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>>

I need to set this investigation aside, then come back to it.



- Paddy

Vanity Search on Rosetta Code

A vanity search is usually when you look for your own name on Google to
show how popular you are (in those terms, no personal slight intended).



I wanted to know how many new pages on Rosetta Code that I had started
so wrote the following script that starts from a users first page of href="http://www.rosettacode.org/wiki/Special:Contributions/Paddy3118">contributions,
and downloads all further pages searching for new page creations, which
are specially marked in the HTML and show as style="font-weight: bold;">N in the table.

The code:

'''
Rosetta Code Vanity search:
 color="#ff00ff">    How many new pages has someone created?
'''

 color="#a020f0">import urllib, re

user = ' color="#ff00ff">Paddy3118'

site = ' color="#ff00ff">http://www.rosettacode.org'
nextpage = site + ' color="#ff00ff">/wiki/Special:Contributions/' + user
nextpage_re = re.compile(
    r' color="#ff00ff"><a href="([^"]+)" title="[^"]+" rel="next">older ')

newpages = []
pagecount = 0
 color="#804040">while nextpage:
    page = urllib.urlopen(nextpage)
    pagecount +=1
    nextpage = ''
     color="#804040">for line  color="#804040">in page:
         color="#804040">if  color="#804040">not nextpage:
             color="#0000ff"># Search for URL to next page of results for download
            nextpage_match = re.search(nextpage_re, line)
             color="#804040">if nextpage_match:
                nextpage = (site + nextpage_match.groups()[0]).replace(' color="#ff00ff">&amp;', ' color="#ff00ff">&')
                 color="#0000ff">#print nextpage
                npline=line
         color="#804040">if ' color="#ff00ff"><span class="newpage">'  color="#804040">in line:
             color="#0000ff"># extract N page name from title
            newpages.append(line.partition(' color="#ff00ff"> title="')[2].partition(' color="#ff00ff">"')[0])
    page.close()

nontalk = [p  color="#804040">for p  color="#804040">in newpages  color="#804040">if  color="#804040">not p.startswith(' color="#ff00ff">Talk:')]

 color="#804040">print " color="#ff00ff">User: %s has created %i new pages of which %i were not Talk: pages, from approx %i edits" % (
    user, len(newpages), len(nontalk), pagecount*50 )
 color="#804040">print " color="#ff00ff">New pages created, in order, are: color="#6a5acd">\n ",
 color="#804040">print " color="#6a5acd">\n  ".join(nontalk[::-1])

What I have created on RC

The output of the program shows all the pages I created , in order of
creation:

User: Paddy3118 has created 31 new pages of which 20 were not Talk: pages, from approx 300 edits
New pages created, in order, are:
   href="http://paddy3118.blogspot.com/2008/08/spiral.html">Spiral
   href="http://paddy3118.blogspot.com/2008/08/monty-hall-problem-simulations.html">Monty Hall simulation
  Web Scraping
  Sequence of Non-squares
  Anagrams
  User talk:Lupus
   href="http://paddy3118.blogspot.com/2008/10/max-licenses-in-use.html">Max Licenses In Use
  One dimensional cellular automata
  Conway's Game of Life
  Village Pump:Home/Foldable output
  Data Munging
  Data Munging 2
  Column Aligner
  Probabilistic Choice
   href="http://paddy3118.blogspot.com/2008/12/knapsack-problem.html">Knapsack Problem
  Yuletide Holiday
  Common number base conversions
  Octal
  Integer literals
  Command Line Interpreter

I have added links to show when I blogged about a task as well as
starting the RC page. I can see that I have a 'User talk:' page that
should also be filtered out.



I was always writing small examples that I thought might be useful
examples for a Python training course. I was looking for a public home
for them and initially thought that, after stumbling across RC, that RC
would be a good home for them. I am only partially right, but I have
found the discipline of writing for RC to be enjoyable in itself, so
continue to contribute.



I quite enjoyed the challenge of creating an RC task beginning with the
letters K and then Y, so they could complete their full alphabet of
 named tasks. Yuletide Holiday was created around xmas 2008
and is really about Y2k errors - but they seem to have stuck with my
name :-)

I need to re-visit Data Munging and add extra clarification to the task
as RC needs a good task description, wheras a lot of data munging tasks
don't. 



If you are interested in language comparison sites then you might want
to take a look at RC too!



- Paddy.

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

Carol Thatchers golliwog remark

Having
lived through "The Thatcher years", when Carol Thatcher's mother was
Prime Minister, I thought then that most of the racists were
 openly members of her Tory party. It is no surprise then to
hear that href="http://www.dailymail.co.uk/news/article-1136005/Chiles-reveals-truth-Carol-Thatchers-golliwog-gaffe.html">Carol
thinks it is OK to call black people Golliwogs when "where
all white here" - nudge-nudge. Together with href="http://news.bbc.co.uk/1/hi/world/africa/4169557.stm">her
brothers antics in Africa, you get a picture of the views
circulating in the Thatcher household during their formative years that
is sickeningly racist.

I guess we have advanced to
the stage that even someone who is the daughter of a Baroness; who's
mother still wields great power in the UK; felt it unwise to make her
comments on-screen, but by witnessing the cries of
'outrage' at her mere dismissal from the BBC. I think British
society can't be complacent on its way to an integrated society.

-
Paddy.

P.S. Big-up Jo Brand for walking out.
P.P.S.
There was a member of href="http://www.comicrelief.com/what_we_do/what_we_fund_and_why">Comic
Relief  in the green room too, yet still Carol
thinks its OK?