Tag: programming

Reflecting on Participating in the Vlaamse Programmeerwedstrijd

Last Wednesday, I participated in the fourth edition of the Vlaamse Programmeerwedstrijd (VPW), hosted by PHL in Hasselt. The VPW is a Flemish programming contest inspired by the ACM International Collegiate Programming Contest (ICPC). Participants compete in teams of 3 and are divided into three different categories: high school students (category I), undergraduate students (category II), and graduate students or professionals (category III). Teams get 3 hours to solve 5 problems in one of 12 supported programming languages, using a single computer.

My team competed in category III and consisted of myself and two colleagues. Our main motivation was fun, and curiosity of how well (or bad) we would do. Also, since I was encouraging students to participate, it wouldn’t hurt to set an example by participating myself too.

Or so I thought Our team eventually did not do well, as we only managed to correctly solve 1 out of 5 exercises. There was a big gap between the top 5 and the other teams in our category. Only the teams ranking 1st and 2nd correctly solved all problems. The 3rd team solved 4 problems, the 4th and 5th ranked teams solved 3 problems, and from then on teams only solved 2 problems or less (four teams didn’t solve any problems). All except 1 team in the top 5 already participated in this contest before. This year’s winner actually ranked 21st last year in the Northwestern European Regional Programming Contest (NWERC), which is a European contest that serves as a qualifier for the ACM ICPC World Finals. By the way, kudos to the two teams of Master’s students from our university who managed to rank 7th and 9th (and beat us too).

Nevertheless, I had a lot of fun participating. I think I have a better idea now of what matters in this kind of contest and how we could do better in the future. Here is a quick list of factors that I feel are important:

Speed

You have to work really fast. Teams get 3 hours for 5 problems, which comes down to 36 minutes per problem. That includes reading the problem description, thinking about the solution, actually coding it up and verifying that it works!

You can bring notes, books and existing code along (although, obviously, you are not allowed to use the web), so it makes sense to build your own library of useful algorithms and data structures which you can use, either written down on paper or available in code. This includes things like graphs, trees, DFS, BFS, backtracking, the Sieve of Eratosthenes, Dijkstra and Floyd-Warshall. For example, we skipped one of the problems since we didn’t have a well-tested data structure available for it. Of course, you should also understand these algorithms and data structures and know when to use them.

Since speed is important, this means you have to be proficient in the language you’re using. You don’t have time to look up how a certain feature works, so make sure you know how to read input (obviously), how to work with built-in data structures (e.g. lists, strings, dictionaries, stacks, tuples) and how to perform common operations (e.g. copying containers, mathematical operations on numbers, replacing characters in strings, regex matching). We used Python, which has a few nice features such as built-in eval (useful for evaluating strings of mathematical expressions with the right operator precedence), easy I/O, list comprehensions, built-in combinations and permutations functions, while also being easy to learn. I heard that most of the top-scoring teams were using Haskell.

Know about Time Complexity

This is really essential. You have to be able to quickly assess the time complexity of your algorithm and decide whether it will good enough. Most problem descriptions include upper bounds on their inputs, which you should take into account (even if the example input is very small). This helps you to discard inefficient algorithms, and gives you more time to work out a better one. Most programs will have to perform well on large inputs, which means you will usually have to do better than O(N^2).

We made this mistake twice, because we were stressing over the amount of time left and wanted to quickly code up a working solution. While you can optimize your code, you don’t have time to change your algorithm when you have just finished a working (but slow) solution. With about 25 minutes left, we had a working version for one of the problems, but didn’t succeed in optimizing that solution further to avoid exceeding the time limit for the contest input. So eventually, we didn’t get any points for our solution. What we should have done instead was think about the time complexity of our algorithm first, and then discard it when we would have noticed that it didn’t scale.

Moreover, C, C++ (and Java) have an advantage over scripting languages in terms of performance, since a suboptimal algorithm in C/C++ (e.g. O(N^2) instead of O(NlogN)) might get very close to the time limit but could still be fast enough. The same algorithm implemented in a scripting language will almost always be too slow. If you’re programming in Python, just try running your code with CPython and PyPy to see what I mean. Here’s an example of running naive matrix multiplication (takes cubic time) of two randomized 500×500 matrices in CPython versus PyPy:

$ time python n3matrix.py 500
real	2m30.598s
user	2m30.189s
sys	0m0.068s
$ time pypy n3matrix.py 500
real	0m13.244s
user	0m13.137s
sys	0m0.064s

The PyPy version runs in 13 seconds and would probably not exceed the contest time limit, while the CPython version takes a whopping 150 seconds! Even though there are great libraries for matrix operations in Python (hello NumPy!), this still matters since most programming contests don’t allow the use of external libraries.

Here’s a similar example of sorting a list of 10.000 elements using bubble sort (a quadratic algorithm):

$ time python n2sort.py 10000
real	0m38.837s
user	0m38.730s
sys	0m0.016s
$ time pypy n2sort.py 10000
real	0m2.284s
user	0m2.192s
sys	0m0.036s

Of course, one could also argue that scripting languages allow you to implement and debug a solution more quickly than C/C++, but I guess it all depends on how fluent you are in your language of choice.

Teamwork

Although you work in teams of 3 people, you can only use one computer, which means only one person at a time can do the actual coding. You will have to divide tasks. For example, one team member could try to get a head start on the next problems, or could sort problems in order of difficulty to select the next problem to work on collectively. I think this actually worked quite well in our team.

In our case, it helped to have the fastest programmer/typist on the keyboard most of the time, although we did switch several times when someone had an idea they wanted to try. If you switch a lot, make sure you standardize somewhat on the setup you use, or at least allow easy switching between tools. We made sure we had different editors on the laptop set up to work in a way that the other team members were comfortable with. Because we used Python, we also had to standardize on the number of spaces used for indentation.

Practice and Study

Finally, the best way to get better is by practicing (exemplified by the number of top-scoring teams who also participated in previous editions of the contest). You can practice on problem sets from previous years or online problems sets (e.g. Project Euler, UVA, or SPOJ). Once you get better, it will probably also help to practice problems in contest conditions: as a team, with a time limit and just a single computer.

However, just practicing more probably won’t cut it. You are also going to need a good reference book on algorithms to look up problems, and suitable algorithms or heuristics for these problems. Since you won’t have enough time to read through books during the competition, you need to have this knowledge in your head (i.e. by putting the theory from the books into practice). I think you can only get better through a combination of theory and practice: studying different techniques and applying them in solutions to programming problems. Books on algorithms and data structures that I liked myself are: Skiena’s The Algorithm Design Manual, CLRS and Sedgewick’s Algorithms.

Of course, these are just my own observations, so comments are always welcome!

Getting up and running with the Kinect in Ubuntu 12.04

I’m currently experimenting a bit with the Kinect depth camera, which I intend to use for a prototype. I’ve played around with the device before on Windows using the Microsoft Kinect SDK. Setting up libfreenect on Windows is actually quite a pain, which was the reason why I started with the Microsoft SDK. As I wanted to code in Python, I’ve had a look at PyKinect and the Python Tools for Visual Studio (see also this PyCon US 2012 talk about building a Kinect game with Python). Unfortunately, the PyKinect samples seem to be outdated, and don’t work with the latest version of the Kinect SDK (version 1.0, released in February).

So I decided to see how far I would get with the Kinect and libfreenect on Ubuntu (12.04). Step 1: install the libfreenect demos to test if it works (this will also install libfreenect and its dependencies).

$ sudo apt-get install libfreenect-demos

So far so good. Unfortunately, the demo application wouldn’t start:

$ freenect-glview 
Kinect camera test
Number of devices found: 1
Could not claim interface on camera: -6
Could not open device

Strange.. I did another check to see if my user was in the plugdev group (which
was the case):

$ groups jo
jo : jo adm cdrom sudo dip plugdev lpadmin sambashare

Then I noticed that the Kinect’s LED kept blinking continously, which usually means there’s some sort of connection problem. It was correctly recognized, though:

$ lsusb
...
Bus 002 Device 007: ID 045e:02b0 Microsoft Corp. Xbox NUI Motor
Bus 002 Device 008: ID 045e:02ad Microsoft Corp. Xbox NUI Audio
Bus 002 Device 009: ID 045e:02ae Microsoft Corp. Xbox NUI Camera

After a quick web search for the specific libfreenect-glview error message, I learned that recent versions of the Linux kernel prevent libfreenect from claiming the Kinect as they now include a driver to support the device as a regular webcam (see kinect.c), which is actually quite cool. This also means there should be a specific video device for the Kinect (/dev/video1 in my case).

The kernel modules are indeed loaded:

$ lsmod | grep -i gspca
gspca_kinect           12936  0
gspca_main             28366  1 gspca_kinect
videodev               98259  2 gspca_main,uvcvideo 

Let’s try playing the camera stream using GStreamer and Video4Linux:

$ gst-launch-0.10 v4l2src device=/dev/video1 ! video/x-raw-yuv ! ffmpegcolorspace ! xvimagesink

That seems to work!

The Kinect actually has two image sensors: an RGB camera and a depth sensor, which consists of an infrared laser projector and a monochrome CMOS sensor. A depth map is created by projecting structured infrared light and capturing the resulting image from the monochrome sensor. As I wasn’t sure how to grab an image from the monochrome sensor, I contacted the author of the kernel module (Antonio Ospite). He told me it’s possible to get a monochrome image by specifying an image size of of 640×488 pixels (instead of the usual 640×480). Note that the kernel module currently only supports video streams from the monochrome sensor as unprocessed output.

If we pass that specific width and height to GStreamer, we get this:

It’s also possible to get the full-size (1280×1024) monochrome image. However, most webcam apps will just show the video stream from the RGB sensor for that resolution as you can’t specify that you want the specific Y10B format. To do that, you can use a separate program like qv4l2, which can be installed as follows:

$ sudo apt-get install qv4l2

To get the full-size monochrome image, run qv4l2, open the /dev/video1 device in raw mode (File > Open raw device), select 1280×1024 for the frame size, and “Y10B – Y10B” for the capture format, and click the red capture button:

OK, back to running the libfreenect demo. Someone over at superuser.com suggested to remove the modules (so that the user-mode libfreenect driver could
take over) and run libfreenect-glview again.

And indeed, after removing both gspca modules, the freenect-glview demo did work:

$ sudo modprobe -r gspca_kinect 
$ sudo modprobe -r gspca_main
$ freenect-glview 
Kinect camera test
Number of devices found: 1
GL thread
Write Reg 0x0006 <= 0x00
Write Reg 0x0012 <= 0x03
Write Reg 0x0013 <= 0x01
Write Reg 0x0014 <= 0x1e
Write Reg 0x0006 <= 0x02
Write Reg 0x0005 <= 0x00
Write Reg 0x000c <= 0x00
Write Reg 0x000d <= 0x01
Write Reg 0x000e <= 0x1e
Write Reg 0x0005 <= 0x01
...

The left side of the window shows a colored depth image, while the right side shows the RGB image from the camera. Of course, it would be quite cumbersome to remove the modules again every time you want to use libfreenect. One option is to blacklist the gspca module as follows:

$ echo "blacklist gspca_kinect" >> /etc/modprobe.d/blacklist.conf

Now that we've got that sorted out, I'll try out the libfreenect Python wrapper (or perhaps SimpleCV).

Update: Antonio Ospite pointed out in the comments that recent versions of libfreenect (0.1.2) can automatically detach the kernel driver. There's a PPA available by Florian Echtler with updated libfreenect packages for Ubuntu 12.04.

Python introduction movie

I just wanted to share this movie about the Python programming language. Although it’s a bit dated, I feel the movie still provides a nice overview of the benefits of Python, and explains why the language is good for educational purposes. It can be found at python.org.

You’ll see interviews with Guido van Rossum (creator of the Python language), Eric S. Raymond (author of “The Cathedral and the Bazaar” and the excellent article “Why Python?”), and Tim Peters (known a.o. from The Zen of Python).

The film was originally called “A Python Love Story”, and was was made in 2001 by a class of high school students in Yorktown High School (Arlington, Virginia) together with their Computer Science teacher Jeff Elkner. Elkner is known for translating Allen Downey‘s “How to Think Like a Computer Scientist” into Python. The original (and longer) version of the video is available from the Python Bibliotheca.

Facade update: code available and information about related student projects

My previous posts on face detection with Python and on changing the user’s presence when he/she is detected by the webcam are two of the most popular articles on my blog. There were quite a few comments that asked about the code for this project.

Although I already created a Facade project page a while ago and made the code available through Bazaar, I never announced it here. To make it easier to try the script out, I also uploaded an archive of the code. This version includes a simple Python script that works on Windows (simple_winclient.py) that performs face detection.

I noticed today that Jinwei Gu, a PhD student at the University of Columbia and teaching assistant for the course COMS W4737 (E6737) Biometrics, included my blog post in a list of links to resources for doing face detection.

Last year, two students improved the presence detection in Facade during their Bachelor’s theses.

Bram Bonné worked on the network aspect, to allow users to have their presence detected on multiple computers. When users would move from one computer to another (or to a mobile device), their messages would automatically be routed to their current machine.

Here are a few screenshots from Bram’s thesis:

Multi-device presence

An everywhere messaging service that takes into account the user&#039;s presence.

Bram also created a demo video of his system:

Kristof Bamps worked on supporting a more diverse set of sensors (e.g. presence of a Bluetooth phone, keyboard and mouse input). He used a decision tree to model all these sensors, and determine the user’s correct presence based on the collected information.

Two screenshots from Kristof’s thesis:

Showing the user&#039;s presence state

A history of presence changes

Kristof’s demo video:

I have unfortunately not yet found the time yet to merge Kristof’s and Bram’s code into the main Facade branch, but this should not be too big of a problem.

Small update on face detection post

Just a quick update on my previous post. I hooked my code up to a D-Bus daemon, and used it to detect if I was sitting behind my desk or not.

I had to position the camera a bit lower, because it would sometimes not recognize my face when I was looking at the bottom of my screen. Having a dual-monitor setup doesn’t help either, since you should ideally position the webcam in the middle of the two displays to have good coverage. I positioned the webcam in the middle of the two displays at the bottom and tilted it upwards, which gives good results:

I guesstimated that if the system couldn’t detect a face for a period of 10 seconds, I would be away from my desk (or at least not paying attention to the screen). I played around a bit with pygtk and notify-python to create a status icon and show notification bubbles whenever my status changed. Here’s what happens when it detects that I’m away from my desk (notice the bubble in the upper right corner):

When I return, the system will change its status icon accordingly and notify me again:

OpenCV is fun!