Go deh!

Thursday, August 27, 2009

Saw this, and thought of you...

Here in the UK, it is back-to-school time with many parents buying new school computers for their children. Windows 7 is not released yet, but here is an alternative opinion on the operating system from a competitor:

http://windows7sins.org/#7

Wednesday, August 26, 2009

The Story of the Regexp and the Primes

If you are all sitting comfortably, then I shall begin...

Once upon a time, in a land an internet away, A python programmer was
browsing the web when he StumbledUpon a post with a curious regular
expression purporting to test numbers for primality. On further
investigation, the regexp was attributed in more than one place to
"Abigail" and took the form:

style="font-weight: bold; font-family: monospace;">^1?$|^(11+?)\1+$

Wanting to find out how it worked, the programmer was stumped, as all
the posts mentioning the regexp asked you to visit a page with a
supposedly excellent explanation of its inner workings, but the domain
name was no longer present.

The programmer decided to work it out for himself and came up with the
following...

A prime number is a
positive integer that is only divisible by itself and one. Zero and one
are not prime.

Let's say a number N, greater than one, is not prime. Then
there exists two numbers, S and T, that when multiplied together equal
N. We have:

S x T = N

Lets us further assume
that T is greater than, or equal to S. (They can be swapped if
necessary to make this so). Then a small bit of manipulation gives:

(S x (T-1)) + S = N

(You take one less S in
the multiplication, then you need to add the S back).

Lets swap the terms and write this as equation (a):

style="font-weight: bold;">S + (S x (T-1)) = N style="font-weight: bold;"> when S,T,N are integers greater
than one, and N is style="font-style: italic; font-weight: bold;">not style="font-weight: bold;"> prime

Abigail's regexp relies on representing integers as strings of that
number of ones:

Zero would be
    ''

One would be     '1'

two becomes     '11'

and so on...

The regexp gives a match if the string of ones does not represent a
prime.

To match zero or one occurrences of a 1 we use the first half of the
regexp:

style="font-family: monospace;">^1?$

Where ^anchors the following to a match from the beginning of the
string, ? will match zero or one occurrences of the preceding 1, and
the trailing $ matches the end of the string, i.e. it matches
a string that contains only zero or one 1 characters.

Going back to equation (a), greater than one, is the same as two or
more.

So S will be represented by two or more 1's - we don't know how many,
but we do know that it is two or more. S, in a regexp, becomes
something like:

style="font-family: monospace;">11+

1 followed by one or more 1's. S is less than or equal to T,
which translates to using a less greedy form of the zero-or-one
matcher, which is +? giving a representation of S as:

style="font-family: monospace;">11+?

We want to find S followed by T-1 identical copies of S, so lets form a
group out of what matches S:

style="font-family: monospace;">(11+?)

Then by referring to this group, it is the first group in the regexp so
can be referred to as \1, we can search for extra copies of the group
by:

style="font-family: monospace;">\1+

S and its copies must cover the whole of the number so must start at ^
and finish at $:

style="font-weight: bold; font-family: monospace;">^(11+?)\1+$

Together with the earlier regexp fraction that covers the numbers zero
and one, they can be or'd together to cover all non primes as
the following:

style="font-family: monospace;">^1?$|^(11+?)\1+$

...Not knowing when to quit, the programmer opted to display some of
his Python code that defines a primality tester using the regexp:

>>> import re

>>> def isprime(n):

    return not re.match(r' style="font-weight: bold;">^1?$|^(11+?)\1+$', '1' * n)

>>> [i for i in range(40) if isprime(i)]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

And another function that shows S and T from the regexp match:

>>> def is style="font-weight: bold;">notprime(n):

    notprime = re.match(r'^(1?)$|^(11+?)(\2+)$', '1' * n)

    if notprime:

        if n <=1:

            return (len( notprime.groups()[0]), )

        else:

            S, SxT1 = notprime.groups()[1:]

            s = len(S)

            t = 1 + len(SxT1)//s

            return (s,t)

    else:

        return ()

>>> [(i, isnotprime(i)) for i in range(15)]

[(0, (0,)), (1, (1,)), (2, ()), (3, ()), (4, (2, 2)), (5, ()), (6, (2, 3)), (7, ()), (8, (2, 4)), (9, (3, 3)), (10, (2, 5)), (11, ()), (12, (2, 6)), (13, ()), (14, (2, 7))]

... And so to bed.

THE END.

Saturday, August 08, 2009

Words From Hex Letters

Enter the six hexadecimal letters into an href="http://rosettacode.org/wiki/Anagrams#Python">anagram
solver with a large scrabble-like href="http://www.puzzlers.org/pub/wordlists/unixdict.txt">dictionary
and you can generate a list of sixteen 'English' words that are also
hex numbers. Good for sprinkling around your assembler listings to
spice up the usual DEADBEEF. CAFÉABBÉ anyone? (confess over a coffee).

style="text-align: left; width: 189px; height: 648px; margin-left: 40px;"
border="1" cellpadding="2" cellspacing="2">

WORD
MEANING

ABBE
priest/clergyman

ABED
in bed/ asleep

BABE
infant

BADE
bid, appeal

BEAD
droplet

BEEF
meat from cow. complaint.

CAFE
small restaurant

CEDE
surrender, abdicate

DADA
father, dad

DADE
<None found>

DEAD
"pining for the href="http://en.wikipedia.org/wiki/Fjords" title="Fjords"
class="mw-redirect">fjords", stunned,
snuffed-it.

DEAF
"hard of hearing"

DEED
contract. accomplishment

FACE
boldness. front

FADE
disappear gradually.

FEED
food. give food

P.S. Anyone have a meaning for DADE?

Sunday, August 02, 2009

Facebook User-Clustering Puzzle

I came across the following href="http://www.facebook.com/careers/puzzles.php?puzzle_id=8">puzzle
at facebook. The task is to generate clusters of users based on who
they send emails to, as extracted from their large log file.

They give a strict format for the log file entries of:

style="font-family: monospace;"><date> '\t'
<send email address> '\t' <to email address>

Some lines from the log might look like:

Thu Dec 11 18:17:01 PST 2008    Finley.Cox@xx.com    James.Harrison@xx.com
Thu Dec 11 18:21:01 PST 2008    Alfie.Khan@xx.com    Tyler.Blanchet@xx.com
Thu Dec 11 18:23:01 PST 2008    Harry.White@xx.com   Finley.Ali@xx.com

They then state that a cluster exists if everyone in the group has sent
at least one email to everyone else in the group, so a cluster of users
A B and C, would have had to have sent the following emails at some
time:

from: A to B

from: A to C

from: B to A

from: B to C

from: C to A

from: C to B

You should extract the clusters from the log and report only maximal
clusters, i.e. in the example above, don't report A,C as a cluster if
you are also reporting A,B,C.

Their is also a format for how clusters are to be reported:

Only clusters of three or more people are to be reported

Reports are to be printed to stdout.

A cluster to a line.

Emails in the cluster to appear in sorted order; style="font-style: italic;">separated by the
two characters of a single comma followed by a single space.

The lines of clusters to also be sorted on the characters
appearing in the each cluster line.

An output for some log file might look like:

Aaron.Lewis@xx.com, Callum.Bennett@xx.com, Jayden.Mills@xx.com, Lucas.Lewis@xx.com, Matthew.Kennedy@xx.com
Alfie.Clarke@xx.com, Amy.Russell@xx.com, Connor.King@xx.com, Ethan.Thomas@xx.com, Joshua.Mcdonald@xx.com

The log files are said to be large.

The above is the original problem, re-phrased.

The Reverse Problem

Early on in thinking about how to solve the problem I thought I would
need much more than the ten lines or so of sample log lines
that they gave. I then thought that style="font-style: italic;">generating a log
file would be a good task too and set out to solve that
instead!

I need to:

Generate pseudo-random email addresses

Generate clusters of users

Generate a log from the clusters

And in that order too. When I have emails, I can create
clusters of emails of different sizes, then expand the clusters into a
log file structure, then print the log in the correct format.

The code follows, this description.

Line 9 is a debug remnant.

Although have only run the code in Python 3, I think it
should work in Python 2.6 as well.

Lines 10-13 are because intern is moved to the sys module in Python 3.

Lines 15-40: I needed thousands of names so trawled WP for href="http://en.wikipedia.org/wiki/List_of_most_popular_given_names">first
names and href="http://en.wikipedia.org/wiki/List_of_most_common_surnames">family
names to create their product.

Lines 27 and 41: I intern'd the strings because I could -
It's a possible premature style="text-decoration: line-through;">ejacu
optimization, but hey.

Lines 43-45: I will be building the log without times but
in order, then adding times to the ordered log entries. to do that i
need the time to start, and some possible time increments between log
entries that I will randomly choose between.

Line 48; The size of cluster I generate is a random choice
between the sizes mentioned here.. For example, a cluster size of 2, ( style="font-family: monospace;">[2]*20), will
predominate.

Line 51 controls how many style="font-style: italic;">extra times an
email might be sent between two people.

Line 53: namegen
just pairs every first name with every family name. If you want more,
you could use two first names for example, as well as extending the
name lists. (or hyphenated family names). Anyone for Imogen Ethan
Islam-Singh :-)

Line 60: name2email
changes the name from namegen into an email address string

Lines 64-69: clustergen
generates clustercount clusters of names. It randomly chooses how many
names to put in each cluster using clustersizefreq;, then generates
that many names per cluster. nextname feeds new names are required, and
the sorts ensure the clusters are generated in the correct order for
printing to satisfy the original puzzles output criteria.

Lines 71-74: clusterprint will correctly format and print
the clustergen data structure.

Lines 76-95: logggen.
The largest function

Line 81 creates a number of clusters

Line 83 takes the cluster of users and turns each cluster
in turn into the expanded set of correspondances between every member
of the cluster, in order.

Line 86 randomly duplicates some entries of the log using
repeatmsgfraction.

Line 89 adds some authenticity by randomising the order
of the emails

Lines 91-94 add the time information to the log.

Line 95 returns the cluster info as well as the log.

Lines 97-101 function logprint can correctly format and
print the log data. Note the handling of the PST timezone in line 100.

 1 
 color="#804040"> 2 '''
 color="#804040"> 3  Random Data generator for:
 color="#804040"> 4   href="http://www.facebook.com/careers/puzzles.php?puzzle_id=8">http://www.facebook.com/careers/puzzles.php?puzzle_id=8
 color="#804040"> 5 '''
 color="#804040"> 6 
 color="#804040"> 7 
 color="#804040"> 8 import itertools, random, datetime
 color="#804040"> 9 from pprint  color="#a020f0">import pprint  color="#a020f0">as pp
 color="#804040"> 10 try:  color="#0000ff"># Python 3/2 compatibility
 color="#804040"> 11  from sys  color="#a020f0">import intern
 color="#804040"> 12 except:
 color="#804040"> 13  pass
 color="#804040"> 14 
 color="#804040"> 15 firstname = ''' color="#ff00ff"> 
 color="#804040"> 16  Lola Imogen Jasmine Leah Daniel Isla Millie Lilly Benjamin Evie
 color="#804040"> 17  Finlay Ella Jacob Grace Jayden Freya Summer James Adam Henry
 color="#804040"> 18  Poppy Joshua Charlotte Thomas Noah Maisie Tyler Liam George Mason
 color="#804040"> 19  Matthew Joseph Nathan Stan Scarlett Jessica Samuel Leo William Olivia
 color="#804040"> 20  Ruby Isabella Emma Isabelle Charlie Phoebe Alfie Owen Erin Oscar
 color="#804040"> 21  Cameron Katie Harvey Aaron Ethan Lily Finley Riley Jamie Megan
 color="#804040"> 22  Caitlin Amy Connor Alexander Ben Eva Bethany Brooke Layla Harry
 color="#804040"> 23  Chloe Harrison Lauren Ava Oliver Mia Abigail Ellie Holly Jake
 color="#804040"> 24  Hannah Luke Molly Jack Amelia Dylan Alex Lucas Lucy Ryan
 color="#804040"> 25  Daisy Sophie Sophia Archie Callum Lewis Isabel Logan Max Emily
 color="#804040"> 26  '''.split()
 color="#804040"> 27 firstname = [intern(n)  color="#804040">for n  color="#804040">in firstname]
 color="#804040"> 28 
 color="#804040"> 29 familyname = list(set( ''' color="#ff00ff"> 
 color="#804040"> 30  Wilson Russell Smith Phillips Dixon White Gill Brown Statham Oneill
 color="#804040"> 31  Harris Doyle James Ahmad Roberts Mann Moore Thomas Saunders Barker
 color="#804040"> 32  Bright Allen George Hill Jackson Rose Malley Mills Sheppard Mason
 color="#804040"> 33  Wright Holt Pearce Bull Richards Ward Lopez Mathey King Stone
 color="#804040"> 34  Johnson Baker Dupont Green Davis Blanchet Taylor Dean Donnelly Evans
 color="#804040"> 35  Woods Patel Meacher Simon Clarke Young Ellis Palmer Lynch Alexander
 color="#804040"> 36  Sutton Ahmed Adams Kennedy Davies Walker Austin Fernandez Mustafa Rodriguez
 color="#804040"> 37  Bennett Murray Powell Harrison Campbell Cole Khan Mcdonald Edwards Wood
 color="#804040"> 38  Thompson Singh Williams Power Price Watson Hall Jones Cox Chapman
 color="#804040"> 39  Arnold Reid Garcia Morgan Mitchell Ali Lewis Stubbs Scott Islam
 color="#804040"> 40  '''.split() ))
 color="#804040"> 41 familyname = [intern(n)  color="#804040">for n  color="#804040">in familyname]
 color="#804040"> 42 
 color="#804040"> 43 starttime = datetime.datetime(2008, 12, 11, 17, 53, 1, 0)
 color="#804040"> 44 # Choice of delta times between log entries
 color="#804040"> 45 timedeltafreq = [ datetime.timedelta(0, secs)  color="#804040">for secs  color="#804040">in [60]*3 + [120]*10 + [240]*10 ]
 color="#804040"> 46 
 color="#804040"> 47 # Choice of cluster sizes
 color="#804040"> 48 clustersizefreq = [2]*20 + [3]*8 + [4]*3 + [5]*2 + [6]*1 +[7]*1 + [8]*1
 color="#804040"> 49 
 color="#804040"> 50 # Many messages between the same two people?
 color="#804040"> 51 repeatmsgfraction = 2.0  color="#0000ff"># Extra 200%
 color="#804040"> 52 
 color="#804040"> 53 def  color="#008080">namegen():
 color="#804040"> 54  'Generates (first, family) name tuples'
 color="#804040"> 55  names = list(itertools.product(firstname, familyname))
 color="#804040"> 56  random.shuffle(names)
 color="#804040"> 57  for name  color="#804040">in names:
 color="#804040"> 58  yield name
 color="#804040"> 59 
 color="#804040"> 60 def  color="#008080">name2email(name):
 color="#804040"> 61  'format (first, family) name as email address'
 color="#804040"> 62  return ' color="#ff00ff">%s.%s@xx.com' % name
 color="#804040"> 63 
 color="#804040"> 64 def  color="#008080">clustergen(clustercount, clustersizefreq=clustersizefreq,
 color="#804040"> 65  firstname=firstname, familyname=familyname):
 color="#804040"> 66  'Generate clustercount clusters of unique users'
 color="#804040"> 67  nextname = namegen().__next__
 color="#804040"> 68  return sorted( sorted(nextname()  color="#804040">for i  color="#804040">in range(random.choice(clustersizefreq)))
 color="#804040"> 69  for j  color="#804040">in range(clustercount) )
 color="#804040"> 70 
 color="#804040"> 71 def  color="#008080">clusterprint(clusters):
 color="#804040"> 72  'Print already sorted clusters in output format'
 color="#804040"> 73  for cluster  color="#804040">in clusters:
 color="#804040"> 74  print ( ' color="#ff00ff">, '.join(name2email(n)  color="#804040">for n  color="#804040">in cluster) )
 color="#804040"> 75 
 color="#804040"> 76 def  color="#008080">loggen(clustercount, clustersizefreq=clustersizefreq,
 color="#804040"> 77  firstname=firstname, familyname=familyname,
 color="#804040"> 78  starttime=starttime, timedeltafreq=timedeltafreq,
 color="#804040"> 79  repeatmsgfraction=repeatmsgfraction):
 color="#804040"> 80  'Generate a log of clustercount clusters of unique users'
 color="#804040"> 81  clusters = clustergen(clustercount)
 color="#804040"> 82  # clustered emails
 color="#804040"> 83  log = sum([ list(itertools.permutations(cluster, 2))  color="#804040">for cluster  color="#804040">in clusters ],
 color="#804040"> 84  [])
 color="#804040"> 85  # repeats
 color="#804040"> 86  for i  color="#804040">in range(int(repeatmsgfraction*len(log))):
 color="#804040"> 87  log.append(random.choice(log))
 color="#804040"> 88  # dispersed emails
 color="#804040"> 89  random.shuffle(log)
 color="#804040"> 90  # log times for emails
 color="#804040"> 91  logtime = starttime
 color="#804040"> 92  for n, (send, to)  color="#804040">in enumerate(log):
 color="#804040"> 93  log[n] = (logtime, send, to)
 color="#804040"> 94  logtime += random.choice(timedeltafreq)
 color="#804040"> 95  return clusters, log
 color="#804040"> 96 
 color="#804040"> 97 def  color="#008080">logprint(log):
 color="#804040"> 98  'Print log in input format'
 color="#804040"> 99  for logtime, send, to  color="#804040">in log:
 color="#804040">100  print (' color="#ff00ff">%s\t color="#ff00ff">%s\t color="#ff00ff">%s' % (logtime.strftime(" color="#ff00ff">%a %b %d %H:%M:%S PST %Y")
 color="#804040">101  , name2email(send), name2email(to)))
 color="#804040">102

The Program in use

Switching to the command
line shell, I generate a log and its clustering and print the results.
Because of the way the log is generated from the clustering, the
clustering of the log should be as stated.

style="font-family: monospace;">>>> style="font-weight: bold;">clusters, log = loggen(3);
clusterprint(clusters); print(); logprint(log); print(); len(log) style="font-family: monospace;">
Alfie.Khan@xx.com,
Lily.Rose@xx.com, Tyler.Blanchet@xx.com style="font-family: monospace;">
Finley.Ali@xx.com,
Harry.White@xx.com

Finley.Cox@xx.com,
James.Harrison@xx.com

Thu Dec 11 17:53:01
PST 2008
Finley.Cox@xx.com    James.Harrison@xx.com style="font-family: monospace;">
Thu Dec 11 17:55:01
PST 2008
Lily.Rose@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 17:59:01
PST 2008
Finley.Cox@xx.com    James.Harrison@xx.com style="font-family: monospace;">
Thu Dec 11 18:03:01
PST 2008
Finley.Ali@xx.com    Harry.White@xx.com style="font-family: monospace;">
Thu Dec 11 18:07:01
PST 2008
Tyler.Blanchet@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 18:09:01
PST 2008
Tyler.Blanchet@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 18:13:01
PST 2008
Alfie.Khan@xx.com    Lily.Rose@xx.com style="font-family: monospace;">
Thu Dec 11 18:17:01
PST 2008
Finley.Cox@xx.com    James.Harrison@xx.com style="font-family: monospace;">
Thu Dec 11 18:21:01
PST 2008
Alfie.Khan@xx.com    Tyler.Blanchet@xx.com style="font-family: monospace;">
Thu Dec 11 18:23:01
PST 2008
Harry.White@xx.com    Finley.Ali@xx.com style="font-family: monospace;">
Thu Dec 11 18:27:01
PST 2008
Harry.White@xx.com    Finley.Ali@xx.com style="font-family: monospace;">
Thu Dec 11 18:29:01
PST 2008
James.Harrison@xx.com    Finley.Cox@xx.com style="font-family: monospace;">
Thu Dec 11 18:33:01
PST 2008
Alfie.Khan@xx.com    Tyler.Blanchet@xx.com style="font-family: monospace;">
Thu Dec 11 18:37:01
PST 2008
Alfie.Khan@xx.com    Lily.Rose@xx.com style="font-family: monospace;">
Thu Dec 11 18:39:01
PST 2008
James.Harrison@xx.com    Finley.Cox@xx.com style="font-family: monospace;">
Thu Dec 11 18:43:01
PST 2008
Tyler.Blanchet@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 18:45:01
PST 2008
Alfie.Khan@xx.com    Tyler.Blanchet@xx.com style="font-family: monospace;">
Thu Dec 11 18:47:01
PST 2008
Harry.White@xx.com    Finley.Ali@xx.com style="font-family: monospace;">
Thu Dec 11 18:49:01
PST 2008
Harry.White@xx.com    Finley.Ali@xx.com style="font-family: monospace;">
Thu Dec 11 18:53:01
PST 2008
James.Harrison@xx.com    Finley.Cox@xx.com style="font-family: monospace;">
Thu Dec 11 18:57:01
PST 2008
Finley.Cox@xx.com    James.Harrison@xx.com style="font-family: monospace;">
Thu Dec 11 18:59:01
PST 2008
Harry.White@xx.com    Finley.Ali@xx.com style="font-family: monospace;">
Thu Dec 11 19:03:01
PST 2008
Lily.Rose@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 19:04:01
PST 2008
Tyler.Blanchet@xx.com    Lily.Rose@xx.com style="font-family: monospace;">
Thu Dec 11 19:06:01
PST 2008
James.Harrison@xx.com    Finley.Cox@xx.com style="font-family: monospace;">
Thu Dec 11 19:10:01
PST 2008
Tyler.Blanchet@xx.com    Alfie.Khan@xx.com style="font-family: monospace;">
Thu Dec 11 19:12:01
PST 2008
Lily.Rose@xx.com    Tyler.Blanchet@xx.com style="font-family: monospace;">
Thu Dec 11 19:16:01
PST 2008
Finley.Cox@xx.com    James.Harrison@xx.com style="font-family: monospace;">
Thu Dec 11 19:20:01
PST 2008
Tyler.Blanchet@xx.com    Lily.Rose@xx.com style="font-family: monospace;">
Thu Dec 11 19:22:01
PST 2008
Alfie.Khan@xx.com    Tyler.Blanchet@xx.com style="font-family: monospace;">

30

To Do

The cluster info for the puzzle should, of course, have the
clusters of size two filtered out

I haave a solution to the original puzzle, but: " style="font-style: italic;" title="Insert schoolboy excuse here">Blue
Martians forcibly wiped it from my brain" :-)

- Paddy.

Tuesday, July 28, 2009

The case of the disappearing over-bar

Rosetta-code has a task
which asks you to reverse a Unicode string
correctly. I had glanced at the Python
solution and thought nothing of
it until someone did something similar in the R language and stated
that it may be incorrect for the given pattern which includes an
over-bar (my description) over the f in "as⃝df̅" (See the
orginal article for the true Unicode string).

I cut-n-pasted the Python solution and the test string into Python 3.1
idle and decided to test it:

Python 3.1 (r31:73574, Jun 26 2009, 20:21:35) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> # I cut and paste the following string with an over-bar on the f
>>> x = input()
as⃝df̅
>>> # Just showing x gives the over-bar on the f
>>> x
'asâƒdfÌ…'
>>> # Print it and it is fine.
>>> print(x)
asâƒdfÌ…
>>> # Reverse x though, and the over-bar movesover the quote!
>>> x[::-1]
'Ì…fdâƒsa'
>>> # print the reversed x and it disappears altogether!
>>> print(x[::-1])
Ì…fdâƒsa
>>>

|NowCut and paste the unicode characters from firefox for the input
statement, and make sure that:

>>> ['%x' % ord(char) for char in x]
['61', '73', '20dd', '64', '66', '305']

As the unicode might otherwise be lost in my editing to try and present
it to you above.

A bit of scary reading introduced me to
Unicode character classes. It seems that Unicode characters are
sometimes composed, and that if I know what character gets composed
with another, (always the last non-composed character to the left),
then you should be able to form composed groups of characters and then
reverse them.

The WP article gave me the vocabulary, so a quick search in Pythons
library gave me the unicodedata
module which has the name
function. I am not sure if this will work in every case, but from the
WP article and this experimentation:

>>> [(c,'%s' % unicodedata.name(c,0xfffff)) for c in x]
[('a', 'LATIN SMALL LETTER A'), ('s', 'LATIN SMALL LETTER S'), ('⃝', 'COMBINING ENCLOSING CIRCLE'), ('d', 'LATIN SMALL LETTER D'), ('f', 'LATIN SMALL LETTER F'), ('̅', 'COMBINING OVERLINE')]

I think I can group by the presence of the word COMBINING in the name
of a character and so produced the following reversal function:

'''
  Reverse a Unicode string with proper handling of combining characters
'''

import unicodedata

def ureverse(ustring):
    '''
    Reverse a string including unicode combining characters

    Example:
        >>> ucode = ''.join( chr(int(n, 16))
                             for n in ['61', '73', '20dd', '64', '66', '305'] )
        >>> ucoderev = ureverse(ucode)
        >>> ['%x' % ord(char) for char in ucoderev]
        ['66', '305', '64', '73', '20dd', '61']
        >>> 
    '''
    groupedchars = []
    uchar = list(ustring)
    while uchar:
        if 'COMBINING' in unicodedata.name(uchar[0], ''):
            groupedchars[-1] += uchar.pop(0)
        else:
            groupedchars.append(uchar.pop(0))
    # Grouped reversal
    groupedchars = groupedchars[::-1]

    return ''.join(groupedchars)

if __name__ == '__main__':
    ucode = ''.join( chr(int(n, 16))
                     for n in ['61', '73', '20dd', '64', '66', '305'] )
    ucoderev = ureverse(ucode)
    print (ucode)
    print (ucoderev)

It works for the given example text (Try running it to see the output -
I've given up trying to work out what characters you might see).

Gosh, an attractive Unicode issue! Whatever next.

Wednesday, June 24, 2009

Type based API's and Duck Typing Shocker!!

The Voidspace tech blog has href="http://www.voidspace.org.uk/python/articles/duck_typing.shtml">an
article in which the author, Michael Ford, blames duck-typing
for a problem in trying to find the type of an argument.

After a very good explanation of how duck typing in Python
comes about Michael starts his section on the problem by
stating the principal of duck typing as:

"The
principle of duck typing says that you shouldn't care what type of
object you have - just whether or not you can do the required action
with your object."

All well and good but then later on Michael states:

"If we
want our code to treat different types of object differently then
the approach in example two fails. This isn't contrived - this is
exactly the situation we found ourselves in with ConfigObj."

So, type is important in his case. Fine. style="font-weight: bold;">But why lay the blame at duck
typings door ?

His example interface relies on knowing what constitutes a "listy"
object, or a "stringy" object, etc, in Python 2.x, which he notes is a
pain, but I think the cause of the problem w.r.t. duck typing is
choosing an API that relies on an ill-defined idea of what constitutes
close enough to a dict/list/string or whatever, then not having the
language provide an easy solution.

Abstract
base classes are an attempt to help out in such cases that is
new in Python 2.6 and 3.0, but if you want to link functionality with
type then you can't expect to get duck typing too.

Where Duck Typing Does Not fit.

If a function has an expensive or non-reversible operation that depends
on an attribute of an argument, then it may be wise to check
all arguments for compatibility up-front; but even then, whats wrong
with reading the code? Defensive programming can creep up on
you...

Monday, June 22, 2009

Killer Script

Following on from my href="http://paddy3118.blogspot.com/2009/03/batch-process-runner-in-bash-shell.html"
target="_blank">Batch process runner script, I got
thinking that a nice capability would be to have a maximum runtime
limit for the jobs.

My first thought was to create an href="http://unixhelp.ed.ac.uk/CGI/man-cgi?at" target="_blank">at
command set to execute the reuired time after the start of each job,
one for each job, that would kill the job.

Nah.

Discussions with a friend lead to consideration of using href="http://docs.sun.com/app/docs/doc/816-5165/ulimit-1?l=en&a=view&q=ulimit"
target="_blank">ulimit in the script to limit the
run time, but unfortunately on the Unix box I was testing on, ulimit
could only limit the maximum CPU time, not run time. If the job was
stuck in a non-busy wait then it would not be auto-killed.

I decided to try creating a script to run a time eating processing task
that created a background kill task so the script would be self
killing.

The script

Line 1:    The KILLAFTER environment
variable will kill the script after 3 seconds

Line 5:    Store the process ID for the
'bash -c' script for killing later

Line 8:    This is the slleping background
sub-process that wakes after KILLAFTER seconds and kills the script.

Line 9:    But if the normal script commands
finish, store the sub-process PID so it can be cleanly killed itself.

Line 12: Some dummy command that counts up every second.

Line 13:   And save its exit status so it can be
restored after removing the background kill process.

Line 16:   Terminate the background kill process so
we are not left waiting.

Line 18:   Exit with the saved exit status.

Line 19:   Prints the exit status of the whole 'bash
-c' script

Lines 20-24 show the output of the first run. Notice how although the
for loop in line 12 is set to count to 5, the count gets killed after
printing 3, i.e. the three seconds of $KILLAFTER.

Lines 27 onwards show a second run where KILLAFTER is set to more time
than is used by the for loop. Notice how the script prints the full
count up to 5, and has a return status of zero.

 1 bash-paddy:  style="font-weight: bold;">env  style="font-weight: bold;" color="#008080">KILLAFTER style="font-weight: bold;">= style="font-weight: bold;" color="#ff00ff">3 style="font-weight: bold;"> bash  style="font-weight: bold;" color="#6a5acd">-c style="font-weight: bold;"> '
 color="#804040"> 2 # New bash script shell environment
 color="#804040"> 3 
 color="#804040"> 4 # Its PID
 color="#804040"> 5 export  color="#008080">thisshellpid color="#804040">= color="#a020f0">$$
 color="#804040"> 6 
 color="#804040"> 7 # Sleeping killer will blast this script after given time
 color="#804040"> 8 (sleep  color="#a020f0">$KILLAFTER  color="#804040">;  color="#804040">kill  color="#ff00ff">-9 $thisshellpid color="#804040">) color="#804040">&
 color="#804040"> 9 killerpid= color="#a020f0">$!
 color="#804040">10 
 color="#804040">11 # Any time consuming command
 color="#804040">12 for y  color="#804040">in  color="#ff00ff">1 2  color="#ff00ff">3 4  color="#ff00ff">5;  color="#804040">do sleep  color="#ff00ff">1;  color="#804040">echo color="#ff00ff"> $y color="#804040">;  color="#804040">done
 color="#804040">13 trueexitstatus= color="#a020f0">$?
 color="#804040">14 
 color="#804040">15 # If time consuming command worked OK then...
 color="#804040">16 kill  color="#ff00ff">-9 $killerpid
 color="#804040">17 
 color="#804040">18 exit  color="#a020f0">$trueexitstatus
 color="#804040">19  style="font-weight: bold;">'  style="font-weight: bold;" color="#804040">; style="font-weight: bold;">  style="font-weight: bold;" color="#804040">echo style="font-weight: bold;" color="#ff00ff"> Returned status:  style="font-weight: bold;" color="#a020f0">$?
 color="#804040">20 1
 color="#804040">21 2
 color="#804040">22 3
 color="#804040">23 Killed
 color="#804040">24 Returned status:  color="#ff00ff">137
 color="#804040">25 bash-paddy:
 color="#804040">26 bash-paddy:
 color="#804040">27 bash-paddy:  style="font-weight: bold;">env  style="font-weight: bold;" color="#008080">KILLAFTER style="font-weight: bold;">= style="font-weight: bold;" color="#ff00ff">10 style="font-weight: bold;"> bash  style="font-weight: bold;" color="#6a5acd">-c style="font-weight: bold;"> '
 color="#804040">28 # New bash script shell environment
 color="#804040">29 
 color="#804040">30 # Its PID
 color="#804040">31 export  color="#008080">thisshellpid color="#804040">= color="#a020f0">$$
 color="#804040">32 
 color="#804040">33 # Sleeping killer will blast this script after given time
 color="#804040">34 (sleep  color="#a020f0">$KILLAFTER  color="#804040">;  color="#804040">kill  color="#ff00ff">-9 $thisshellpid color="#804040">) color="#804040">&
 color="#804040">35 killerpid= color="#a020f0">$!
 color="#804040">36 
 color="#804040">37 # Any time consuming command
 color="#804040">38 for y  color="#804040">in  color="#ff00ff">1 2  color="#ff00ff">3 4  color="#ff00ff">5;  color="#804040">do sleep  color="#ff00ff">1;  color="#804040">echo color="#ff00ff"> $y color="#804040">;  color="#804040">done
 color="#804040">39 trueexitstatus= color="#a020f0">$?
 color="#804040">40 
 color="#804040">41 # If time consuming command worked OK then...
 color="#804040">42 kill  color="#ff00ff">-9 $killerpid
 color="#804040">43 
 color="#804040">44 exit  color="#a020f0">$trueexitstatus
 color="#804040">45  style="font-weight: bold;">'  style="font-weight: bold;" color="#804040">; style="font-weight: bold;">  style="font-weight: bold;" color="#804040">echo style="font-weight: bold;" color="#ff00ff"> Returned status:  style="font-weight: bold;" color="#a020f0">$?
 color="#804040">46 1
 color="#804040">47 2
 color="#804040">48 3
 color="#804040">49 4
 color="#804040">50 5
 color="#804040">51 Returned status:  color="#ff00ff">0
 color="#804040">52 bash-paddy:
 color="#804040">53

Monday, June 15, 2009

XKCD Simpler Knapsack Solution

After reading the feedback on my href="http://paddy3118.blogspot.com/2009/06/xkcd-knapsack-solution.html"
target="_blank">earlier solution to the XKCD knapsack problem,
I decided to re-write it without itertools.product and with integer
maths.

I came up with a solution that used explicit while loops that worked,
and used much less traversals through nested loops, but I then boiled
that down to a recursive solution which retains the ability to easily
modify the number of dishes , whilst restricting the number of times
through the loops to the bare minimum.

In the previous solution I worked out the maximum number of each dish
that cost less than or equal to the amount and looped from zero to that
many times. In the solution below the while loops cut off looping on
any particular dish when adding another would put the cost over the
maximum.

And now the code:

items = ( ('MIXED FRUIT',   2.15),
          (' color="#ff00ff">FRENCH FRIES',  2.75),
          (' color="#ff00ff">SIDE SALAD',    3.35),
          (' color="#ff00ff">HOT WINGS',     3.55),
          (' color="#ff00ff">MOZZ STICKS',   4.20),
          (' color="#ff00ff">SAMPLER PLATE', 5.80),
          (' color="#ff00ff">BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
 color="#0000ff"># All calcs in integer cents.
prices = [int(price*100)  color="#804040">for price  color="#804040">in prices]
ecost = int(exactcost*100)

 color="#0000ff"># counts of each dish
dishcounts = [0]*len(prices)
 color="#0000ff">possibleorders = []
cost = 0
maxnesting = len(dishcounts)

 color="#804040">def  color="#008080">enumeratedish(nest, cost, possibleorders):
     color="#804040">global dishcounts, prices, ecost, maxnesting
     color="#804040">while cost <= ecost:
         color="#804040">if nest+1 < maxnesting:
            enumeratedish(nest+1, cost, possibleorders)
         color="#804040">elif cost == ecost:
            possibleorders.append(dishcounts[:])
             color="#804040">break
        dishcounts[nest] += 1
        cost += prices[nest]
         color="#0000ff">#print (dishcounts)
    cost -= prices[nest] * dishcounts[nest]
    dishcounts[nest] = 0

enumeratedish(0, 0, possibleorders)
 color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
 color="#804040">for order  color="#804040">in possibleorders:
    order = zip(dishes, order)
     color="#804040">print( ' color="#ff00ff">  ',
           ' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount  color="#804040">for dishcount  color="#804040">in order  color="#804040">if dishcount[1]))

feel free to compare the two solutions.

Saturday, June 13, 2009

XKCD Knapsack Solution

A brute force solution to the following comic from href="http://xkcd.com/287/">XKCD:

title="General solutions get you a 50% tip."
src="http://imgs.xkcd.com/comics/np_complete.png">

Assuming the one sandwich represents the end of the menu, I used an
exhaustive search algorithm. Things to note are the use of zip(*table)
to transpose the items and itertools.product instead of nested for
loops.

'''
from:  href="http://xkcd.com/287/">http://xkcd.com/287/
'''

 color="#a020f0">from itertools  color="#a020f0">import product

items = ( (' color="#ff00ff">MIXED FRUIT',   2.15),
          (' color="#ff00ff">FRENCH FRIES',  2.75),
          (' color="#ff00ff">SIDE SALAD',    3.35),
          (' color="#ff00ff">HOT WINGS',     3.55),
          (' color="#ff00ff">MOZZ STICKS',   4.20),
          (' color="#ff00ff">SAMPLER PLATE', 5.80),
          (' color="#ff00ff">BARBEQUE',      6.55) )

exactcost = 15.05

dishes, prices = zip(*items)
rangeofdishes = [tuple(range(1+int( (exactcost+0.005)/price )))  color="#804040">for price  color="#804040">in prices]

possibleorders = [tuple(zip(dishes, numbers))
                   color="#804040">for numbers  color="#804040">in product(*rangeofdishes)
                   color="#804040">if int(exactcost*100)
                       == int(100* sum(num*price
                                        color="#804040">for num,price  color="#804040">in zip(numbers, prices)))
                  ]
 color="#804040">print(' color="#6a5acd">\nALL POSSIBLE CHOICES OF MENU ITEMS THAT COST %.2f, ONE PER LINE' % exactcost)
 color="#804040">for order  color="#804040">in possibleorders:
     color="#804040">print( ' color="#ff00ff">  ',
           ' color="#ff00ff">, '.join(' color="#ff00ff">%s: %i' % dishcount  color="#804040">for dishcount  color="#804040">in order  color="#804040">if dishcount[1]))

The answers I get are:

style="font-family: monospace;">ALL POSSIBLE CHOICES OF MENU
ITEMS THAT COST 15.05, ONE PER LINE style="font-family: monospace;">

MIXED FRUIT: 1, HOT WINGS: 2, SAMPLER PLATE: 1 style="font-family: monospace;">

MIXED FRUIT: 2, MOZZ STICKS: 1, BARBEQUE: 1


MIXED FRUIT: 7

(I'd go with the hot wings).

Sunday, May 31, 2009

Zed and community

Who is Zed?

Zed it seems knows about his blogging style: asking questions
as statements;and ranting.but
it seems that he has written good code for the Rails community in the
past and has earned some peoples respect. Now he is a new member of the
Python community I would hope that current members realize his style
and try not to emulate it.

Zed may be here for a long stay, or gone tomorrow, but I wouldn't want
the lasting effect to be a rise in the abrasiveness of the Python
community, or an unthinking
abandonment of community practices. Even if Zed does produce
Pythons Holy Grail, we have to remember that that is software.
Community matters, and we have to work with the
Zeds, the Alex's, the Xah's, the Tim's without being seen to sink to
the lowest common denominator.