Janto's blog

icfp 2011 contest

2011-06-21T14:37:00.002+02:00

Our approach was more relaxed this year. I suspect we were more in the mood for fun hacking than doing well on the leader board.

We played with the idea of using subversion instead of a DVCS. I thought our workflow might require too many merges, but in the end Mercurial's branches worked well for us. It also made bringing old bots back to life pretty easy. Doing the same with subversion would probably have been more complicated.

Our implementation was done in Python. Field values were either integers or objects with run methods (aliased with __call__). Functions like attack, heal and K that take more than one turn were implemented as nested class definitions. It was simple, and worked well. S was the most deeply nested:

class S(Func):
    def run(self, arg):

        class S_partial1(Func):

            def __repr__(next_self):
                return "S(%s)"%arg

            def run(next_self1, next_arg1):
                class S_partial2(Func):
                    def __repr__(next_self2):
                        return "S(%s)(%s)"%(arg, next_arg1)
                    def run(next_self2, next_arg2):
                        return arg(next_arg2)(next_arg1(next_arg2))
                return S_partial2()

        return S_partial1()

We started with some very basic bots and worked our way up to more complex behavior. Many of our strategies are rather sensitive to interference as they where (initially) launched from the first few slots. If those slots are damaged by the opponent everything fails. Trying to capitalize on this we tried to monitor actions of opponent and attack slots that gets most "activity".

Unfortunately the monitoring is rather complex and slow. So we experienced timeout issues on the test server.

We also tried to detect how zombie cards are played and heal its target ASAP. Seems to work quite well and makes the opponent waste a few moves and messes with their state.

Overall we think our strategies were sufficiently smart, but some of it just took too many turns and processing time.

We wasted a few hours debugging a non-issue... I just forgot to call stdout.flush(). Also, in the end we might have submitted a buggy version. Oops! Will have to see how it goes. I should have made unit tests.

This year's ICFP was a lot of fun! The organizers did not make any of the mistakes made in previous years: The problem was well defined, there wasn't any obfuscation for the sake of obfuscation, the barrier to entry was low and there weren't any serious issues with the test server. It was all done very well. From their blog comments they always seemed friendly and in good spirits. It's subtle things like this that I think make a competition fun.

If there is any criticism then it's with the submission form. It probably made the organizers' job much easier, but it would have been nice to see the state of your own submission.

Edit: We only bothered getting one camera working this year.

ICFP 2010 contest

2010-07-08T00:47:00.001+02:00

Our team had 5 members this year: Myself, Loftie Ellis, Niel Thom, Pieter Holtzhausen and Albert Swart. It was Niel's first time participating and helped tremendously. We had a lot of fun. Mostly due to the team dynamics. The contest itself... not so much.

We soon figured out the organisers tried to make things interesting by leaving out large parts of the spec. This might have been a good idea if there wasn't multiple plausible interpretations for the single provided example. And Occam's razor did not hold true.
It took us about 24h to convince ourselves that our initial assumptions were incorrect. Our interpretation did not produce a consistent mapping. If it wasn't for a comment on the IRC channel, we might have wasted even more time trying to track down non-existent bugs.

Overall I was disappointed in this year's problem. The barrier to entry was just too large. In fact, only about a quarter of registered teams received any points. Meaning they either couldn't figure out the circuit format or couldn't compute the prefix. That's just silly. It should be easy for a team to get going, after which things can get as complex as they want.

I doubt many teams got to the really interesting problems. If Loftie didn't submit the correct prefix 5am on Monday (about 7h before contest end), we wouldn't have had any points.

I hope next year is organised by an American university. From my experience, their's are usually more fun.

I again made some time lapse videos of us working. We played a lot of StarCraft towards the end :) I might put it on youtube some time.

Update: Videos follow

icfp 2009 contest

2009-06-29T23:27:00.000+02:00

Here's a quick technical writeup about our entry for this year's ICFP contest.

Our team of 4 is called "xor eax, eax". i.e. myself, Loftie Ellis, Pieter Holtzhausen and Albert Swart.

After a bit of discussion, Loftie and I set to work coding up the virtual machine specification in Python. We used the builtin array type to manage the bytecode, but later switched to numpy. Albert translated it to a C version, which Pieter hooked into Python code with ctypes. I wrote a simple GUI in opencv.

We encountered a few issues switching between our 32bit and 64bit machines. We had an 8x2GHz machine to our disposal, but ended up not really using it.

Pieter wrote the basic Hohnmann transfer code, which Loftie used to manually determine target orbits for the first 2 problem sets. I used Python structs to write the submissions file.

We finished it well within the lightning round time. In fact most of the work happened in the first 8 hours. At one stage we where fourth on the leader board. Unfortunately we spent too much time on the manual tweaking Saturday and was only able to do problem sets one, two and a single scenario of problem set 3 for the lightning round.

We decided to approach problem 4 as a series of jumps between different orbital radii. In other words: to reach a target we need to do a Hohnmann transfer to a radius that will cause the target and our ship to meet. We did not have enough sleep and energy to explore the optimal sequential order of the jumps in too much detail.

So Sunday I set to work on setting up scipy's optimization library to search for the optimal radius. We tended to primarily use the Golden section search. That worked well and converged in around 35 iterations on average.

Monday we didn't really do anything (except for playing a game of starcraft). The last update of the score board placed us at position 77. Since then we raised our score to around 2200, if I recall correctly, by primarily completing the remaining scenarios of problem 3.

(Edit: The final scores are in. We finished 70th out of 328 with a score of 2275.)

We should have spent less time manually tweaking behavior and rather try to find a more general solution. We also should have looked at the scenario's in more detail, since we later discovered them to be simpler than the assumptions we were working with. I think these two factors sucked more of our energy than we should have allowed it to.

I was hesitant when we began writing the VM in python, but it was surprisingly efficient. The C version was around 5x faster I would guess. Some of the other members were surprised by some python's scoping strangeness. It's interpreted nature allowed us a lot of experimentation, however. We used a local subversion repository, which worked out well.

All things considered it was a good competition. The only major upset was a re-release of the problem 4 binary, which invalidated a few hours of our work. I have never really read about astrodynamics before this contest and found it very interesting.

During the competition I continuously captured one image every minute from a webcam I mounted on the wall with sticky tape. Using mencoder I compiled it into a 25fps video. So each second in the video represents the passage of 25 minutes.

ICFP 2008 programming contest

2008-07-15T17:05:00.008+02:00

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

2007-03-30T07:42:00.001+02:00

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

2006-12-03T01:32:00.001+02:00

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

You can download my full thesis or some slides.

Edit 2011/02/01: Here is the source code. It's a bit of a mess and it's going take a bit of work to get it going on newer systems because it probably requires an older wxWindows. The interesting parts are in src/linetools.py. If you find it useful or reference my work I'd love to hear about it.

One of my favourite opinionated 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

2006-07-24T22:27:00.001+02:00

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

2006-07-12T16:11:00.001+02:00

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

2006-06-24T17:02:00.000+02:00

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):

Flock (webbrowser):

wikidPad (note keeper):

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

os.listdir iterator

2006-05-21T19:33:00.001+02:00

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

2006-05-04T23:28:00.001+02:00

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".

icfp contest date announced

2006-03-30T23:53:00.001+02:00

It's clear what I'll be doing the weekend of July 21–24. The annual ICFP programming contest is the programming contest. This year I have to enter. Even if my solution doesn't run.

scite & bicycle repair man

2006-02-24T13:04:00.001+02:00

SciTE has been my favorite editor for a long time now. Especially for Python code. But there are two things I really miss: refactoring capabilities and a graphical code overview.

A few years ago I integrated refactoring using Bicycle Repair Man. That code has been lost but yesterday I decided to quickly rewrite it. It ~~won't work with files using tabs for indentation~~ (fixed with hack) due to an irritating bug in SciTE (which still hasn't been fixed since I filed it in 2003, unfortunately). Comments and suggestions are welcome!

Download it here: http://bitbucket.org/janto/snippets/src/tip/scitebike.py
See the file for installation instructions.

Now about that graphical code overview...

motion capture in python

2006-01-14T16:54:00.001+02:00

You know those suits with the ping-pong balls attached to it? The kind they use in motion capture? I thought it would be really cool if I could build my own. Then I'd be able to film my kickboxing and analyze it afterwards.

The current state-of-the-art seems to be tracking a magnetic field with the sensors on the suit. Unfortunately I don't have the resources to do that. So I'm going with the older way: visually tracking the markers.

I capture frames using my cheap webcam and the VideoCapture Python library. Others have used it for simple motion detection but not motion tracking. I decided to track the motion of red objects. Why red? Well, it's one of the least common colours in my office and is usually concentrated to a small area (bottle caps, mugs, books).

To get my hands on the red pixels I can't simply extract the R from RGB images. If a colour has a red component it could also be white, yellow, magenta... So you take the R and subtract the G and B. Ignoring values below zero you now have a gauge for the "redness" of a pixel.

(Extra points: Correct me if I'm wrong, but I believe "R minus G minus B" will give you a "redness" plane that intersects the xy chromaticity diagram (see sRGB color space) as a line running from blue to green along the edge of the sRGB gamut. The triangular plane segment within the gamut reaches it's "peak" at the maximum red representable by sRGB.)

This is a simple way to find the maximum red point on the image. I drew a crosshair over that point for clarity. With the series of images captured by the webcam I constructed an animated gif. So the system tracks a red object. Cool.

However, what I want to do is track more than one red object. I did this by forming clusters of red dots above certain intensity.

How do you form clusters? Well I used the K-means algorithm, conveniently included with SciPy. Et viola! It seems to do a pretty good job of it.

Not bad for a days work. Only 150 lines of Python. Of course it is at this point that my fear is confirmed: My webcam doesn't seem up to the task of tracking the speed of my movements. So before I jump around with a bunch of red markers on my body, I'll need a better camera.

Edit: You can download a rough version of the code here: motion_capture.zip. Parts are commented out so you don't need a webcam. You will need Python, SciPy and PIL however. I hope this works...

Another Edit: Here's an alternative I wrote (vr_tracker2.zip) that uses numarray, Pycluster and PIL instead. I'm starting to dislike SciPy. If there are enough requests I think I'll have to do another write-up.