Python makes simple solutions.

The title is a slogan I thought of to counter those who say Python is simple. My slogan emphasises that :

• Python solves problems.
• Those solutions are simple to understand.
• The code produced is simple to maintain.

I've been Crunched!

There is a new crunchy out. I just downloaded the release, unzipped to a directory, then double-clicked crunchy.py, and Firefox opened a new page of delight. Five minutes of reading and I was able to open this very blog and have all the Python code come alive. On this entry, I was able to re-run the example and have new times printed - in the browser, with just a click of an (added) button!
If I had a new algorithm I could have used the edit window supplied to write and test it as well as save my changes.

Here is what a crunchy version of this page looks like.

The added editor comes pre-loaded with my example code. The new execute button, when clicked inserts the output of running the code from the editor below it. (click on the image for a larger view).


Neat!

bit twiddling extras

As a follow up to this
I commented on what I thought would be a better solution. Richard Jones pointed us at how pyglet solved how to find the net power of two and how to check if a number is a power of two using some nifty bit twiddling.

Will McGugan then timed
both his and pyglets code, but didn't implement my suggestion (I didn't give code).

I have added an implementation of my suggestion and timed all three sets.
The timing shows that although my implementation of is_power_of_2 is fastest by a smidgen; My implementation of next_power_of_2 by iterative comparison of a list is half way between Wills and pyglets implementation, with pyglet the winner.

I have not got timings with psyco.


The code

setup_1 = """
from math import log, ceil
 
def is_power_of_2(n):
    return log(n, 2) % 1.0 == 0.0
 
def next_power_of_2(n):
    return (2 ** ceil(log(n, 2)))
"""

setup_2 = """
def next_power_of_2(v):
    v -= 1
    v |= v >> 1
    v |= v >> 2
    v |= v >> 4
    v |= v >> 8
    v |= v >> 16
    return v + 1
 
def is_power_of_2(v):
    return (v & (v - 1)) == 0
"""

setup_3 = """
list_of_powers = [x**2 for x in range(32)]
set_of_powers = set(list_of_powers)

def next_power_of_2(v):
    for x in list_of_powers:
        if x >= v: return x

def is_power_of_2(n):
    return n in set_of_powers

"""


from timeit import Timer

t1 = Timer("is_power_of_2(128)", setup_1)
t2 = Timer("is_power_of_2(128)", setup_2)
t3 = Timer("next_power_of_2(125)", setup_1)
t4 = Timer("next_power_of_2(125)", setup_2)
t5 = Timer("is_power_of_2(128)", setup_3)
t6 = Timer("next_power_of_2(125)", setup_3)

print "float math is_power_of_2:", t1.timeit()
print "bit-twiddling is_power_of_2:", t2.timeit()
print "set-lookup is_power_of_2:", t5.timeit()
print
print "float math next power of 2:", t3.timeit()
print "bit-twiddling next power of 2:", t4.timeit()
print "list-comparison next power of 2:", t6.timeit()

The Timings

float math is_power_of_2: 2.33588961726
bit-twiddling is_power_of_2: 0.573784377623
set-lookup is_power_of_2: 0.54499859619

float math next power of 2: 3.06279429369
bit-twiddling next power of 2: 2.08060354039
list-comparison next power of 2: 2.58548279181

My First Python one-liner

I created my first Python one-liner, to be used in anger today!
I was working on Unix, and because I know and use the normal command line utilities sed/grep/awk/perl etc, as well as Python, I tend to not use Python for one-liners (even very long one-liners), as Pythons syntax isn't up for it, and the other tools are in their element.
Today I was installing four simulation/verification packages from Cadence. We use the modules utility to allow us to easily access tools, but these new tools had what I was told was a complex setup script to be sourced that did a lot before setting environment variables to appropriate values.

I decided I needed to see what the changes to the environment were so needed to create a sorted list of environment variables before & after sourcing the setup, and then doing a gvimdiff. I could not use env|sort as our environment has a few variables with multi-line string values which are printed on separate lines and so mess with the sort.

I remembered that pprint sorts dictionaries and prints string values with escaped versions of newlines so came up with:

 python -c 'import os, pprint; pprint.pprint(dict(os.environ))' 

The dict() is needed as os.environ is not a true dictionary, it can interact with calls to putenv() and unsetenv.

Here is a sample session showing how it prints newlines in values:

bash$ export XX='Spam
Ham'
bash$ python -c 'import os, pprint; pprint.pprint(dict(os.environ))'|fgrep XX
 'XX': 'Spam\nHam',
bash$

- Paddy.

The Hat Problem

I found an item describing an intriguing mathematical game, that I immediately 'got' for the size of problem described and decided to write a Python program to help me explore it.

In the source, you can create different strategy functions that take the same arguments
and return either a colour or the global name ipass.

Enjoy!

'''
The hat problem

From: http://www.msri.org/people/members/sara/articles/hat.html

The hat problem goes like this:
    Three players enter a room and a red or blue hat is placed on each
    person's head. The color of each hat is determined by a coin toss,
    with the outcome of one coin toss having no effect on the others. Each
    person can see the other players' hats but not his own.

    No communication of any sort is allowed, except for an initial
    strategy session before the game begins. Once they have had a chance
    to look at the other hats, the players must simultaneously guess the
    color of their own hats or pass. The group shares a hypothetical $3
    million prize if at least one player guesses correctly and no players
    guess incorrectly.
'''

import random

verbose = True
numplayers = 3
hatcolours = 'red blue'.split()
ipass = 'pass'

def otherhatcolour(hat):
    ''' not(hat) when hat can have two or more colours'''
    return hatcolours[(hatcolours.index(hat)+1) % len(hatcolours)]

def playerhats(n = numplayers):
    ''' generate all hat combinations for the players, but scrambled.'''
    if n:
        hats = hatcolours[:]
        random.shuffle(hats)
        for h1 in hats:
            for h2 in playerhats(n-1):
                yield [h1] + h2
    else:
        yield []

def strategy0(otherhats, hatcolours):
    '''
    If there is a clear max total of hat colours:
        Yours is a random choice from the hat colours occuring the least
    else:
        pass
    '''
    # Count the total hats in each colour
    colourcount = [otherhats.count(c) for c in hatcolours]
    # What hat colours are most/least prevalent
    mn = min(colourcount)
    mx = max(colourcount)
    #
    if colourcount.count(mx) == 1:
        # only one colour occurs as the maximum
        return hatcolours[random.choice([ index
                                          for index, count in enumerate(colourcount)
                                          if count == mn]) ]
    else:
        return ipass

def strategy1(otherhats, hatcolours):
    '''
    If there is a clear max and min total of hat colours,
    Yours is the min; otherwise pass.
    '''
    # Count the total hats in each colour
    colourcount = [otherhats.count(c) for c in hatcolours]
    # What hat colours are most/least prevalent
    mn = min(colourcount)
    mx = max(colourcount)
    #
    if mn != mx and (mn == 0 or colourcount.count(mx) == colourcount.count(mn) == 1):
        # only one colour occurs as the maximum, another as minimum
        # So guess the minimum
        return hatcolours[colourcount.index(mn)]
    else:
        return ipass

def scoreplayers(ph, strategy, _verbose = verbose):
    ''' Compute score and return 1 if players win otherwise zero'''
    n = len(ph)
    strat = []
    playerguessed = []
    for playernum,hat in enumerate(ph):
        strat = strategy([h for i,h in enumerate(ph) if i != playernum], hatcolours)
        if _verbose:
            print "%sPlayer%i:%s under a %6s hat replies: %6s" % (
                "  "*(playernum+1), playernum, "  "*(n-playernum-1), hat, strat
                ),
        if strat == hat:
            if _verbose:
                print "Correct"
            playerguessed.append(True)
        elif strat == ipass:
            if _verbose:
                print "-"
            playerguessed.append(ipass)
        else:
            if _verbose:
                print "Incorrect"
            playerguessed.append(False)
    if (True in playerguessed) and not( False in playerguessed):
        if _verbose:
            print "   Players WIN\n"
        return 1
    else:
        if _verbose:
            print "   Players LOSE\n"
        return 0



def run_stratagem(strategy, _verbose= verbose, _numplayers = numplayers,
                   _hatcolours = hatcolours):
    '''Applies a strategy function to all possible games of a hat problem.

    Prints either a verbose output of every trial, or a summary of
    all trials in csv format
    '''

    global verbose, numplayers, hatcolours
    verbose, numplayers, hatcolours = _verbose, _numplayers, _hatcolours

    totaltries = 0
    totalwins = 0
    if verbose:
        print "\nSTRATEGY"
        print strategy.__name__
        print strategy.__doc__
    for ph in playerhats():
        totaltries +=1
        totalwins += scoreplayers(ph, strategy, verbose)
    if verbose:
        print "\n\n Players won %i/%i = %.2g%% of the time by using %s\n" % (
                totalwins, totaltries, float(totalwins)/totaltries*100.0,
                strategy.__name__)
    else:
        print "Strategy,%s,Hats,%i,Players,%i,Games,%i,Wins,%i,Win%%,%.4f" % (
                strategy.__name__, len(hatcolours), numplayers,
                totaltries, totalwins, float(totalwins)/totaltries)


colours = 'red blue orange yellow green indigo violet'.split()
print
run_stratagem(strategy0, verbose)
run_stratagem(strategy1, verbose)

Wheel of time...

Just read Invasion Of The Dynamic Language Weenies it seems that what goes around, comes around, in that here we have a Java programmer decrying an article on dynamic languages, when years earlier I could read similar articles from C++ adherents about this new Java thing from Sun. java must be cool. Java had its culture. Interminable articles on run-anywhere code and late night drinking (of high strength coffee).

Excuse me while I fetch a lemon - some crocodile tears are called for. ;-)

"The Wheel of Time turns, and Ages come and pass, leaving memories that become legend. Legend fades to myth, and even myth is long forgotten when the Age that gave it birth comes again".

Robert Jordan - "The Wheel of Time".

Bash style environment variable expander in Python

At work we have a certain config file that has bash/tcsh style embedded environment variable references of two styles:
${VARNAME}
and
$VARNAME

I thought I would try my hand at a concise python expander for the syntax and came up with:

bash$  python -c '
import sys,os,re
s=sys.stdin.read()
s1 = re.subn(r"\$([a-z_A-Z][A-Za-z_0-9\-]*)", r"%(\1)s", s)[0]
s2 = re.subn(r"\${([^}]+)}", r"%(\1)s", s1)[0]
print s2 % os.environ ' < in_file > expanded_file

Fizz-Buzz.py

I am having to set some extra work at home for my ten year old son. I found information on a game Fizz-Buzz and introduced it to my son, only to find that he had already played a variant at school.

Oh well.

By that time I had already created a python program to check his answers (written in simplistic style as I intend one day to get all of my kids to learn Python).

'''
Fizz-Buzz.py

Fizz-Buzz Game.
Instructions for two players, 3-5 game. (Easiest).

   1. Players take it in turns counting from one to ninety-nine.
      (Don't take too much or too little time between numbers
       - try for a steady pace)
   2. Player must say Fizz-Buzz instead of their number if the number is a
      multiple of three and of five.
   3. Otherwise, player must say Fizz instead of their number if the number
      is a multiple of three.
   4. Otherwise, player must say Buzz instead of their number if the number
      is a multiple of Five. 

Digit version
  Use basic instructions 1-4 as above, then add the following rules:

   5. Otherwise, player must say Fizz for each digit in the number that is
      a three,
      And player must also say Buzz for each digit in the number that is a
      five.
      (for example, say Fizz-one instead of 31, Fizz-two instead of thirty
      two)
   6. Remember, the rules must be applied in order so  thirty three is
      actually Fizz and not Fizz-Fizz as it is first a multiple of three
'''

fizz = 3
buzz = 5
digits_version = True

for tens in (0,1,2,3,4,5,6,7,8,9):
   for units in (0,1,2,3,4,5,6,7,8,9):
       number = tens*10 + units
       if number == 0:
           pass
       else:
           print "For", number, "Say",
           if (number % fizz) == 0 and (number % buzz) == 0:
               print "FizzBuzz"
           elif (number % fizz) == 0:
               print "Fizz"
           elif (number % buzz) == 0:
               print "Buzz"
           elif digits_version:
               saytens = tens
               sayunits = units
               digits_as_fizzbuzz = False
               if tens == fizz:
                   saytens = "Fizz"
                   digits_as_fizzbuzz = True
               if units == fizz:
                   sayunits = "Fizz"
                   digits_as_fizzbuzz = True
               if tens == buzz:
                   saytens = "Buzz"
                   digits_as_fizzbuzz = True
               if units == buzz:
                   sayunits = "Buzz"
                   digits_as_fizzbuzz = True
               if digits_as_fizzbuzz:
                   print saytens,sayunits
               else:
                   print number
           else:
               print number

Pythons Function Nested Parameter Definitions

(And I don't mean nested function definitions).

Whilst reading PEP3107 on what's coming this year in Python 3000 I came across this section where it mentions nested parameters in function definitions.
I could not emember this feature so googled a bit, and still could not find it.
It was time to suck-it-and-see, so using Python2.5 I did:

>>> def x ((p0, p1), p2):
...     return p0,p1,p2
...
>>> x(('Does', 'this'), 'work')
('Does', 'this', 'work')
>>>

My current skunk-works project extracts data from VHDL source files as a list of nested tuples. I use each outer tuple as a record but unpack the record manually at each function call. If I used the above then the function parameter definition would reflect the record structure.

On closer inspection of the Python Function definition grammar, I find that nested parameters are represented by the sublist token.

Neat!

- Paddy.

unzip un-needed in Python

Someone blogged about Python not having an unzip function to go with zip().
unzip is straight-forward to calculate because:

>>> t1 = (0,1,2,3)
>>> t2 = (7,6,5,4)
>>> [t1,t2] == zip(*zip(t1,t2))
True

Explanation

In answer to a commentator, I have written a (large), program to explain the above.
unzip_explained.py:

'''
Explanation of unzip expression zip(*zip(A,B))

References:
 1: Unpacking argumment lists
    http://www.network-theory.co.uk/docs/pytut/UnpackingArgumentLists.html
 2: Zip
    >>> help(zip)
    Help on built-in function zip in module __builtin__:

    zip(...)
        zip(seq1 [, seq2 [...]]) -> [(seq1[0], seq2[0] ...), (...)]
        
        Return a list of tuples, where each tuple contains the i-th element
        from each of the argument sequences.  The returned list is truncated
        in length to the length of the shortest argument sequence.


'''

def show_args(*positional, **kwargs):
  "Straight-forward function to show its arguments"
  n = 0
  for p in positional:
    print "    positional argument", n, "is", p
    n += 1
  for k,v in sorted(kwargs.items()):
    print "    keyword argument", k, "is", v

A = tuple( "A%i" % n for n in range(3) )
print "\n\nTuple A is:"; print "   ", A
B = tuple( "B%i" % n for n in range(3) )
print "Tuple B is:"; print "   ", B

print "\nLets go slowly through the expression: [A,B] == zip(*zip(A,B))\n"

print "List [A,B] is:"
print "   ", [A,B]
print "zip(A,B) has arguments:"; show_args(A,B)
print "zip(A,B) returns:"
print "   ", zip(A,B)
print "The leftmost zip in zip(*zip(A,B)), due"
print " to the 'list unpacking' of the previous"
print " value has arguments of:"; show_args(*zip(A,B))
print "The outer zip therefore returns:"
print "   ", zip(*zip(A,B))
print "Which is the same as [A,B]\n"

And here is the program output:

Tuple A is:
    ('A0', 'A1', 'A2')
Tuple B is:
    ('B0', 'B1', 'B2')

Lets go slowly through the expression: [A,B] == zip(*zip(A,B))

List [A,B] is:
    [('A0', 'A1', 'A2'), ('B0', 'B1', 'B2')]
zip(A,B) has arguments:
    positional argument 0 is ('A0', 'A1', 'A2')
    positional argument 1 is ('B0', 'B1', 'B2')
zip(A,B) returns:
    [('A0', 'B0'), ('A1', 'B1'), ('A2', 'B2')]
The leftmost zip in zip(*zip(A,B)), due
 to the 'list unpacking' of the previous
 value has arguments of:
    positional argument 0 is ('A0', 'B0')
    positional argument 1 is ('A1', 'B1')
    positional argument 2 is ('A2', 'B2')
The outer zip therefore returns:
    [('A0', 'A1', 'A2'), ('B0', 'B1', 'B2')]
Which is the same as [A,B]