Posts Tagged ‘python’

Project Creation

Sunday, October 5th, 2008

After making a few tracs and subversion repos by hand and having to do all the little things that need setting up to make things run smoothly (remembering to give svn trunk/tags/branches directories, setting up trac authentication, etc.), I decided to make a little shell script to do most of it for me.

The script I wrote takes a name as its argument and makes a trac and a repository using that name and makes a linked pair with all the bits set the way I need them in my environment for basic functionality. The repository is accessible to anyone in group dev, and I am the only admin on the trac.

if [ $# != 1 ]; then
    echo "Usage: $0 <project name>"
    exit 1
echo "About to create svn/trac for project $PROJ."
echo "    svn: $SVNPATH"
echo "    trac: $TRACPATH"
echo "Press Ctrl-C to abort."
sleep 5
svnadmin create $SVNPATH
chown -R root:dev $SVNPATH
chmod -R g+ws $SVNPATH
svn mkdir -m "Directory layout" file://$SVNPATH/trunk file://$SVNPATH/branches file://$SVNPATH/tags
# initenv <projectname> <db> <repostype> <repospath>
trac-admin $TRACPATH initenv $PROJ sqlite:db/trac.db svn $SVNPATH
chmod g+w $TRACPATH/db
chmod g+w $TRACPATH/db/trac.db
cat >> $TRACPATH/conf/trac.ini <<EOF
acct_mgr.htfile.htpasswdstore = enabled
acct_mgr.web_ui.accountmodule = enabled
acct_mgr.web_ui.loginmodule = enabled
trac.web.auth.loginmodule = disabled
authentication_url =
password_file = /var/trac/htpasswd
password_store = HtPasswdStore
trac-admin $TRACPATH permission add jonathan TRAC_ADMIN

Things I might like to fix someday:

  1. I create duplicate sections in the trac.ini, although it appears to parse them OK.
  2. I’d like it to put a link on the wiki start page with the URL to the repository.

Trac Setup

Monday, July 7th, 2008

Redmine ended up being a bust due to Debian shipping a version of ruby (1.8.7) that is incompatible with Ruby on Rails. Apparently it doesn’t work above 1.8.6. I am impressed that a language’s flagship application gets broken by a point release and no one seems to have anything to say about it other than “don’t use 1.8.7”.

I switched back to Trac despite its limitations because it actually works. Of course, then I had to set up its user authentication, which was a headache of its own. Sometimes I cannot win.

Now, to put things on wikis!

RegExp Master

Thursday, May 8th, 2008

Sphere Online Judge (SPOJ) is an ongoing automated online programming contest site. They are presently running Open Contest 2008, which Dion and I have done some problems in. In order to compare our results, and so that we overdo one problem set rather than actually trying many, I have written a python script to allow us to compare our scores on the RegExp Master problem.

The answer set consists of 10 regular expressions, one per line, or — if no answer is provided for that task. The script assumes that answers are correct, and calculates the score of 1 + 1/length of pattern. — lines score 0 points, as expected.

#!/usr/bin/env python
import sys
def analyze(fname):
    lines = open(fname, "r").readlines()
    i = 1
    total = 0
    for l in lines:
        l = l.rstrip()
        if l == "---":
            score = 0
            score = 1.0 + 1.0/len(l)
        print "%d:\t%d\t%f" % (i, len(l), score)
        i += 1
        total += score
    print "Total score:\t%f" % (total)
if __name__ == "__main__":

My (updated) results:

1:      29      1.034483
2:      104     1.009615
3:      36      1.027778
4:      54      1.018519
5:      17      1.058824
6:      187     1.005348
7:      3       0.000000
8:      95      1.010526
9:      3       0.000000
10:     15      1.066667
Total score:    8.231759

Update: Added more columns to score output, increased my score.

Dice Rolling 2

Saturday, March 1st, 2008

In the last piece I wrote, I was describing how I was trying to make a tool to efficiently calculate the probability of rolling or exceeding a particular sum on a number of dice. I had gotten as far as a recursive solution which allowed me to roll any number of s-sided dice, but which rapidly slowed down as more dice were added.

I spent a good amount of time at this point tearing my hair out looking for patterns in the numbers that would allow me to directly calculate the total number of ways to roll a particular number on n s-sided dice. I never came up with one. What I did end up doing was mentioning my problem to a mathematically inclined officemate, who found a paper on an interesting technique for me

The Technique

The general gist of this method is to, for each face of your current die, add it to the various sums you made on your previous dice.

Let’s give it a try, because that explanation was nearly worthless. I’ll roll two six-sided dice (by hand) to keep things simple, and verify my results against what my prior calculator generated. Then I’ll write a program that will use this method for any n s-sided dice, as before.

For the first die, I can roll any number 1 through 6 exactly one way.


Now, when I roll the second die, I can get a 1 through 6, and add it to each of the pips/ways pairs above. I’ll show what I mean. In the case that my second die is a 1, the table updates like this:

total pipsold pipsnew pips

OK, so that chart isn’t completely enlightening, at least not yet. Please do note that total pips is old pips + new pips. Now I’m going to see what happens if my die comes up a 2.

total pipsold pipsnew pips

Then I add the charts from rolling 1 and 2 and count the number of ways I can get each number.

total pipstotal ways

I’ll do the whole thing again for a three. Possible outcomes:

total pipsold pipsnew pips

And add it to the running count of new possibilities:

total pipstotal ways

If you recall from last time what the chart of how many ways you can roll a given number on two dice looked like, you’ll see that we’re well on our way to generating it. I’m just going to jump ahead and show the results for applying this from 1 all the way to 6 for the second die.

total pipstotal ways

So, let’s have some code.

The Code

def roll(n, s):
    # roll n s-sided dice
    numresults = s ** n         # s^n results
    # make two buffers, with 1 for each value on 1 die
    # neededd because we only do a proper calculation for 2+ dice
    buff = [0] + [1] * s + [0] * ((n - 1) * s)
    oldbuff = [0] + [1] * s + [0] * ((n - 1) * s)
    for d in range(2, n + 1):   # for dice 2 through n
        # clear buffer
        buff = [0] * (s * n + 1)
        for i in range(1, s + 1):
            # for each face, sum with old outcomes
            for j in range(d - 1, (d - 1) * s + 1):
                # We are doing die 'd' now
                # prior results are thus in the range of (d-1, (d-1)*s)
                # We found one way * oldbuff[j] ways = oldbuff[j] ways to get here
                buff[i + j] += oldbuff[j]
        oldbuff = buff
    return (buff, numresults)
def printres(results, numresults):
    remaining = numresults
    print "N\t#N\t%N\t#N+\t%N+"
    for i in range(len(results)):
        chance = 100.0 * results[i] / numresults
        pluschance = 100.0 * remaining / numresults
        print "%d\t%d\t%0.02f\t%d\t%0.02f" % \
            (i, results[i], chance, remaining, pluschance)
        remaining -= results[i]
(results, numresults) = roll(2, 6)
printres(results, numresults)

This produces the same results in only a fraction of the time. It actually goes about the summing in a slightly less efficient manner than the paper that I was shown, but makes up for it by being less mysterious.

The Results

How much faster is it?

When I mentioned calculating 10 10-sided dice last time I actually told a little lie. I didn’t actually bother running the test to the end. During the course of writing this entry I started it running and although I’m not using the fastest machine out there it took more than 2 hours to complete. This version can calculate those results in less than 0.02 seconds.

To be a bit more mathematical, the way the recursive solution is nesting for loops is O(s^n). This solution, however, is O(s*n).

Dice Rolling

Thursday, February 28th, 2008

To start with, I am going to retell the tale of some dice rolling statistics I spent time calculating circa October 2006. My demonstration code is in Python, because it’s fairly legible even if you aren’t familiar with it.


I like to play games, and playing games often requires one to roll dice. In Warmachine, in particular, one rolls a number of six-sided dice, sums the values together, and checks if the total is greater or smaller than another number. I found myself wondering one day how different numbers of dice affected the probability of reaching (or exceeding) certain sums.

Trivial Solution

In the case of Warmachine, one most often rolls two dice, sometimes rolls three dice, and rarely rolls four dice and then adds the values together. Let’s make a quick test program to use for loops to make a chart of outcomes for two six-sided dice to demonstrate where this is going:

def roll():
    # make results array for how many outcomes there are
    results = [0] * 13
    numresults = 0
    for i in range(1, 7):
        for j in range(1, 7):
            # mark that we found one more way of getting i+j
            # and that we have made one more combination
            results[i+j] += 1
            numresults += 1
    return (results, numresults)
def printres(results, numresults):
    remaining = numresults
    print "N\t#N\t%N\t#N+\t%N+"
    for i in range(len(results)):
        chance = 100.0 * results[i] / numresults
        pluschance = 100.0 * remaining / numresults
        print "%d\t%d\t%0.02f\t%d\t%0.02f" % \
            (i, results[i], chance, remaining, pluschance)
        remaining -= results[i]
(results, numresults) = roll()
printres(results, numresults)

The output looks like this:

N       #N      %N      #N+     %N+
0       0       0.00    36      100.00
1       0       0.00    36      100.00
2       1       2.78    36      100.00
3       2       5.56    35      97.22
4       3       8.33    33      91.67
5       4       11.11   30      83.33
6       5       13.89   26      72.22
7       6       16.67   21      58.33
8       5       13.89   15      41.67
9       4       11.11   10      27.78
10      3       8.33    6       16.67
11      2       5.56    3       8.33
12      1       2.78    1       2.78

The N label means the number being rolled. #N is the number of ways that number may be rolled. %N is the chance of that number being rolled. #N+ and %N+ are the number of ways and percentage chance of rolling a value equaling or exceeding N.

As you can see, this method is fairly simple, but the use of nested for loops to control how many dice I’m rolling is very restrictive. For the particular scenario I have outlined, I could have gotten away with nesting four loops and ignoring the ones I didn’t need, but that would have been an inelegant solution. I wanted something general.

OK Solution

I quickly came up with an obvious solution to the problem of needing variable numbers of nested loops – recursion. As this section’s title might suggest, it was not the ultimate solution, but it more than solved the initial problem.

Let’s update and clean the code a bit so that it is rolling n s-sided dice.

def _roll_recursive(n, s, r, results):
    numresults = 0
    for i in range(1, s+1):
        if n == 1:
            results[r+i] += 1
            numresults += 1
            numresults += _roll_recursive(n-1, s, r+i, results)
    return numresults
def roll(n, s):
    # roll n s-sided dice
    # make results array for how many outcomes there are
    results = [0] * (n * s + 1)
    numresults = _roll_recursive(n, s, 0, results)
    return (results, numresults)
def printres(results, numresults):
    remaining = numresults
    print "N\t#N\t%N\t#N+\t%N+"
    for i in range(len(results)):
        chance = 100.0 * results[i] / numresults
        pluschance = 100.0 * remaining / numresults
        print "%d\t%d\t%0.02f\t%d\t%0.02f" % \
            (i, results[i], chance, remaining, pluschance)
        remaining -= results[i]
(results, numresults) = roll(2, 6)
printres(results, numresults)

It’s not much longer (only 4 lines, and those are mostly function definitions and some associated whitespace), and it takes the number and sides of the dice as arguments. The output is the same as that for the trivial solution above. Let’s have it roll 3 dice and see what that looks like.

N       #N      %N      #N+     %N+
0       0       0.00    216     100.00
1       0       0.00    216     100.00
2       0       0.00    216     100.00
3       1       0.46    216     100.00
4       3       1.39    215     99.54
5       6       2.78    212     98.15
6       10      4.63    206     95.37
7       15      6.94    196     90.74
8       21      9.72    181     83.80
9       25      11.57   160     74.07
10      27      12.50   135     62.50
11      27      12.50   108     50.00
12      25      11.57   81      37.50
13      21      9.72    56      25.93
14      15      6.94    35      16.20
15      10      4.63    20      9.26
16      6       2.78    10      4.63
17      3       1.39    4       1.85
18      1       0.46    1       0.46

There we go. Just in case you ever wondered, you have a 0.46% chance of rolling boxcars on three dice.

As stated above, this solution was more than enough to generate all the tables I could have ever wanted for playing Warmachine. However, by this point I no longer had gaming on my mind. I wanted to play around a little, and generate all sorts of weird tables. For example, I wanted to see what the various probabilities looked like if I rolled ten ten-sided dice.

What I found was that it took several minutes to calculate. Now, Python is a very slow language. I gained some ground by rewriting my solution in C, but I still had a fundamentally slow algorithm. It was some time before I had a better solution, which will be discussed in the next post.