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?

DVClub yah!

I attended the second (as well as the first), meeting of the Bristol chapter of DVClub yesterday.



This is a meeting, organised by and for Verification Engineers.
Held at a local company (my workplace this time around - Infineon
Technologies), it is a lunchtime meeting of approximately 55 engineers
this time and the subject for the day was Formal Verification (of
Hardware).







Once we all were seated, I couldn't help getting a feeling of
'belonging'. It isn't often you get to meet local engineers working in
similar fields to yourself. Mike Bartley, the organiser kept the event
on schedule, and the speakers knew their stuff. A question of
mine, lead to an interesting conversation with Douglas Fisher who is a
verification specialist at Synopsys - it's a rare opportunity when you
get to swap ideas with a developer from an EDA company so I must
thank DVClub and its Bristol members for a well organised gig.

Links to presented papers

Mike Bartley has all the presented papers available on his company's site for the Bristol Branch of the BCS








- Paddy.

word differ

My brother was over from France this new year and he asked me to write him a small script for the first time.



He had a problem in that he had some prose in a foreign language, and a list of words that the students should learn. He wanted stats on what words from the list were actually used in his prose.



I wrote the following small script. Interestingly enough, the bit that needed a bit of research was doing the graphical file opening for Windows - I really am that used to a Unix environment :-)



It is a very simple program but, on reflection, I can remember doing similar work twenty years ago in AWK: finding out what is different between two 'things' and printing the differences in a sorted order. Back then I would have used Suns original awk, keeping the two sets of data in associative arrays, doing the set arithmatic in explicit for loops, and calling out to the Unix sort utility to print sorted output. Such specialized diff'ing tasks have crept up regularly for me, and they are now very easy to do in Python (or Perl); and I have never had to resort to C for even the largest datasets I've encountered.

word_differ.pyw

Here is the program word_differ.pyw:

# -*- coding: cp1252 -*-

'''
  Find the difference in words used in two documents

  Asks for two files which then have their words extracted and compared.

  Most punctuation, and all words of just numbers are dropped.

  (C) 2009 Donald 'Paddy' McCarthy. paddy3118@gmail.com
'''

import Tkinter, tkFileDialog, re, datetime, sys
root = Tkinter.Tk()
root.withdraw()


def wordsinfile(f):
    words = set()
    txt = f.read()
    words = set( w.lower() for w in re.split(r"""[ \t\n\-,;:\.\?@#~=+_!"£$%^&\*\(\)<>|\\\[\]{}`]""", txt)
                 if w and not all( c in '0123456789' for c in w) )
    return words


f1 = tkFileDialog.askopenfile(parent=root,initialdir="/",title='First text file for word diffing')
if not f1: sys.exit()
f2 = tkFileDialog.askopenfile(parent=root,initialdir="/",title='Second text file for word diffing')
if not f2: sys.exit()
f3 = tkFileDialog.asksaveasfile(parent=root,initialdir="/",title='Save output as file (end with .txt to create a windows text file)')
if not f3: sys.exit()

set1 = wordsinfile(f1)
set2 = wordsinfile(f2)

print >>f3, "Output from program word_differ.py (Author Donald McCarthy: (C) 2009)."
print >>f3, "  Generated on: " + datetime.datetime.now().isoformat()

print >>f3, "  First File:  " + f1.name
print >>f3, "  Second File: " + f2.name
print >>f3, "  Output to:   " + f3.name

print >>f3, "\nWords in the first file that are not in the second:"
for w in sorted(set1 - set2):
    print >>f3, " ", w
print >>f3, "\nWords in the second file that are not in the first:"
for w in sorted(set2 - set1):
    print >>f3, " ", w
print >>f3, "\nWords common to both files:"
for w in sorted(set1 & set2):
    print >>f3, " ", w

f1.close(); f2.close(); f3.close()

Example word list: word list.txt

  back
  black
jump  
  bored
  hair
  missile
  lamb
  little
  played
  sent

Example prose: rhyme.txt

Mary had a little lamb
Who's hair was long and black.
She played with it,
Got bored with it
And then she sent it back!

By Paddy McCarthy - 2009-01-04.

Example output: diff.txt

Output from program word_differ.py (Author Donald McCarthy: (C) 2009).
  Generated on: 2009-01-04T07:20:18.890000
  First File:  C:/Documents and Settings/All Users/Documents/Paddys/word_differ/word list.txt
  Second File: C:/Documents and Settings/All Users/Documents/Paddys/word_differ/rhyme.txt
  Output to:   C:/Documents and Settings/All Users/Documents/Paddys/word_differ/diff.txt

Words in the first file that are not in the second:
  jump
  missile

Words in the second file that are not in the first:
  a
  and
  by
  got
  had
  it
  long
  mary
  mccarthy
  paddy
  she
  then
  was
  who's
  with

Words common to both files:
  back
  black
  bored
  hair
  lamb
  little
  played
  sent

Experiences converting a C lex/yacc parser for Verilog to pure Python

href="http://en.wiktionary.org/wiki/back_in_the_day">Back in
the day, simulators only had point delays, so all gate
libraries had buffers on their I/O. Now, we tend to use path, or
pin-to-pin delays in gate level models things have been made more
difficult for me.

My task was to randomly inject
some stuck-at faults in a large gate level Verilog design for
simulation. Individual gates of the design are connected by nets and
although I can force a net  I cannot force a node as all nodes
on a net are affected by a force on the net, and you cannot get at
individual nodes by looking to force a net  inside  a
particular gate model as their are no input buffers.  The
other problem with forcing nets/nodes using interactive commands of the
simulator is that you have to compile the design sub-optimally as all
the nets have to be accessible which stops the compiler/elaborator from
performing certain speed optimizations on what will be an execution
speed critical set of simulations.

Brainstorming
with a colleague we came up with the concept of modifying the netlist
to insert logic to either pass-through or force its out put to either 1
or 0 from an external control.

So off I went to href="http://embedded.eecs.berkeley.edu/Alumni/pinhong/scriptEDA/">ScriptEDA,
(great page - awful backdrop), and installed his href="http://www-cad.eecs.berkeley.edu/%7Epinhong/scriptEDA/pythongnd-0.35.tar.gz">Python
Interface for Gate-level Netlist Engine., which I then tried
on my gate level netlist.. Unfortunately our gate-level netlist failed
to parse because it used concatenations of nets which the parser
couldn't handle. I would need to extend the parser to support
 net concatenations.

Looking at the
source of the parser it was a C program using href="http://en.wikipedia.org/wiki/Flex_lexical_analyser">lex
and yacc
creating C data structures which were then interfaced to Python via a href="http://www.swig.org/">SWIG generated
wrapper. I don't like  to maintain C programs , and I needed
to flex my parsing abilities so decided to spend a short time
researching a pure Python solution.

PLY
The
obvious choice of  Python parsing tool seemed to be PLY as it
stands for Python Lex Yacc, so a download later and poking around in
the install, I came across href="http://code.google.com/p/ply/source/browse/trunk/example/yply/yply.py?r=43">yply.py:
style="margin-left: 40px;">

yply.py

This example implements a program yply.py that converts a UNIX-yacc
specification file into a PLY-compatible program.  To use, simply
run it like this:

   % python yply.py [-nocode] inputfile.y >myparser.py

The output of this program is Python code. In the output,
any C code in the original file is included, but is commented out.
If you use the -nocode option, then all of the C code in the
original file is just discarded.

To use the resulting grammer with PLY, you'll need to edit the
myparser.py file. Within this file, some stub code is included that
can be used to test the construction of the parsing tables. However,
you'll need to do more editing to make a workable parser.

Disclaimer:  This just an example I threw together in an afternoon.
It might have some bugs.  However, it worked when I tried it on
a yacc-specified C++ parser containing 442 rules and 855 parsing
states.