Der zweite Platz der Code Competition “Rucksackproblem”

Herzlichen Glückwunsch!

Patrick gewinnt mit seiner in Java entwickelten Lösung den zweiten Platz bei der Code Competition “Rucksackproblem”. Besonders beeindruckend sind die von Patrick implementierten Algorithmen und seine Überlegungen dazu. Herzlichen Glückwunsch!

IT-Talents: Hallo Patrick, herzlichen Glückwunsch zu Deinem zweiten Platz bei der Code Competition „Rucksackproblem“! Erzähl den anderen IT-Talenten doch kurz etwas über Dich.

Patrick: Mein Name ist Patrick, ich bin 20 Jahre alt und studiere momentan Wirtschaftsinformatik im 5. Semester an der TU München. Nebenher arbeite ich in einer Firma für technische Kommunikation als Werkstudent in der Anwendungsprogrammierung. Mit dem Programmieren, vor allem in Java, habe ich so etwa ab der 10. Jahrgangsstufe angefangen, weil Java ab diesem Zeitpunkt auch Thema im Informatikunterricht war. Das war aber nur der Startschuss – seitdem habe ich natürlich stetig weiter gelernt und mich letztlich sogar für ein interdisziplinäres Informatikstudium entschieden, weil mich auch wirtschaftliche Vorgänge interessieren.

IT-Talents: Was hat Dich motiviert, an der Competition teilzunehmen und wie bist Du auf den Wettbewerb aufmerksam geworden?

Patrick: Letztes Jahr bin ich zum ersten Mal auf IT-Talents und die Code Competitions aufmerksam geworden, als ich mir die Competition „Kampf gegen Mühlen“ auf Facebook vorgeschlagen wurde. Seitdem folge ich IT-Talents und den Themen der Competitions. Genau wie bei meiner Teilnahme bei der Codecompetition zum Problem des Handlungsreisenden, habe ich teilgenommen, weil ich mich sehr gut für grundlegende Probleme der Informatik begeistern kann. Und wenn ein guter Lösungsversuch in einem solchen Umfeld auch noch honoriert wird – wer kann da schon nein sagen?

IT-Talents: Wie bist Du an die Lösung der Aufgabenstellung herangegangen? Hattest Du schon Erfahrung mit dem Rucksackproblem?

Patrick: Ja, das Problem wurde in einer Vorlesung, an der ich teilgenommen habe, im Rahmen eines Überblicks über verschiedenste Probleme, die als lineares Programm darstellbar sind, behandelt – allerdings nur oberflächlich. Die Vorlesung fixierte sich vor allem auf das Lösen solcher Probleme mit dem Simplex-Algorithmus, aber da ich den schon kannte, suchte ich für diese Competition nach Alternativen. So entdeckte ich bei meinen Recherchen einen pseudo-polynomiellen, matrixorientierten Algorithmus, der nur mit pareto-optimalen Lösungen arbeitet und so die beste Lösung findet. Leider scheitert dieser Ansatz bei wachsender Anzahl an Elementen aufgrund von Speicherbeschränkungen sehr schnell, und so fügte ich noch einige Heuristiken hinzu, deren Ergebnisse ich schließlich mit einem genetischen Algorithmus zu verbessern versuchte.

IT-Talents: Du hast Dich für eine Lösung der Aufgabenstellung in Java entschieden, wieso?

Patrick: Das ist recht einfach: Java ist aktuell noch die einzige Sprache, in der ich wirklich gut bin und ich habe sie in den Jahren auch zu lieben gelernt, trotz der Kritik, die sie immer wieder einstecken muss. Ich fühle mich in dem Umfeld wohl und arbeite gerne damit, auch in meinem Job. Seit einiger Zeit beschäftige ich mich zusätzlich mit Webentwicklung in JavaScript und HTML/CSS, empfand dies aber als weniger geeignet für die Aufgabe.

IT-Talents: Welche Probleme sind bei der Entwicklung der Software aufgekommen? Wie lange hat die Entwicklung gedauert?

Patrick: Einige Schwierigkeiten hatte ich bei der Implementierung des pseudo-polynomiellen Algorithmus. Obwohl er am Ende nicht wirklich viel Code besitzt, war der Weg doch sehr steinig. Von falsch herum gefüllten Tabellen bis zu vollkommen verwirrenden Ausgaben beim Tracing durch die fertige Tabelle aufgrund eines falschen Operators mitten im Code war alles dabei. Ich erinnere mich auch, einmal fast alles hingeschmissen zu haben – aber wenn ich in etwas schon Arbeit gesteckt habe, mache ich es auch fertig. Und das algorithmische Ergebnis kann sich ja scheinbar sehen lassen 😉
Ich denke, dass ich insgesamt zwei Wochen gebraucht habe, aber nicht jeden Tag daran gearbeitet habe. Ich schätze, dass ich etwa 50 Stunden investiert habe.

IT-Talents: Und was hast Du durch die Entwicklung gelernt?

Patrick: Ich hatte zuvor nie Kontakt mit genetischen Algorithmen. Wie nützlich diese sein können, um sich optimalen Lösungen anzunähern, ist mir erst durch diese Competition klar geworden. Auch wenn mein Ansatz sicher noch etwas ausgebaut werden kann, fand ich diese Erfahrung sehr beeindruckend und möchte mich auch zukünftig noch etwas mehr mit dieser Materie beschäftigen.

IT-Talents: Zu guter Letzt: Was würdest Du Dir thematisch gerne einmal als Code Competition wünschen?

Patrick: Was ich wirklich, wirklich sehr cool fände, wäre ein KI-Battle: In einem beliebigen Spiel (vielleicht auch noch nicht allzu häufig in KI umgesetzte, wie Rummikub) treten mehrere KI gegeneinander in einem Turnier an. Das Serverinterface stellt IT-Talents. Der Programmierer der Sieger-KI erhält die Preise der Competition. Das würde noch ein wenig mehr ansporn zum Wettberwerb geben und würde auch mal ein wenig Abwechslung in die Bewertungsmethode der Competitions geben. Da ist der Sieger dann eindeutig, wie auch im Sport – da kann niemand über subjektive Bewertungen meckern! 🙂

IT-Talents: Vielen Dank für Deine Teilnahme, das Interview und viel Spaß mit Deinem Gewinn 😉

Rückmeldungen