With the help of the folks here from OzLabs, I coordinated the linux.conf.au hackfest. I thought it'd be neat to post a few notes on the questions, as well as some approaches that we liked.
If you're interested in taking a look before we've spoiled all of the answers, the hackfest questions are up here.
The answers shown here are by no means the outright best way to solve the problems presented, but should be a decent starting point. There may be better answers around - in fact, if you have a suggestion, feel free to email me. However, the judges' decisions on the hackfest prizes are final.
Because this will be a fair bit of content, I'll split up the discussion over a number posts, each covering a couple of questions.
Finally, kudos to the participants of this year's hackfest, we had some great entries. Hope to see you all next time!
1. Jail Break
Write a program which when run chrooted in an empty directory, with euid
of 0, will escape from the chroot jail and demonstrate it has escaped by
creating a file called
/tmp/escaped.txt containing your
This one could be solved by a touch of googling. The core of the answer looks something like:
mkdir(TEMP_DIR, 0755); chroot(TEMP_DIR); for (x = 0; x < 1024; x++) chdir(".."); chroot(".");
However, some folks took the googling thing a little too far, and also
included other functionality, like starting a shell in the broken-out
environment, instead of writing to
/tmp/escaped.txt. So, for my
first piece of advice for the aspiring hackfest entrant: read the
2. Finding circles
Write a program to find the position of circles in an image.
Your program should take one command-line argument, the filename of the input image. The output of your program will be the coordinates of circles found in the image, one circle per line, in the format
[jk@pokey hackfest]$ ./find-circles input.png 331,79 399,204 367,133 579,44 212,237 206,416 516,144 292,409 161,438
Coordinates are relative to the top-left corner of the image.
The input file will be in png format, greyscale, with 8 bits per pixel. We suggest you use a support library to read your image data; if your submission is in C, you can use read-png.c as an example of using libpng, or include it as part of your entry.
The following images are representative of the input images we will test your program with. Each of these images contains 30 circles; the final images may contain varying numbers of circles. Click on the image for the full-size version.
|no noise||1% noise||4% noise||32% noise||64% noise|
You may assume the following:
- All of the circles are fully contained within the image
- The circles don't overlap (however, they may be touching).
The circles we test with may be a different size than the sample images, but you can assume that all circles in a single input image are the same size.
We will test your program on a set of images, with a total of 100 circles. One point is given for each correctly found circle (within a tolerance of ±2 pixels in both axes). Points will be deducted for reporting spurious circles.
One "classic" approach to finding circles is to use a Hough Transform. To do this:
- Threshold to produce a binary image.
- Remove noise, for example, using an open-close operation.
- Perform edge-detection, so you have a set of circle outlines, rather than solid circles.
- Allocate a 3D accumulator array (ie, width × height × possible radii).
- For each white pixel in the image, and each possible radius r, count it as a 'vote' (in the accumulator array) for a circle centered on all points r-distance from the pixel.
- Find maxima in the accumulator array. Coordinates of the maxima correspond to the centres of the circles.
The disadvantage of this approach is that it takes a lot of time to code, and the hackfest only runs for 3 hours (the advantage being that you get to make pretty graphs like this).
So, we can do a couple of things to side-step some of the tricky stuff. These really highlight the 'hack' part of 'hackfest':
- Instead of edge-detecting, just count each white pixel as a vote for a set of circles from 0 to r distance away. The accumulator gets a little messy, but it should still work
- Because we're now counting so many points, and not relying on edge detection (which really seems to suffer from a noisy image), don't worry about removing noise, it should all average out in the end, right?
- The thresholding doesn't need to be a separate step, just do an
if (pixel > threshold)" when walking through the image.
So, I'd probably end up coding something like this: (it may look like python, but it's pseudocode)
for y in 0..rows: for x in 0..cols: if image[y][x] > threshold: increment_accumulator(accum, x, y, radius)
increment_accumulator(accum, x, y, r) increments the
accumulator values at all points which lie within a circle of radius r
centered at (x,y). That can be repeated for possible radii.
Impressively, this is the basic gist of the entries we got. Even more impressively, one of the submissions managed to find 9 of the 10 circles in this image:
Pretty freakin' cool, huh?