Kyle and I were talking about sorting algorithms and he mentioned his idea for the worst algorithm ever which is essentially compute every possibly permutation for an array and then scan the list to find the one that is in sorted order. It sounds pretty stupid and a worthy waste of time

Naturally I wanted to code this in Python because it really is the one true programming language and for the added performance hit

First step is I needed a way to compute all possibly permutations of an array. I optimized slightly and make this function a generator so that I’m not using ridiculous amounts of memory (let’s not be wasteful).

Here is a rather simple generator to return every permutation of the supplied array.

def permutations(list):
    if len(list) == 0:
        yield []
    else:
        for i in range(len(list)):
            for perm in permutations(list[:i] + list[i+1:]):
                yield [list[i]] + perm

Now I also need a way of checking that a list is in sorted order. This is easy.

def issorted(list):
    for i in range(len(list)-1):
        if list[i] > list[i+1]: return 0
    return 1

Finally the sorting algorithm which scans through every permutation until it finds one in sorted order.

def permutationsort(lst):
    for guess in permutations(lst):
        if issorted(guess): return guess
    return None #should never get here

Now what is a new algorithm without amazing performance statistics?

**Note: timing is just elapsed duration and is likely rather inaccurate.

As it turns out sorting a list already in order is a very fast operation with this implementation of the permutation sort (although that can be fixed). The worst case scenario with this implementation is a list in reverse order and as you can see the performance tanks VERY quickly as the size of the list increases (what other algorithm requires 97sec to sort a 10 element list?). In the worst case the number of permutations to be scanned is (list-size)! which is a bit over 3.5million combinations for a 10 element list. A 20 element list would require reviewing 2.5 quintillion lists in the worse case which is WAY beyond the computing power of anything in existence.

This code is available in the public domain and you are welcome to include it in your software

Future ideas for this project include building a distributed permutation sorting tool (much like Seti-at-home) for sorting larger lists of maybe 15 elements). I can just imagine the screen saver this could produce.

Weird! and Yuck!

Anji’s parents own a really nice house in Calgary that they’ve been trying to rent out for quite some time. The house has been sitting vacant for about 8 months and, as luck would have it, 2 months from them returning to Canada (for a couple months) the house finally rents. And naturally the renter wants the house in three days!

So on Tuesday night after work we headed out to the house and proceeded to pack up left over garbage and put all the stuff still in the house into the locked storage room in the basement. After several hours of work we managed to haul most of the dishes and garage stuff downstairs and empty the fridge. There was still the minivan in the garage to deal with but at this point negotiations were in place to leave it there for a few months.

Wednesday night I was working at SAIT so we didn’t get a chance to get to the house.

Thursday night after my googleview we headed out to the house again. This time to cart all the garden tools and van tires into the garage attic. The tires actually went pretty well thanks to my supply of yellow nylon rope. It was just a matter of dropping the rope, having Anji tie it to a tire and slip the other end over a rake I was dangling down, and then hoisting it up. (The opening the the garage attic is roughly a 4ft x 16in whole between the joists so carrying them up would have been really hard. At this point things were going pretty good. It was about 9:30pm and we were about ready to go.

Then we tried to start the van…

The renter decided that she wanted to store her furniture in the garage and didn’t want the van there so we needed to get it out by the Friday morning possession. Unfortunately the battery was dead. We drove my car in and tried boosting it but nothing… At this point Ryan and his GF Sara arrived. I figured the van might just need more juice than my car could pump out so we phoned AMA to get a REAL boost (and if things didn’t go well a tow). Sara, Anji and Kailey headed back to our place to get some sleep while Ryan and I stayed behind for the AMA guy. It took about an hour and a half before he showed up during which time we cleaned up a bit more and Ryan played with his wireless Internet connection.

While we were waiting I kept my cell on me just in case AMA got lost on their way. Then my phone rang. “This is 911 Emergency. We received a phone call from you. Is there an emergency?” Yikes. My stupid phone has some “feature” when holding “1″ down will call 911 and it looks like my pocket did just that. I apologized profusely and ended the call.

Finally AMA showed up and they guy whipped out the booster cables, hooked them up and we tried starting it. Nothing… He turned off his lights, revved the engine for about 10minutes and we tried again. Nothing. Repeat. After about an hour or so of revving and starting he started clunking the starter because he figured maybe so dust/dirt was preventing it from working. It did get to the point of almost turning over once but that was about it. Finally the decision was made to tow the vehicle to Crowfoot Ford. He backed up his truck to the garage, hoisted up the minivan and proceeded to maneuver the van out of the garage with literally inches to spare on both sides of the vehicle (the towing wheels made the vehicle very wide).

Anyways. To make a long story it was 1:30am by time we finally got the van over to Crowfoot Ford and paid the driver for the extra towing. Ryan and I were talking on the way home. It seems to use that this is the guy that really deserves a tip. Sure waitressing in a restaurant is hard work but this guy was with is for about 2 hours, crawling under the vehicle, getting covered in dirt, and all he was paid, from us, was the $8.75 for towing. It just seems so wrong.

For a long time I’ve loved web applications. They seem like the perfect way to deploy so many tools. It’s great lately seeing so many GOOD new web apps spring up. The GOOD web applications, like all good software, have intuitive user interfaces (for their primary functionality at least). Some prime examples would be Google Search and Gmail as both exhibit great power and remarkably simple interfaces.

Yesterday I came across a tool called tadalist which is a great example of a good web application. It’s a basic checklist managing program and it has a very sharp interface. The interface is much like gmail’s (very interactive) in that it almost hides the fact it’s a web application from you. It’s very minimal but it works really well for what it does. It allows sharing of check lists in a very simple but useful way. I like it.

Anyways. yeah.

So I phoned Telus this morning to inquire about (1) cheap evenings and weekends calling, and (2) call forwarding from my cell. I’m curious because I’m expecting to have a fair bit of evening calls to my cell the next bit and would like to try and make that affordable and was thinking either get an evening rate or just forward the calls to whatever land line I’m closest to at the moment.

Anyways I do the usual thing, press 0 as fast as I can because I absolutely hate the stupid voice activated menus which never actually answer my questions and just waste my time. I get this woman right away which is pretty good for Telus. At which point I ask question #1 and it turns out that Telus’s definition of an evening is 8pm which doesn’t help me any. I have 1.5 kids. I’m usually in bed by then. I then try and ask my second question which goes something like this:

Me: I’ve got a pay-and-talk plan and was wondering if I can get call forwarding for it?

Mrs. Telus: And you are Jeff Clement of xxx-xxx-xxxx?

Me: Yes

Mrs. Telus: What is your 4-digit pin code?

Me: My pin code?

Mrs. Telus: Yes

Me: I have no idea

Mrs. Telus: Well you have to use it for [ACRONYM FOR TELEPHONE BASED ACCOUNT ADMIN THINGY].

Me: I use the website.

Mrs. Telus: You need your pin for that.

Me: No I don’t. It uses a real password.

Mrs. Telus: What is that password?

Me: I’m not telling you. (I’m thinking great. She’s probably sitting there reading my password. Note to self: Change it to something anti-Telus just for kicks.)

Mrs. Telus: Well I can’t let you have details for your account without your pin.

Me: I don’t care! (getting annoyed now) I don’t want details for my account. I just want to know about call forwarding. Forget my account!

Mrs. Telus: Ok. No. We don’t offer call forwarding for pay-and-talk plans.

Me: Fine

Mrs. Telus: Any thing else I can help you with?

Me: No. (thinking to my self, “doubtful, you work for Telus”)

Mrs. Telus: Thank you for calling Telus.

Click!

Bah. Was that really so hard to just answer my questions? -10pts for asking for my password. -10 for probably seeing my password on her screen in order to validate that. Grr.

Anyways. I’m not usually a mean guy. I just really hate Telus. I have yet to have a single useful interaction with any of them. This includes their cell phone people, business internet support, phone support, etc, etc, etc.

I was thinking it would be nice to just start using gmail. But I have so much historical e-mail (13,000 messages) that I’d like to be able to access. I found a python script that would allow me to import from my maildirs but unfortunately it didn’t keep state as to how far it made it and gmail’s smtp servers would keep blocking me after a few thousand messages. So I wrote a simple tool index all of my e-mail messages and keep track of whether they had been successfully sent or not and another tool to poll that list and try sending the ones that haven’t been sent. Here is that tool (yes. it’s really hacked together. I was lazy)

import os
import sqlite
import whrandom
import time
import sys
import smtplib
import email

DBFILE = '/home/jsc/.gmaildb'
DESTADDR = 'FILLINADDRESSHERE@gmail.com'
SERVERS = ['gsmtp57.google.com','gsmtp185.google.com','gsmtp185-2.google.com','gsmtp171.google.com','gsmtp171-2.google.com']

class GoogleMailImporter:
    def __init__(self, dbfile, destaddr, servers):
        if not os.path.exists(dbfile):
            self._db = sqlite.connect(dbfile)
            c = self._db.cursor()
            c.execute('create table maillog (msgid integer primary key, msgpath varchar(2000), posted integer)')
            self._db.commit()
        else:
            self._db = sqlite.connect(dbfile)
        self._destaddr = destaddr
        self._servers = servers

    def _sendMessage(self, destaddr, server, msgfile):
        rawmsg = open(msgfile,'r').read()
        msg = email.message_from_string(rawmsg)
        #server = smtplib.SMTP(server)
        server.sendmail(msg['From'], destaddr, rawmsg)
        #server.quit()
        return 1

    def importDirectory(self, directory):
        c = self._db.cursor()
        for pardir, dirs, files in os.walk(directory):
            for file in files:
                c.execute('insert into maillog (msgpath) values (%s)',os.path.realpath(os.path.join(pardir,file)))
        self._db.commit()

    def process(self):
        connections = []
        for server in self._servers:
            connections.append(smtplib.SMTP(server))
        c = self._db.cursor()
        c.execute('select * from maillog where posted <> 1 or posted is null')
        for row in c.fetchall():
            try:
                if self._sendMessage(self._destaddr, whrandom.choice(connections), row['msgpath']):
                    print "posted",row['msgpath']
                    c.execute('update maillog set posted=1 where msgid=%s',row['msgid'])
                    self._db.commit()
            except Exception, e:
                print "error",row['msgpath'],e
            #time.sleep(2)

if __name__=='__main__':
    gm = GoogleMailImporter(DBFILE, DESTADDR, SERVERS)
    if len(sys.argv)==2 and sys.argv[1] == 'process':
        gm.process()
    elif len(sys.argv)==3 and sys.argv[1] == 'import':
        gm.importDirectory(sys.argv[2])
    else:
        print "syntax"

On an interesting note of my 13,000 archived messages about 3544 are actually spam. Unfortunately my old archival scheme was just save everything just in case. So now I’ve got ~10,000 historical ham messages (4758 conversations) in gmail and I’m using … 160MB

Came across the IronPython project a while ago but haven’t really touched it much. Finally had some time this afternoon so I took a peak at it. IronPython is yet another project to integrate Python and .NET.

I really like the idea of integrating Python and .NET for several reasons:

• Being able to embed a Python interpreter in a .NET application as a scripting engine to allow easy extension / behaviour tweaking would be great. Our app has lots of little client specific extensions and being able to have them written in a very high level language would be nice.
• On that note being able to embed a Python interpreter into a running app so that you can invoke the interpreter and then poke with live objects would just be soo cool. It would be so useful for developing and testing.

My little test program is this one.

import sys
sys.LoadAssemblyByName("System.Windows.Forms")
from System.Windows.Forms import MessageBox
MessageBox.Show('Hello World')

I’ll play with it more tomorrow and see if I can embed an interpreter.

I’ve been thinking for a while now that maybe I should make one of those trendy photoblogs to aid my visitors in seeing my latest and greatest photos since rummaging through the albums isn’t usually all that fun (although I’ll still keep those there too). Anyways Lorien reminded me about this so I got after it and actually built it. The software is a bit clunky but it works and it has an archive, comments, and all the usual stuff. Only thing it’s missing would be photos but I have plans to add those in the near future

So if you are interested go ahead and hit my photoblog.

I plan on building a smarter archive (once there is data to be archived) and an RSS feed when I have time.

For a while now I’ve been playing with a “social bookmarking” service called del.icio.us and I think I’m quite hooked.

I’ve never liked the traditional hierarchical bookmarks system for the same reason I don’t like folders for e-mails. I rarely find that a bookmark belongs in only one filter but the tools make it hard/impossible for a bookmark to exist in more than one place and still be maintainable. del.icio.us uses tags instead. When you add a bookmark to del.icio.us you provide a name, url, and description and you also provide a list of tags. Tags are just single works describing the link. So my site might be given tags like “geek photography linux python”. Now when I’m browsing my bookmarks I can look at the geek tag and I’ll see all the bookmarks tagged with geek. Then I can narrow it down my choosing photography and get those that have both tags and so on. Trust me. Very cool.

Another thing I hate about bookmarking built into browsers is that I surf at home and at work and I want access to my bookmarks from home and work without having to work at it. With del.icio.us all your bookmarks are stored on their server which is a bit scary but they give you access to your raw data so you can do your own backups. And since it’s stored on their server you can access it from everywhere. You are given your own URL for your bookmarks (http://del.icio.us/jclement) and you can easily filter the results by adding tags onto that like (http://del.icio.us/jclement/photography) and (http://del.icio.us/jclement/photography+hacks).

This alone would have made me really happy but the final coolness points come from the “social” side of it. Basically when you link to a site del.icio.us keeps track of others who have linked to have same site and can use that information to suggest tags for the site as well as allow you to view popular bookmarks for a given tag. I’ve been loving the popular bookmarks feature. It saves me from having to look around the net for interesting stuff. As people find neat stuff they add it to their bookmarks and if enough people do that it shows up in the popular lists and then I can copy it to my bookmarks. I don’t think I described that well but it’s slick. You can even subscribe to another users bookmarks if you find they are interested in the same stuff as you so that when they add stuff you are notified. Only thing to watch out for is that your bookmarks are public which works for me but might not for you

Using del.icio.us is really simple. The about page has instructions. I simply added two buttons to my browser toolbar. One button to add the current page to del.icio.us (using the experimental one on the about page) and another button to bring my to my main page on del.icio.us. It’s awsome.

I came across this interesting article this afternoon describing the use of gmail as a spam filtering system for another e-mail account. Given that my server is pretty much crippled by spamassassin this tweaked my interest.

The solution is really quite simple. From your gmail account you set it up to forward all e-mail to your real account. On your real e-mail account you set it up to look for a “X-Forwarded-For: user@gmail.com user@domain.com” header that gmail sets when forwarding e-mail. If the header is there then it came from google and was spam checked. If it isn’t then it wasn’t so forward it to google and it’ll be back in a bit assuming they didn’t think it was spam.

This has the advantage of not using my CPU time for spam filtering and providing free backups (2gb and counting). Of course all this assumes you don’t mind that google is reading your e-mail.

Just for kicks I set it up on my account. Here is my .procmailrc.

###################################################################
# Jeff's Spam Filtering ProcMailRC (using gmail)
# inspired by http://mboffin.com/post.aspx?id=1636
###################################################################

### If gmail forwarded header is missing, forward to gmail
:0:
* ^X-Forwarded-For: [MY GMAIL ADDRESS] [MY REAL ADDRESS]$
./Maildir/

### Otherwise we don't have the gmail header so forward it on to gmail to
### borrow their spam filtering (account is setup to forward back)
:0
*
! [MY GMAIL ADDRESS]

We’ll see how it goes. I’m not really crazy about relying on anything but my own server for e-mail and I don’t really like them having copies of my e-mail but not having to run spamassassin would be REALLY nice.

Just for interest my server VM has 128M of virtual memory and was using all of it and about 100M of swap. Now that I’ve shut spamassassin down I’m using 48M and no swap. Hmmmm.