# Go deh!

Mainly Tech projects on Python and Electronic Design Automation.

## Friday, May 18, 2007

### 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 problemFrom: http://www.msri.org/people/members/sara/articles/hat.htmlThe 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 randomverbose = Truenumplayers = 3hatcolours = '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 ipassdef 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 ipassdef 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 0def 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()printrun_stratagem(strategy0, verbose)run_stratagem(strategy1, verbose)`

1. Heya there

Really like python code layout and syntax highlighting, looks exactly like the stuff I write in vi :) What did you use to generate the HTML?

2. Why vim 7.0 of course :-)