informatiCup 2008 by Linus Atorf & Malte Nuhn

informatiCup 2008
From late 2008 to early 2009, we (Linus Atorf and Malte Nuhn) took part in informatiCup 2008, a competition in programming and computer science amongst university students in Germany, Austria and Switzerland. Contestants choose to complete (usually) one of three tasks. The tasks mostly involve a difficult problem in informatics and require you to write a working program which implements the developed algorithm, as well as to document the solution properly. We heard about the contest in October 2008, but most of the heavy work was done late November until January 2009 (deadline was January 15th). The finals were held end of March 2009 in Bonn, Germany.

informatiCup 2008

From late 2008 to early 2009, we (Linus Atorf and Malte Nuhn) took part in informatiCup 2008, a competition in programming and computer science amongst university students in Germany, Austria and Switzerland. Contestants choose to complete (usually) one of three tasks. The tasks mostly involve a difficult problem in informatics and require you to write a working program which implements the developed algorithm, as well as to document the solution properly.

We heard about the contest in October 2008, but most of the heavy work was done late November until January 2009 (deadline was January 15th). The finals were held end of March 2009 in Bonn, Germany.

The problem
We chose to solve the first task called "CargoConcept". You can read the official description (or look at the pictures) here (0.1MB, PDF, German). Basically you're given a set of cities (2D-points) and a border (simple polygon). The problem is now to connect the cities through a network of tunnels, with the total length of all tunnels as short as possible. The borders must not be crossed by tunnels. Inside the border-polygon, you're allowed to insert "terminals" that connect to the tunnel network in order to reduce the total length. The question is then: Where to place those terminals, and how to build the tunnels?

The problem

We chose to solve the first task called "CargoConcept". You can read the official description (or look at the pictures) here (0.1MB, PDF, German).

Task description Basically you're given a set of cities (2D-points) and a border (simple polygon). The problem is now to connect the cities through a network of tunnels, with the total length of all tunnels as short as possible. The borders must not be crossed by tunnels. Inside the border-polygon, you're allowed to insert "terminals" that connect to the tunnel network in order to reduce the total length. The question is then: Where to place those terminals, and how to build the tunnels?

Our solution
After some investigation of the problem and various ideas, we played around a little with a brute-force solver (having in mind that due to performance issues this wouldn't be a feasible solution to win the contest with). We finally settled to use a evolutionary approach (genetic algorithm), something we always wanted to implement once. Our program is written in Python (it's actually our first program in Python), relying on a custom C-extension for numerical and performance-critical calculations. The GUI uses Qt, a graphics framework (we use the Python-wrapper PyQt). This way the program is executable on Windows, Linux, and Mac OS. Read on to see screenshots and videos, download the program, documentation, or our final presentation.

Our solution

Python powered After some investigation of the problem and various ideas, we played around a little with a brute-force solver (having in mind that due to performance issues this wouldn't be a feasible solution to win the contest with). We finally settled to use a evolutionary approach (genetic algorithm), something we always wanted to implement once.

Qt powered Our program is written in Python (it's actually our first program in Python), relying on a custom C-extension for numerical and performance-critical calculations. The GUI uses Qt, a graphics framework (we use the Python-wrapper PyQt). This way the program is executable on Windows, Linux, and Mac OS.

Read on to see screenshots and videos, download the program, documentation, or our final presentation.

Screenshots & Videos

The following videos demonstrate the way our algorithm works (or at least how it looks) and how problem data can be viewed or edited using the GUI.

Click on the pictures to enlarge:

Demo videos (download as DivX below):

Downloads
Download the complete program, "Evolutionary Approach for Solving Obstacle Avoiding EST Problems". It's open source (GPL). Python and C source code - (3 MB, zip archive) Includes source, documentation, and scripts, runs on Windows, Linux, Mac OS Windows executable - (11 MB, zip archive) Runs directly on all 32bit Windows systems Demo videos (same as YouTube videos above): Video 1 (3.4MB, DivX) - Loading data and using the world map Video 2 (7.1MB, DivX) - The genetic algorithm in action Video 3 (1.2MB, DivX) - Demonstrating implicit pathfinding Documentation is available here (in German): Paper (description of the algorithm) - (0.3MB, PDF) Manual (for the GUI) - (0.3MB, PDF) See our final presentation (in German): PowerPoint 2007 - (ppsx, 1.1MB, recommended) PowerPoint 95 to 2003 - (pps, 2.9MB, minor display problems) Portable Document Format - (pdf, 2.8MB, no animations)

Downloads

Download the complete program, "Evolutionary Approach for Solving Obstacle Avoiding EST Problems". It's open source (GPL).

Python and C source code - (3 MB, zip archive)
Includes source, documentation, and scripts, runs on Windows, Linux, Mac OS
Windows executable - (11 MB, zip archive)
Runs directly on all 32bit Windows systems

Demo videos (same as YouTube videos above):

Video 1 (3.4MB, DivX) - Loading data and using the world map
Video 2 (7.1MB, DivX) - The genetic algorithm in action
Video 3 (1.2MB, DivX) - Demonstrating implicit pathfinding

Documentation is available here (in German):

Paper (description of the algorithm) - (0.3MB, PDF)
Manual (for the GUI) - (0.3MB, PDF)

See our final presentation (in German):

PowerPoint 2007 - (ppsx, 1.1MB, recommended)
PowerPoint 95 to 2003 - (pps, 2.9MB, minor display problems)
Portable Document Format - (pdf, 2.8MB, no animations)

Results
In February 2008, we were both happy and relieved to receive an invitation to the finals of the top 5 teams in Bonn, Germany (although we had of course secretely hoped to be there all the time). As last test (and again underestimated by us) we had to present our work in front of a jury (the presentation can also be downloaded, see above). After the final presentation, the jury declared us (by very close decision) the winner: We made the 1st place and awarded prize money worth 4000 Euros! So all that's left to say now: A big thank you to all the organizers, participants, and of course sponsors for this great contest. We're particularly grateful to: Andre Alexander Bell - for his support with Python and Qt, and for providing us with an alternative SVN repository when ours went down Manuel Holtgrewe - for motivational chats about the contest and discussing ideas with us Mark Summerfield - for his great book and examples about Python and PyQt All the others - who always supported us and weren't annoyed (or were they?) by our constant ramblings about alle the problems we encountered

Results

In February 2008, we were both happy and relieved to receive an invitation to the finals of the top 5 teams in Bonn, Germany (although we had of course secretely hoped to be there all the time). As last test (and again underestimated by us) we had to present our work in front of a jury (the presentation can also be downloaded, see above).

After the final presentation, the jury declared us (by very close decision) the winner: We made the 1st place and awarded prize money worth 4000 Euros!

So all that's left to say now: A big thank you to all the organizers, participants, and of course sponsors for this great contest. We're particularly grateful to:

Andre Alexander Bell - for his support with Python and Qt, and for providing us with an alternative SVN repository when ours went down
Manuel Holtgrewe - for motivational chats about the contest and discussing ideas with us
Mark Summerfield - for his great book and examples about Python and PyQt
All the others - who always supported us and weren't annoyed (or were they?) by our constant ramblings about alle the problems we encountered

About us
Linus Atorf was born in 1984 in Düsseldorf, Germany. He currently lives in Aachen and studies physics in his 10th semester at RWTH Aachen University. Since 2007 he has also been working as student assistent with the Institute of Imaging and Computer Vision, where he's currently involved with LEGO Mindstorms Robots and MATLAB. Malte Nuhn was born in 1985 in Düsseldorf, Germany. He currently lives in Aachen and studies physics in his 10th semester at RWTH Aachen University, as well as computer science in his 8th semester. He was previously involved with various jobs in teaching as student assistant (subjects programming and theoretical physics). He's currently working on his diploma thesis in physics (about monitoring in grid computing). The team in this constellation has been successful before, the last time at "Sun Software Preis 2006", an annual competition held at RWTH Aachen University. The presentation is still available (0.3MB, PDF, German).
You can contact us by mail: linus (dot) atorf (at) rwth-aachen (dot) de malte (dot) nuhn (at) rwth-aachen (dot) de

About us

Linus Atorf was born in 1984 in Düsseldorf, Germany. He currently lives in Aachen and studies physics in his 10th semester at RWTH Aachen University. Since 2007 he has also been working as student assistent with the Institute of Imaging and Computer Vision, where he's currently involved with LEGO Mindstorms Robots and MATLAB.

Malte Nuhn was born in 1985 in Düsseldorf, Germany. He currently lives in Aachen and studies physics in his 10th semester at RWTH Aachen University, as well as computer science in his 8th semester. He was previously involved with various jobs in teaching as student assistant (subjects programming and theoretical physics). He's currently working on his diploma thesis in physics (about monitoring in grid computing).

The team in this constellation has been successful before, the last time at "Sun Software Preis 2006", an annual competition held at RWTH Aachen University. The presentation is still available (0.3MB, PDF, German).

You can contact us by mail:

linus (dot) atorf (at) rwth-aachen (dot) de
malte (dot) nuhn (at) rwth-aachen (dot) de

Disclaimer
Disclaimer of Warranty. The Software on this page is provided "AS IS," without a warranty of any kind. ALL EXPRESS OR IMPLIED REPRESENTATIONS AND WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. Limitation of Liability. IN NO EVENT WILL THE AUTHORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, RELATING TO THE USE, DOWNLOAD, DISTRIBUTION OF OR INABILITY TO USE SOFTWARE, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

Disclaimer

Disclaimer of Warranty. The Software on this page is provided "AS IS," without a warranty of any kind. ALL EXPRESS OR IMPLIED REPRESENTATIONS AND WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED.

Limitation of Liability. IN NO EVENT WILL THE AUTHORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, RELATING TO THE USE, DOWNLOAD, DISTRIBUTION OF OR INABILITY TO USE SOFTWARE, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.