ICFP 2008 programming contest

It's been about a week since our team (myself, Pieter Holtzhausen, Loftie Ellis and Albert Swart) completed the ICFP programming contest. I think I've had enough sleep now for a little writeup.

The most important problem was that the provided sample maps and server was not necessarily representative of what we will be judged against. Assuming martians are not a threat (either not smart or too few), the optimal strategy is to ignore them, keep accelerating and dodge craters and boulders on the way to the home base. If a map contains martians of significant intelligence, they will have to be avoided.

Our approach was to continuously switch between 2 modes:

1. Given a goal position (initially the home base), move towards that goal. If there is an object in the path towards the goal, set the goal to be directly to the side of the obstacle. Once we arrive at a goal, reset the goal to the home base and repeat.

2. If our strategy is to take martians into account, predict if we will collide with a martian on our current velocity and path. If we will collide, change the goal position to be somewhere else.

We decide on our mode based on what was learned about the map. By default we start in the first mode. If we were killed by a martian or have observed more than 4 martians at once in a previous run, start the next run in martian avoidance mode. If we ran into a crater, ignore the martians by next time starting in the first mode.

We wrote everything in Python. We spent most of the time on tweaking the goal following code, keeping the server communication stable and fighting with the lack of a Windows version of the server. Towards the end we tried A* path finding to hook into the goal following system, but decided not to include it in our final version. We also have an alternative visualization system based on OpenCV.

I'm quite proud of our entry. We never collide with any craters or boulders if enemies are ignored. If enemies are taken into account we effectively make running away from them our short term mission. I'm a bit worried they will test our code against maps with dead ends, or that our martian avoidance code fails (because it hasn't been thoroughly tested).

I predict the first few places will be taken by entries that can characterize the type of map quickly.

buying a katana

I've been bitten by the Kendo bug. I've been doing it for a few months now and I feel it's time I got myself a real blade.

However, I don't want a wallhanger. I want something that can cut. Fortunately Cheness focuses on quality cutting-blades available for less than 300USD.

I was really impressed by their "Shura". I've read a lot of really good reviews, especially the one at sword-buyers-guide and the destruction test at RS knives.

Living in South Africa, I knew there would be some problems getting it shipped here. So I decided to purchase it through Paul from sword-buyers-guide. I am very thankful to Paul for going out of his way to help me. His customer support is excellent.

The sword is now on its way. Hopefully it will get here safely.

interactive recognition of hand-drawn circuit diagrams

After six years of study I completed my degree of BEng/MScEng (with computer science) last week. Here is a video of the final prototype:



You can download my full thesis or some slides from my wikispaces account.

One of my favourite parts:

It is generally believed that state coverage is superior to code coverage. It is the author's opinion, however, that state coverage is less important in Python than other languages. As Python typically processes collections (such as lists) using an iterator and not incrementing indices, there are less ways in which errors can occur. Since variables also need not be declared it is also less likely that null pointers would be dereferenced. This is, for example, one of the most frequent sources of errors in the Java programming language.

ICFP contest done

My team and I participated in this year's ICFP programming contest - a weekend of very little sleep and lots of programming. This was the first year our team (i.e. The Black Knight Always Triumphs) took part.

We were amazed at the effort the judges must have gone through to prepare the problems. My favorite problems where writing the virtual machine that ran the problems and hacking into "user accounts" using their stripped down version of Basic which uses Roman numerals for line numbers.

We expect to finish under the first third of participants (that made it to the scoreboard) and we'll definately be back next year.

del.icio.us importing

I wanted to change my del.icio.us username. You aren't allowed to do this directly, but you can export your links to an html file and try to import it back into a new account. Unfortunately their import function can't parse the data generated by their export function. Strange. (apparently fixed now) Luckely they have an open API (and a whole bunch of third-party tools).

So with the help of BeautifulSoup I simply parsed the exported html and used pydelicious to post it back into delicious. Like So:

from BeautifulSoup import BeautifulSoup
import pydelicious
from itertools import count

def main():
  soup = BeautifulSoup(file("export.htm").read())
  user = "user"
  password = "pass"
  items = soup.findAll("a")
  print len(items)
  for item, n in zip(items, count()):
    href = item["href"]
    tags = item["tags"]
    title = item.string
    add_date = item["add_date"]
    last_modified = item["last_modified"]
    print n,
    try:
      pydelicious.add(user, password, href, title, tags=tags, dt=add_date, replace="yes")
    except Exception, e:
      print e

Ah, I love Python.

While writing this post I ran into some del.icio.us experiments, which might be useful to someone. And a follow-up with very pretty graphs.

I want; I need

Feature requests I filed in last half hour. Not all of them are really thought through that well, but I just want to be sure the developers are aware of my needs.

7-zip (compression):

• checkout/install files
• always extract to subfolder

Flock (webbrowser):

• customize search engines from options
• links on page work between link is followed and one is activated

wikidPad (note keeper):

• scan icons subdirectory and image pasting also copies image to a subdir

os.listdir iterator

I found an iterator version of os.listdir for POSIX(?) systems, but I needed one for Windows. Specifically to check if a directory has subdirectories.

import win32file import pywintypes def has_subdirectories(path): try: for info in win32file.FindFilesIterator(os.path.join(path, "*")): if info[0] & win32file.FILE_ATTRIBUTE_DIRECTORY and info[-2] not in [".", ".."]: return True except pywintypes.error: # access denied pass return False

Characterizing People as Non-Linear, First-Order Components in Software Development

Alistair Cockburn has written a lot of very interesting articles but I have to agree with John Carter on Lambda the Ultimate when he called this one his "absolute favourite paper in all the CS literature".